JOIN

Позволяет объединить несколько источников данных (подзапросов или таблиц) по равенству значений указанных столбцов или выражений (ключей JOIN).

Синтаксис

SELECT ...    FROM table_1
-- первый шаг объединения:
  <Join_Type> JOIN table_2 <Join_Condition>
  -- исходная выборка -- записи в таблице table_1
  -- присоединяемая выборка -- записи в таблице table_2
-- следующий шаг объединения:
  <Join_Type> JOIN table_n <Join_Condition>
  -- исходная выборка -- результат объединения на предыдущем шаге
  -- присоединяемая выборка -- записи в таблице table_n
-- могут быть следующие шаги объединения
...
WHERE  ...

На каждом шаге объединения по заданным правилам определяются соответствия между строками исходной и присоединяемой выборок данных, и формируется новая выборка, в которую попадают все сочетания подошедших под условия объединения строк.

Типы объединения (Join_Type)

• INNER (по умолчанию) — Строки объединяемых выборок, для которых не найдено соответствие ни с одной строкой с другой стороны, не попадут в результат.
• LEFT - При отсутствии значения в присоединяемой выборке включает строку в результат со значениям колонок из исходной выборки, оставляя пустыми (NULL) колонки присоединяемой выборки
• RIGHT - При отсутствии значения в исходной выборке включает строку в результат со значениям колонок из присоединяемой выборки, оставляя пустыми (NULL) колонки исходной выборки
• FULL = LEFT + RIGHT
• LEFT/RIGHT SEMI — одна сторона выступает как белый список (whitelist) ключей, её значения недоступны. В результат включаются столбцы только из одной таблицы, декартового произведения не возникает;
• LEFT/RIGHT ONLY — вычитание множеств по ключам (blacklist). Практически эквивалентно добавлению условия IS NULL на ключ противоположной стороны в обычном LEFT/RIGHT, но, как и в SEMI, нет доступа к значениям;
• CROSS — декартово произведение двух таблиц целиком без указания ключевых колонок, секция с ON/USING явно не пишется;
• EXCLUSION — обе стороны минус пересечение.

Условия объединения (Join_Condition)

Для CROSS JOIN условие объединения не указывается. В результат попадет декартово произведение исходной и присоединяемой выборок, то есть сочетание всех со всеми. Количество строк в результирующей выборке будет произведением количества строк исходной и присоединяемой выборок.

Для любых других типов объединения необходимо указать условие одним из двух способов:

1. USING (column_name). Используется при наличии в исходной и присоединяемой выборках одноименной колонки, равенство значений в которой является условием объединения.
2. ON (equality_conditions). Позволяет задать условие равенства значений колонок или выражений над колонками исходной и присоединяемой выборок, или несколько таких условий, объединенных по and.

Примеры:

SELECT    a.value as a_value, b.value as b_value
FROM      a_table AS a
FULL JOIN b_table AS b USING (key);

SELECT    a.value as a_value, b.value as b_value
FROM      a_table AS a
FULL JOIN b_table AS b ON a.key = b.key;

SELECT     a.value as a_value, b.value as b_value, c.column2
FROM       a_table AS a
CROSS JOIN b_table AS b
LEFT  JOIN c_table AS c ON c.ref = a.key and c.column1 = b.value;

Для исключения необходимости в полном сканировании правой присоединяемой таблицы может использоваться вторичный индекс над колонками, входящими в условие соединения. Обращение ко вторичному индексу должно быть указано в явном виде, в формате JOIN table_name VIEW index_name AS table_alias.

Например, создание индекса для использования в условии соединения:

ALTER TABLE b_table ADD INDEX b_index_ref GLOBAL ON(ref);

Использование созданного индекса:

SELECT    a.value as a_value, b.value as b_value
FROM      a_table AS a
INNER JOIN b_table VIEW b_index_ref AS b ON a.ref = b.ref;

