Зроби сам: SQL JOIN на Java

Я часто собеседую розробників і часто задаю їм простий, як кувалда, питання — як всередині працює JOIN в SQL? У відповідь я зазвичай чую нескладне мукання про чарівні дерева і індекси, які швидше. Колись мені здавалося, що кожен програміст фахівець повинен знати, з чим працює. Згодом життя пояснила мені, що це не так. Але мені все ще не зрозуміло, як можна роками смикати базенку, навіть не здогадуючись, а що там у неї «під капотом»?

Я вірю, що особисто ви, мій читач — не такий. Ви-то вже точно знаєте всю таємницю цих СУБД. Ну, може бути, призабули шматочок — але нічого страшного, з ким не буває. Так давайте ж, як інтелігентні люди, разом повторимо, як працюють ці джойны і навіть самі реалізуємо парочку алгоритмів.

SQL JOIN

Постановка завдання
Я ставлю на співбесідах ось таку задачу. Є SQL команда
SELECT
left.K,
left.V1,
right.V2
FROM left
Right JOIN
ON left.K = right.K;

Потрібно виконати те ж саме на Java, тобто реалізувати метод
<K, V1, V2> List<Triple<K, V1, V2>> join(List<Pair<K, V1>> left, List<Pair<K, V2>> right);

Додатково я питаю, що потрібно змінити в сигнатурі та реалізації, щоб зробити вигляд, що ми працюємо з індексами.

Звучить не дуже складно, правда? Але давайте спочатку розберемося, для чого нам взагалі думати про пристрої джойнов?
  1. Знати теорію корисно з чисто пізнавальних міркувань.
  2. Якщо ви розрізняєте типи джойнов, то план виконання запиту, який виходить командою EXPLAIN, більше не виглядає для вас як набір незрозумілих англійських слів. Ви можете бачити в плані потенційно повільні місця та оптимізувати запит переписуванням або хинтами.
  3. новомодних аналітичних інструментах поверх Hadoop планувальник запитів або трохи тупуватий (див. Cloudera Impala), або його взагалі немає (див. Twitter Scalding, Spark RDD). В останньому випадку доводиться збирати запит вручну з примітивних операцій.
  4. Нарешті, є ризик, що одного разу ви потрапите на співбесіду до мене чи до іншого зануді. Від фортеці ваших знань буде залежати результат інтерв'ю. У цьому випадку ще одна прочитана стаття з хабра буде не зайвою.


Nested Loops Join
Самий базовий алгоритм об'єднання двох списків зараз проходять у школах. Суть дуже проста — для кожного елемента першого списку пройдемося по всім елементам другого списку; якщо ключі елементів раптом виявилися рівні — запишемо збіг в результуючу таблицю. Для реалізації цього алгоритму достатньо двох вкладених циклів, саме тому він так і називається.

public static <K, V1, V2> List<Triple<K, V1, V2>> nestedLoopsJoin(List<Pair<K, V1>> left, List<Pair<K, V2>> right) {
List<Triple<K, V1, V2>> result = new ArrayList<>();
for (Pair<K, V1> leftPair: left) {
for (Pair<K, V2> rightPair: right) {
if (Objects.equals(leftPair.k, rightPair.k)) {
result.add(new Triple<>(leftPair.k, leftPair.v, rightPair.v));
}
}
}
return result;
}

Основний плюс цього методу — повна байдужість до вхідних даних. Алгоритм працює для будь-яких двох таблиць, не вимагає ніяких індексів і перекладань даних в пам'яті, а також простий у реалізації. На практиці це означає, що досить просто бігти по диску двома курсором і періодично випльовувати в сокет збігу.

Проте ж, фатальний мінус алгоритму — висока часова складність O(N*M) (квадратична асимптотика, якщо ви розумієте, про що я). Наприклад, для джойна пари невеликих таблиць в 100к і 500к записів необхідно зробити аж 100.000 * 500.000 = 50.000.000.000 (50 млрд) операцій порівняння. Запити з таким джойном будуть виконуватися неввічливо довго, часто саме вони — причина нещадних гальм кривеньких самописних CMS'ок.

Сучасні РСУБД використовують nested loops join в самих безнадійних випадках, коли не вдається застосувати жодну оптимізацію. А які тут можуть бути оптимізації? — запитаєте ви. І, як мудрі аксакали, самі собі відповісте, що…

