Comments 12
Я, конечно, эксперементировал с индексами. Но предпочел не включать их в статью. В случае Nested Loop индекс даст прирост производительности на порядок. Он так и называется Index Nested Loop — когда для вложенного цикла используется индекс. Вообще вариаций у Nested Loop много — еще одна Block nested loop.
В случае с Hash Join прирост не будет столь большим… но проще поэксперементировать. Исходники я оставил, если у вас есть Postgre — дело одной минуты. Не более.
Статья называется «Как реляционная СУБД делает JOIN», и логичный, очевидный и правильный случай, когда есть индекс, почему-то не рассмотрен.
Индекс это и есть сортировка. Планировщик запросов сам разрулит, будет ли он использовать готовый индекс, или отсортирует сам. Как говорит документация того же Postgres: "The required sorting might be achieved either by an explicit sort step, or by scanning the relation in the proper order using an index on the join key".
Приведите пример индекса без сортировки? Понятно, что реализация процесса в СУБД нагружена спецификой вроде page split, fill factor и т.п., но по сути — это сортировка. Откройте исходники того же Postgres и посмотрите, скажем, как делается ребилд.
А про разницу в плане количества дисковых операций я уже сказал. Планировщик запроса лучше вас решит, будет он использовать индекс или нет. Если у вас в базе пока только десять записей, он не станет делать лишние IO и тащить страницы с индексами. А если у вас их биллионы, то возможно вы уже давно переехали на колумнар и индекса вообще нет, а сортировка есть. В одном случае это B-tree, в другом — BRIN. Вы просто пытаетесь заменить абстракцию (СУБД сортирует и может сделать это множеством способов, включая использование имеющегося индекса), отдельно взятой реализацией. Это не верно, хотя бы согласно принципу DIP.
В настоящих реляционках у Nested loops обычно сложность O(N). Допустим мы соединяем таблицу orders и таблицу customers, и передаем список order_id. Пусть у нас достаточно большие таблицы, но не гигантские. Тогда нам на каждый order_id надо затратить три логических чтения блоков индекса (его высота), и одно логическое чтение блока таблицы. Потом столько же для customer_id, который мы взяли в таблице orders. Итого 8 логических чтений. А если нам на вход дали 100 order_id, то у нас будет 800 логических чтений. Строго линейная зависимость.
Неплохо было бы упомянуть, что Hash Join и Merge Join используются только для соединений с условием равенства (a.col1 = b.col2). Иначе только Nested Loops, он универсальный и годится для любых условий.
Как реляционная СУБД делает JOIN?