Если в выражении помимо JOIN выполняется фильтрация данных, то рекомендуется обернуть те условия, про которые известно, что они вернут true для большинства строк, в вызов функции LIKELY(...). Если предположение о преобладании положительных значений в условии окажется верно, такая подсказка может положительно сказаться на времени выполнения запроса. Также LIKELY может быть полезен в том случае, когда вычисление предиката ресурсоёмко и при этом сам JOIN значительно сокращает число строк.

Перед любым источником данных для JOIN можно указать ключевое слово ANY, которое служит для подавления дубликатов по ключам JOIN с соответствующей стороны. В этом случае из множества строк с одинаковым значением ключей JOIN остается только одна (не уточняется какая именно – отсюда и название ANY).
Данный синтаксис отличается от принятого в [ClickHouse], где ANY пишется перед типом JOIN и работает только для правой стороны.

Запрос

$t1 = AsList(
    AsStruct("1" AS key, "v111" AS value),
    AsStruct("2" AS key, "v121" AS value),
    AsStruct("2" AS key, "v122" AS value),
    AsStruct("3" AS key, "v131" AS value),
    AsStruct("3" AS key, "v132" AS value));

$t2 = AsList(
    AsStruct("2" AS key, "v221" AS value),
    AsStruct("2" AS key, "v222" AS value),
    AsStruct("3" AS key, "v231" AS value),
    AsStruct("3" AS key, "v232" AS value),
    AsStruct("4" AS key, "v241" AS value));

SELECT
  a.key, a.value, b.value
FROM ANY AS_TABLE($t1) AS a
JOIN ANY AS_TABLE($t2) AS b
ON a.key == b.key;

выдаст:

а без ANY выдал бы:

Стратегии выполнения JOIN в YTsaurus

Введение

В стандартном SQL поддерживается следующий синтаксис JOIN:

SELECT
  ...
FROM T1 <Join_Type> JOIN T2
ON F(T1, T2);

где F(T1, T2) - произвольный предикат зависящий от колонок обоих таблиц T1, T2.
В YQL подерживается только частный случай – когда предикат F сепарабельный, т.е имеет следующий вид:

SELECT
  ...
FROM T1 <Join_Type> JOIN T2
ON F1(T1) = G1(T2) AND F2(T1) = G2(T2) AND ...;

Такая структура предиката позволяет эффективно реализовать JOIN в рамках концепции map-reduce.

В YQL также как и в стандартном SQL можно сделать несколько JOIN в одном SELECT:

SELECT
  ...
FROM
T1 <Join_Type> JOIN T2 ON F1(T1) = G1(T2) AND F2(T1) = G2(T2) AND ...
   <Join_Type> JOIN T3 ON H1(T1,T2) = J1(T3) AND H2(T1,T2) = J2(T3) AND ...;

В настоящий момент такие JOIN выполняются последовательно и именно в том порядка, в котором написано в запросе.
Единственным исключением является стратегия StarJoin.

Вычисление ключей JOIN

Выполнение JOIN начинается с вычислениия ключей и сохранения из значений в отдельную колонку.
Такое преобразования происходит еще на уровне SQL парсера и является общиим для всех бэкендов (YDB, YTsaurus, DQ и т.п.)

Фактически запрос

SELECT
  ...
FROM T1 <Join_Type> JOIN T2
ON F1(T1) = G1(T2) AND F2(T1) = G2(T2) AND ...;

преобразуется в

SELECT
...
FROM (
    SELECT t.*,
           F1(...) as _yql_join_key1,
           F2(...) as _yql_join_key2, ...
    FROM T1 as t
) as t1
<Join_Type> JOIN (
     SELECT t.*,
            G1(...) as _yql_join_key1,
            G2(...) as _yql_join_key2, ...
    FROM T2 as t
) as t2
ON t1._yql_join_key1 = t2._yql_join_key1 AND t1._yql_join_key2 = t2._yql_join_key2 AND ...;

Приведение ключей к простому общему типу

Данная стадия уже является специфичной для YTsaurus. В ней ключевые колонки с обоих сторон приводятся к одинаковому простому типу.

Запрос

SELECT
  ...
FROM T1 as t1 <Join_Type> JOIN T2 as t2
ON t1.key1 = t2.key1 AND t1.key2 = t2.key2 AND ...;