Hash Join
Якщо розмір однієї з таблиць дозволяє засунути її в пам'ять, значить, на її основі можна зробити хеш-таблицу і швиденько шукати потрібні ключі. Проговоримо трохи докладніше.

Перевіримо розмір обох списків. Візьмемо менший із списків, прочитаємо його повністю і завантажимо в пам'ять, побудувавши HashMap. Тепер повернемося до більшого списком і підемо по ньому курсором з початку. Для кожного ключа перевіримо, чи немає такого ж у хеш-таблиці. Якщо є — запишемо збіг в результуючу таблицю.

Тимчасова складність цього алгоритму падає до лінійної O(N+M), але потрібна додаткова пам'ять.

public static <K, V1, V2> List<Triple<K, V1, V2>> hashJoin(List<Pair<K, V1>> left, List<Pair<K, V2>> right) {
Map<K, V2> hash = new HashMap<>(right.size());
for (Pair<K, V2> rightPair: right) {
hash.put(rightPair.k, rightPair.v);
}

List<Triple<K, V1, V2>> result = new ArrayList<>();
for (Pair<K, V1> leftPair: left) {
if (hash.containsKey(leftPair.k)) {
result.add(new Triple<>(leftPair.k, leftPair.v, hash.get(leftPair.k)));
}
}

return result;
}

Що важливо, в часи динозаврів вважалося, що в пам'ять потрібно завантажити праву таблицю, а итерироваться по лівій. У нормальних РСУБД зараз є статистика cardinality, і вони самі визначають порядок джойна, але якщо з якоїсь причини статистика недоступна, то в пам'ять завантажується саме права таблиця. Це важливо пам'ятати при роботі з молодими кострубатими інструментами типу Cloudera Impala.

Merge Join
А тепер уявімо, що дані в обох списках заздалегідь відсортовані, наприклад, за зростанням. Так буває, якщо у нас були індекси по цим таблицям, або ж якщо ми отсортировали дані на попередніх стадіях запиту. Як ви напевно пам'ятаєте, два відсортованих списку можна склеїти в один відсортований за лінійний час — саме на цьому заснований алгоритм сортування злиттям. Тут нам належить схожа завдання, але замість того, щоб склеювати списки, ми будемо шукати в них загальні елементи.

Отже, ставимо за курсору в початок обох списків. Якщо ключі під курсором рівні, записуємо збіг в результуючу таблицю. Якщо ж ні, дивимося, під яким з курсорів ключ менше. Рухаємо курсор над меншим ключем на один вперед, тим самим «наздоганяючи» інший курсор.

public static <K extends Comparable<K>, V1, V2> List<Triple<K, V1, V2>> mergeJoin(
List<Pair<K, V1>> left,
List<Pair<K, V2>> right
) {
List<Triple<K, V1, V2>> result = new ArrayList<>();
Iterator<Pair<K, V1>> leftIter = left.listIterator();
Iterator<Pair<K, V2>> rightIter = right.listIterator();
Pair<K, V1> leftPair = leftIter.next();
Pair<K, V2> rightPair = rightIter.next();
if (Objects.equals(leftPair.k, rightPair.k)) {
result.add(new Triple<>(leftPair.k, leftPair.v, rightPair.v));
}

while (true) {
int compare = leftPair.k.compareTo(rightPair.k);
if (compare < 0) {
if (leftIter.hasNext()) {
leftPair = leftIter.next();
} else {
break;
}
} else if (compare > 0) {
if (rightIter.hasNext()) {
rightPair = rightIter.next();
} else {
break;
}
} else {
result.add(new Triple<>(leftPair.k, leftPair.v, rightPair.v));
if (leftIter.hasNext() && rightIter.hasNext()) {
leftPair = leftIter.next();
rightPair = rightIter.next();
} else {
break;
}
}
}
return result;
}

Якщо дані відсортовані, то тимчасова складність алгоритму лінійна O(M+N) і не потрібно ніякої додаткової пам'яті. Якщо ж дані не відсортовані, то потрібно спочатку відсортувати їх. З-за цього часова складність зростає до O(M log M + N log N), плюс з'являються додаткові вимоги до пам'яті.

