SQL: Поиск симметричных пар в таблице

Решение

Анализ задачи

Нужно найти пары (X₁, Y₁) и (X₂, Y₂) из одной таблицы, где:

• X₁ = Y₂ (первый элемент первой пары = второй элемент второй пары)
• Y₁ = X₂ (второй элемент первой пары = первый элемент второй пары)

В примере:

• (1, 2) и (2, 1) — симметричные пары ✓
• (5, 6) и (6, 5) — симметричные пары ✓
• (3, 4) — нет парной строки (4, 3), поэтому не входит в результат

Решение 1: Базовое (использование JOIN)

SELECT DISTINCT
    p1.X,
    p1.Y
FROM pairs p1
JOIN pairs p2 ON p1.X = p2.Y AND p1.Y = p2.X
WHERE p1.X <= p1.Y  -- Исключаем дубликаты (выводим только меньшее значение первым)
ORDER BY p1.X ASC;

Объяснение:

1. JOIN: Соединяем таблицу с самой собой (p1 JOIN p2)

   • p1.X = p2.Y AND p1.Y = p2.X — условие симметричности
   • Для пары (1, 2) в p1 найдётся пара (2, 1) в p2

2. WHERE p1.X <= p1.Y: Фильтруем, чтобы вывести только одну из двух симметричных пар

   • (1, 2): 1 <= 2 ✓ → выводим
   • (2, 1): 2 <= 1 ✗ → не выводим

3. DISTINCT: На случай если в исходной таблице есть дубликаты одной и той же пары

4. ORDER BY p1.X: Сортировка в возрастающем порядке

Решение 2: С использованием WINDOW функций (эффективнее)

SELECT
    X,
    Y
FROM (
    SELECT
        X,
        Y,
        -- Проверяем, есть ли обратная пара в таблице
        COUNT(CASE WHEN p2.X = pairs.Y AND p2.Y = pairs.X THEN 1 END)
            OVER (PARTITION BY CASE WHEN X <= Y THEN X * 1000000 + Y ELSE Y * 1000000 + X END)
            AS has_pair
    FROM pairs
    LEFT JOIN pairs p2 ON pairs.X = p2.Y AND pairs.Y = p2.X
) t
WHERE has_pair > 0
    AND X <= Y  -- Выводим только в одной ориентации
ORDER BY X ASC;

Этот подход сложнее и менее читаем, но может быть быстрее для больших датасетов (избегаем двойного сканирования).

Решение 3: Через EXISTS (альтернативный подход)

SELECT
    X,
    Y
FROM pairs p1
WHERE EXISTS (
    SELECT 1
    FROM pairs p2
    WHERE p1.X = p2.Y AND p1.Y = p2.X
)
    AND X <= Y
ORDER BY X ASC;

Преимущество EXISTS:

• Останавливает поиск как только найдена одна matching строка
• Может быть быстрее на большых таблицах

Решение 4: С использованием HAVING (для агрегации)

SELECT
    MIN(X) AS X,
    MAX(Y) AS Y
FROM pairs
GROUP BY CASE WHEN X < Y THEN X * 1000000 + Y ELSE Y * 1000000 + X END
HAVING COUNT(*) = 2  -- Есть ровно 2 пары в противоположных направлениях
ORDER BY MIN(X) ASC;

Объяснение:

• GROUP BY: Группируем симметричные пары в одну группу
• HAVING COUNT(*) = 2: Проверяем, что для каждой пары есть ровно две строки (X, Y) и (Y, X)
• MIN/MAX: Берём минимум X и максимум Y (результат одинаков для (1, 2) и (2, 1))

Решение 5: Оптимизированное для больших таблиц

SELECT
    p1.X,
    p1.Y
FROM pairs p1
INNER JOIN pairs p2 
    ON p1.X = p2.Y 
    AND p1.Y = p2.X
    AND p1.X < p1.Y  -- Условие уже в JOIN, не в WHERE
ORDER BY p1.X ASC;

Почему это лучше:

• Фильтр p1.X < p1.Y в условии JOIN сокращает количество соединений
• Оптимизатор может лучше спланировать выполнение
• Исключаем DISTINCT (как следствие условия X < Y)

Сравнение решений

Рекомендуемое решение для production

SELECT
    p1.X,
    p1.Y
FROM pairs p1
INNER JOIN pairs p2 
    ON p1.X = p2.Y 
    AND p1.Y = p2.X
    AND p1.X < p1.Y
ORDER BY p1.X ASC;

Проверка на примере

Исходные данные:

X = 1, Y = 2
X = 2, Y = 1
X = 3, Y = 4
X = 5, Y = 6
X = 6, Y = 5

Выполнение JOIN:

p1.X=1, p1.Y=2 JOIN p2.X=2, p2.Y=1 → 1<2 ✓ → выводим (1, 2)
p1.X=2, p1.Y=1 JOIN p2.X=1, p2.Y=2 → 2<1 ✗ → не выводим
p1.X=3, p1.Y=4 JOIN нет p2 такой → не выводим
p1.X=5, p1.Y=6 JOIN p2.X=6, p2.Y=5 → 5<6 ✓ → выводим (5, 6)
p1.X=6, p1.Y=5 JOIN p2.X=5, p2.Y=6 → 6<5 ✗ → не выводим

Результат:

X | Y
--|--
1 | 2
5 | 6

Оптимизация для больших датасетов

Если таблица содержит миллионы строк:

-- 1. Создать индекс
CREATE INDEX idx_pairs_xy ON pairs(X, Y);
CREATE INDEX idx_pairs_yx ON pairs(Y, X);

-- 2. Использовать оптимизированный запрос
SELECT
    p1.X,
    p1.Y
FROM pairs p1
INNER JOIN pairs p2 
    ON p1.X = p2.Y 
    AND p1.Y = p2.X
    AND p1.X < p1.Y
ORDER BY p1.X ASC;

Анализ плана выполнения

EXPLAIN SELECT ...

NestedLoopJoin (Inner)
├── Scan pairs p1
│   └── Filter: p1.X < p1.Y
├── Scan pairs p2
│   └── Filter: p2.Y = p1.X AND p2.X = p1.Y
└── Sort
    └── Order by: p1.X

Оптимизатор будет использовать индексы для быстрого поиска соответствующих строк в p2.