преобразуется в

SELECT
...
FROM (
    SELECT t.*,
           CastToCommonKeyType(key1) as _yql_join_key1,
           CastToCommonKeyType(key2) as _yql_join_key2,
    FROM T1 as t
) as t1
<Join_Type> JOIN (
     SELECT t.*,
           CastToCommonKeyType(key1) as _yql_join_key1,
           CastToCommonKeyType(key2) as _yql_join_key2,
    FROM T2 as t
) as t2
ON t1._yql_join_key1 = t2._yql_join_key1 AND t1._yql_join_key2 = t2._yql_join_key2 AND ...;

Приведение к общему типу необходимо для корректной работы map-reduce по ключам родственных, но разных типов.
Например, для ключей типа Int32 и Uint32, общим типом будет Optional<Int32>.
Если конвертацию в общий тип не сделать и оставить исходные колонки в качестве ключевых для map-reduce операций,
то YTsaurus будет рассматривать ключи -1 и 4294967295 как равные.

Такая конвертация нужна не всегда - например ключи типов Int32 и Optional работают корректно.

Дополнительно, ключи сложного типа (все что сложнее Optional от простого типа))
после каста в общий тип еще и конвертируются в строку:

if (
    YQL::HasNulls(casted_key), -- если где-то в ключе встречается null
    null,                      -- то конвертируем значение в null строкового типа (null в SQL не равен никакому значению, в том числа самому себе)
    StablePickle(casted_key),  -- иначе сериализуем значение в строковое представление
)

Такая конвертаця нужна, поскольку ключи сложных типов не поддерживаются в качестве ключей reduce операций в YTsaurus.

Таким образом, после всех конвертаций, мы получаем c обоих сторон JOIN ключи попарно однакового простого типа (с точностью до Optional).

Базовая стратегия JOIN (aka CommonJoin)

Базовая стратегия JOIN выбирается в тех случаях, когда не удается применить по каким-либо причнам остальные стратегии JOIN.
Эта стратегия поддерживает все типы JOIN, включая CROSS JOIN и реализуется через одну MapReduce операцию.

При этом в map стадии происходит:

1. приведение ключей к простому общему типу
2. при наличии модификатотора ANY одинаковые ключи "прореживаются" отдельным оконным фильтром – на окне некоторого размера (сотни мегабайт) детектятся строки с одинаковыми ключами и дубликаты отфильтровываются
3. обработка нуллов в ключах. При этом для INNER JOIN нуллы с обоих сторон отфильтровываются,
   а для LEFT/RIGHT/FULL JOIN строки с нулевыми ключами идут в отдельную выходную таблицу сразу из map стадии

Из map стадии строки с однаковым ключем попадают в одну YTsaurus reduce джобу, в которой собственно и происходиит JOIN.
Если необходимо, то результирующая таблца из reduce стадии объединяется с выходными таблцам из map стадии с помощью отдельной YTsaurus Merge операции.

Чтобы выполнить CROSS JOIN (в котором ключей нет), на map стадии всем строчкам обоих входных таблиц назначается одинаковый ключ 0.

Стратегия LookupJoin

Данная стратегия срабатывает, когда одна из таблиц сортирована по ключам JOIN, а вторая имеет очень малый размер (меньше ~900 строк).

LookupJoin поддерживается для следующих типов JOIN:

• INNER (малая таблица может быть с произвольной стороны)
• LEFT SEMI (малая таблца справа)
• RIGHT SEMI (малая таблица слева)

Стратегия LookupJoin реализуется через одну Map операцию по большой таблице, при этом малая таблица загружается в память.
Типы ключей при этом не обязательно должны совпадать – ключи малой таблицы кастятся к типу ключей в большой таблице.

В отличии от стратегии MapJoin (смотрите ниже), в LookupJoin значения ключей JOIN из малой таблицы попадают в
настройку ranges в YPath большой таблицы. Таким образом из большой таблицы вычитываются только строки с ключами JOIN, которые есть в малой таблице.