Outer Joins
Ви могли помітити, що написаний вище код імітує тільки INNER JOIN, причому розраховує, що всі ключі в обох списках унікальні, тобто зустрічаються не більше, ніж по одному разу. Я спеціально зробив так з двох причин. По-перше, так наочніше — у коді міститься тільки логіка самих джойнов і нічого зайвого. А по-друге, мені дуже хотілося спати. Але тим не менш, давайте хоча б обговоримо, що потрібно змінити в коді, щоб підтримати різні типи джойнов і неунікальні значення ключів.

Перша проблема — неунікальні, тобто повторювані ключі. Для повторюваних ключів потрібно породжувати декартів добуток всіх соответствющих їм значень.
У Nested Loops Join чому це працює відразу.
У Hash Join доведеться замінити HashMap на MultiHashMap.
Для Merge Join ситуація набагато сумніша — доведеться пам'ятати, скільки елементів з однаковим ключем ми бачили.

Робота з неуникальными ключами збільшує асимптотику до O(N*m+M*n), де n і m — середнє записів на ключ у таблицях. В виродженому випадку, коли n=N і m=M, операція перетворюється у CROSS JOIN.

Друга проблема — треба стежити за ключами, для яких не знайшлося пари.
Для Merge Join ключ без пари видно відразу для всіх напрямів JOIN'а.
Для Hash Join відразу можна побачити брак відповідних ключів при джойне ліворуч. Для того, щоб фіксувати непарні ключі праворуч, доведеться завести окремий прапор "є пара!" для кожного елемента хеш-таблиці. Після завершення основного джойна треба буде пройти по всій хеш-таблиці і додати в результат ключі без прапора пари.

Для Nested Loops Join ситуація аналогічна, причому все настільки просто, що я навіть осилив це закодить:

public static <K, V1, V2> List<Triple<K, V1, V2>> nestedLoopsJoin(
List<Pair<K, V1>> left,
List<Pair<K, V2>> right,
JoinType joinType
) {
// Масив для позначення ключів з правого списку, яким не знайшлося пари в лівому
BitSet rightMatches = new BitSet(right.size());

List<Triple<K, V1, V2>> result = new ArrayList<>();

for (Pair<K, V1> leftPair: left) {
// Прапор для позначення ключів в лівому списку, яким не знайшлося пари в правому
boolean match = false;
for (ListIterator<Pair<K, V2>> iterator = right.listIterator(); iterator.hasNext(); ) {
Pair<K, V2> rightPair = iterator.next();
if (Objects.equals(leftPair.k, rightPair.k)) {
result.add(new Triple<>(leftPair.k, leftPair.v, rightPair.v));

// Відзначаємо пари
match = true;
rightMatches.set(iterator.previousIndex(), true);
}
}

// Заповнюємо невідповідності в лівому списку
if ((joinType == JoinType.LEFT || joinType == JoinType.FULL) && !match) {
result.add(new Triple<>(leftPair.k, leftPair.v, null));
}
}

// Заповнюємо невідповідності в правому списку
if (joinType == JoinType.RIGHT || joinType == JoinType.FULL) {
for (int i = 0; i < right.size(); ++i) {
if (!rightMatches.get(i)) {
Pair<K, V2> rightPair = right.get(i);
result.add(new Triple<>(rightPair.k, null, rightPair.v));
}
}
}
return result;
}


Морализаторское післямова
Якщо ви дочитали досюда, значить, стаття здалася вам цікавою. А значить, ви пробачите мені невелику порцію моралей.

Я дійсно вважаю, що знання РСУБД на рівні SQL абсолютно не достатньо, щоб вважати себе професійним розробником ПЗ. Професіонал повинен знати не тільки свій код, але і приблизний пристрій сусідів по стеку, тобто 3rd party систем, які він використовує бази даних, фреймворків, мережевих протоколів, файлових систем. Без цього розробник вироджується до кодера або оператора ЕОМ, і по справжньому складні масштабні завдання стає марним.
Будь ласка, будьте професіоналами.

UPD. Незважаючи на це післямова, стаття, насправді, про JOIN'и.

Додаткові матеріали


Disclaimer: взагалі-то, я обіцяв ще одну статтю про Scalding, але попередня не викликала великого інтересу у публіки. З-за цього тему вирішено було змінити.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.