LookupJoin является наиболее эффективной стратегией JOIN, но налагает самые жесткие условия на типы JOIN
(они должны быть "фильтрующими" по большой таблице) и на размер малой таблицы (ключи должны "влезать" в максимально допустимое число ranges в YPath).
Кроме того, в LookupJoin не поддерживается ANY на стороне большой таблицы.

Настройки (PRAGMA) для стратегии:

Установка любого из этих значений в 0 приводит к отключению LookupJoin стратегии.

Стратегия SortedJoin (aka MergeJoin)

Данная стратегия срабатывает, когда обе таблицы сортированы по ключам JOIN.
При этом ключи JOIN должны быть совпадать по типам с точностью до Optional на верхнем уровне.

Если сортирована только одна таблица, а размер другой не превышает yt.JoinMergeUnsortedFactor * <размер сортированной таблицы>,
то стратегия SortedJoin также выбирается, при этом несортированная таблица сортируется отдельной YTsaurus операцией.
Значение настройки yt.JoinMergeUnsortedFactor по умолчанию составляет 0.2.

Стратегия SortedJoin поддерживает все виды JOIN кроме CROSS JOIN и реализуется через одну операцию Reduce.
При этом, по возможности используется режим reduce с внешними таблицами.
Кроме того, при уникальности ключей JOIN дополнительно включается настройка enable_key_guarantee = false.

Стратегию SortedJoin можно выбрать принудительно через SQL хинт:

SELECT * FROM T1 AS a JOIN /*+ merge() */ T2 AS b ON a.key = b.key;

В этом случае (если необходимо)

1. ключи JOIN будут приведены к общему типу
2. обе таблицы будут отсортированы по ключам JOIN

Настройки (PRAGMA) для стратегии:

Установка yt.JoinMergeTablesLimit в 0 отключает стратегию SortedJoin.

Стратегия MapJoin

Данная стратегия срабатывает, если одна из входных таблиц достаточно маленькая (размером не более чем yt.MapJoinLimit).
При этом меньшая таблица загружается в память (в виде словаря по ключам JOIN), а затем производится Map по большой таблице.

Данная стратегия поддерживает все виды JOIN (в том числе CROSS), но не выбирается если имеется ANY на большей стороне.

Уникальной особенностью MapJoin стратегии является возможность раннего выбора этой страттегии.
Т.е. когда малая входная таблица уже посчиталась и попадает под ограничения на размер, а большая таблица еще не готова.
В этом случае мы можем сразу выбрать MapJoin,
причем есть шанс что Map операция по большой таблице "склеится" с Map оперцией (например фильтром), которая эту большу таблиицу готовит.

Существует также шардированный варант MapJoin: малая таблица разбивается на yt.MapJoinShardCount частей
(каждая часть при этом не должна превышать yt.MapJoinLimit), каждая часть параллельно и независимо JOINится с большой таблицей через Map операцию,
и затем все полученные части объединяются через YTsaurus Merge.

Шардированый MapJoin возможен только для некоторых типов JOIN (INNER,CROSS, LEFT SEMI при условии что малая таблиица справа ункальна).

Настройки (PRAGMA) для стратегии:

Установка yt.MapJoinLimit в 0 отключает стратегию MapJoin.

Стратегия StarJoin

Особенностью данной стратегии является то, что она позволяет выполнять сразу несколько последовательных JOIN через одну операцию Reduce.

Стратегия возможна, когда к одной ("главной") таблице последовательно через INNER JOIN или LEFT JOIN присоединяются таблицы-словари, причем:

1. из главной таблицы во всех JOINах используются одинаковые ключи
2. все таблиицы сортированы по ключам JOIN
3. таблицы-словари еще и уникальны по ключам JOIN

Настройки (PRAGMA) для стратегии:

Порядок выбора стратегий

При выполнении JOIN стратегии пробуются в определенном порядке и выбирается первая подходящая.
Порядок при этом следующий:

1. StarJoin
2. LookupJoin
3. OrderedJoin
4. MapJoin
5. CommonJoin (всегда возможна)