Oracle nested loops outer что значит
For an example, take 2 tables which have to be joined, say “Parent” table & “Child” table [I have taken these table names, only to discuss this topic in an easy way].
If Child table is outer joined with Parent table, then you can say, the matching records from both these tables will be retrieved and then the records which are available only in Parent table will also be retrieved though the corresponding matching records are not available in Child table. This is called outer join. [in natural or equi-join, only the matching records from both the tables will be retrieved.]
- · Nested loop outer join
- · Hash outer join
- · Sort merge outer join
To perform this nested loop outer join, Oracle follows these steps (assume, child table has to be outer-joined with parent table):
- 1. The optimizer chooses parent table as the outer table, or the driving table. Child table is chosen as the inner table (or the driven table).
- 2. For each row in the driving table, if a matching record exists in the driven table, columns (mentioned in the query) from both the tables will be returned .
- 3. If a matching record doesn’t exist in the driven table, columns from parent table alone will be returned and NULL will be returned in the places of child table’s columns mentioned in the query.
As you aware, in the nested loop equi-join, deciding which table is going to be the driving table is the deciding factor. Generally, the smallest of the two tables will be considered as the driving table so that cost will be low. [cost will be low because only minimal number of looping has to be done]. However, in this nested loop outer join, this decision making process becomes immaterial since Parent table will be chosen as the driving table by default irrespective of whether it is a small or big table. Reason is, joining condition determines which table is going to be the driving table in this nested loop outer join instead of cost which is the metric used to identify the driving table in the nested loop equi-join.
- · IF (a matching record from the driven table is available) THEN
- · ELSE (a matching record from the driven table is not available)
Ø Output this unmatched driving table’s record anyway and display NULL for the driven table’s columns mentioned in the query;
· This is very successful when the parent table is smaller, child table is bigger and child table is outer-joined with parent table
· If your requirement is to see the initial matching records (though outer-join is mentioned) as quick as possible, this is the best methodology to rely on. Reason is, as per the logic, though it is kinda having the iterative structure, the matching records would be displayed in each iteration.
· If parent table is small, then looping has to be done for minimal number of times and this technique will work efficiently.
· When this is opted for joining 2 big tables, you may see the initial matching records very fast but it would take a lot of time to display the final matching records.
· This is very resource intense process (especially CPU is utilized a lot) since it has the iterative structure in the process
How to verify whether Oracle follows nested loop outer join or not while executing the sql query. If a query follows this, then you will find similar execution plan like this,
In the explain plan, whenever it chooses this methodology, it displays the keyword [NESTED LOOPS (OUTER)] in the operation column. Whichever the table name that is getting displayed immediately after this word is nothing but the driving table and that’s why you will find parent table’s name in that position followed by child table’s name.
Читает индекс целиком (все строки) в порядке, представленном индексом. В зависимости от различной системной статистики СУБД может выполнять эту операцию, если нужны все строки в порядке индекса, например, из-за соответствующего предложения ORDER BY. Вместо этого оптимизатор может также использовать операцию Index Fast Full Scan и выполнить дополнительную операцию сортировки.
Index Fast Full Scan
Читает индекс целиком (все строки) в порядке, хранящемся на диске. Эта операция обычно выполняется вместо полного сканирования таблицы, если в индексе доступны все необходимые столбцы. Подобно операции TABLE ACCESS FULL, INDEX FAST FULL SCAN может извлечь выгоду из многоблочных операций чтения.
Union-All
Выполняет операцию объединения всех записей между двумя таблицами. Дублирующиеся строки не удаляются.
Дополнительные материалы
- Роскошная статья про устройство РСУБД
- Роскошная книга про алгоритмы. Полезно полистать перед собеседованием.
Disclaimer: вообще-то, я обещал еще одну статью про Scalding, но предыдущая не вызвала большого интереса у публики. Из-за этого тему решено было сменить.
В предыдущих постах этой серии я писал о том, как интерпретировать отдельно взятую строку в выводе анализа explain, его структуру, а также описал базовые операции получения данных (узлы дерева explain).
Сегодня мы перейдем к более сложным операциям.
Function scan
По большому счету, это так просто, что нет особой необходимости что-то объяснять. Но так как эта операция будет использоваться в следующих примерах, я всё же напишу о ней немного.
Function Scan – очень простой узел. Он запускает функцию, которая возвращает набор записей (recordset), – вот и всё. Он не будет запускать функции на подобие “lower()", а только те, которые потенциально вернут множество строк или столбцов. Когда функция вернет строки, они будут переданы в тот узел, который находится на уровень выше Function Scan в дереве плана, или клиенту, если Function Scan является корневым узлом.
Единственная дополнительная логика, которая здесь может возникнуть – это способность фильтровать полученные строки, как здесь:
Думаю, это довольно просто понять – sort берет выбранные записи и возвращает их отсортированными определенным образом.
Хоть это и просто, внутри скрывается интересная логика. Для начала, если память, требующаяся для сортировки, будет больше, чем значение work_mem, то произойдет переключение на дисковую сортировку:
Обратите внимание на изменение Sort Method в примере выше.
В таких случаях Постгрес использует временные файлы, которые хранятся в директории $PGDATA/base/pgsql_tmp/. Конечно же, они будут удалены, как только в них исчезнет необходимость.
Ещё одно дополнительное свойство заключается в том, что Sort может менять свой метод работы, если вызывается операцией Limit, как вот здесь:
Обычно для сортировки выбранного набора данных вам нужно обработать его целиком. Но Постгрес знает, что если вам нужно лишь небольшое количество строк, ему не надо сортировать весь набор данных, достаточно получить только первые значения.
В нотации Big O общая сортировка имеет сложность O(m * log(m)), но Top-N имеет сложность O(m * log(n)), где m – число строк в таблице, а n – количество возвращаемых строк. Важно знать, что этот способ сортировки также использует гораздо меньше памяти (в конце концов, ему не нужно собирать весь набор данных из отсортированных строк, пары строк вполне достаточно), так что он с меньшей вероятностью будет использовать медленный диск для временных файлов.
Limit
Я использовал limit неоднократно, потому что он очень прост, но всё же давайте его подробно обсудим. Операция limit запускает свою субоперацию и возвращает только первые N строк из того, что вернула субоперация. Обычно после этого она останавливает субоперацию, но в некоторых случаях (например, вызов функции pl/PgSQL), субоперация уже завершила свою работу к тому моменту, когда она вернула первую строку.
Как вы видите, использование лимита во втором случае привело к тому, что вложенная операция Seq Scan завершила свою работу сразу после нахождения двух строк.
HashAggregate
Эта операция в основном применяется в случаях, когда вы используете GROUP BY и какие-нибудь агрегаты, вроде sum(), avg(), min(), max() и других.
HashAggregate делает следующее: для каждой строки, которую получает, она находит «ключ» GROUP BY (в данном случае – relkind). Затем в хэше (ассоциативном массиве, словаре) помещает выбранную строку в корзину, обозначенную данным ключом.
После того как все строки были обработаны, она сканирует хэш и возвращает по одной строке для каждого значения ключа, совершая уместные расчёты по необходимости (sum, min, avg и так далее).
Важно понимать, что HashAggregate должен просканировать все строки прежде, чем сможет вернуть хотя бы одну.
Если вы это поняли, то, наверное, видите потенциальную проблему: что делать в ситуации, когда у вас миллионы строк? Хэш будет слишком большим, чтобы уместиться в памяти. И здесь мы снова будем использовать work_mem. Если сгенерированный хэш слишком велик, он будет «сливаться» на диск (опять в $PGDATA/base/pgsql_tmp).
Это значит, что если в плане есть и HashAggregate, и Sort, мы можем использовать вплоть до 2 * work_mem. Такой план легко получить:
В реальности один запрос может использовать work_mem много раз, поскольку work_mem – это ограничение для операции. Поэтому если в запросе применяется 1000 HashAggregate’ов и Sort’ов (и других операций, использующих work_mem), общее потребление памяти может быть очень высоким.
Hash Join / Hash
Поскольку мы только что обсуждали HashAggregate, будет логично перейти к Hash Join.
Эта операция, в отличие от предыдущей, имеет две субоперации. Одна из них всегда “Hash", а вторая – что-нибудь другое.
Как понятно из названия, Hash Join используется для объединения двух наборов записей. Например, как здесь:
Это работает следующим образом: сначала Hash Join вызывает “Hash", который в свою очередь вызывает что-нибудь ещё (в нашем случае – Seq Scan по pg_namespace). Потом Hash создает в памяти (или на диске – в зависимости от размера) хэш/ассоциативный массив/словарь со строками из источника, хэшированными с помощью того, что используется для объединения данных (в нашем случае это столбец OID в pg_namespace).
Конечно, у вас может быть много строк для указанного ключа join (не в этом случае, поскольку я объединяю с помощью первичного ключа, но в целом вполне вероятно, что у вас будет множество строк для одного хэш-ключа).
В нотации Perl, то вывод Hash будет примерно таким:
- Проверяет, есть ли ключ join (pg_class.relnamespace в данном случае) в хэше, возвращенном операцией Hash.
- Если нет, данная строка из субоперации игнорируется (не будет возвращена).
- Если ключ существует, Hash Join берет строки из хэша и, основываясь на этой строке, с одной стороны, и всех строках хэша, с другой стороны, генерирует вывод строк.
Поскольку оба субсканирования могут быть операциями любого типа, они могут оказаться фильтрами, сканированием индексов или тем, что вы себе можете вообразить.
Последнее, о чем стоит упомянуть в связи с Hash Join/Hash – это то, что операция Hash, так же, как Sort и HashAggregate будет использовать память вплоть до work_mem.
Hash Join / Hash
Поскольку мы говорим об объединениях, стоит обсудить Nested Loop. Пример:
Это очень интересный план, потому что он может выполнять выбранные операции неоднократно.
Так же, как и у Hash Join, у Nested Loop есть двое «потомков». Сначала она запускает “Seq Scan" (в нашем примере, сначала она запускает первый узел), а затем, для каждой возвращенной строки (всего 2 строки в нашем примере), она запускает вторую операцию (Index Scan по pg_attribute в нашем случае).
Вы могли заметить, что у Index Scan в фактической метаинформации стоит “loops=2". Это значит, что данная операция запускалась дважды, и другие значения (строки, время) являются средними показателями для всех запусков.
- Nested Loop запускает первую сторону объединения единожды. Давайте назовем её “A".
- Для каждой строки из “A", запускается вторая операция (назовём её “B").
- Если “B" не вернула ни одной строки, данные из “A" игнорируются.
- Если “B" вернула строки, для каждой возвращаемой строки Nested Loop возвращает новую строку, основанную на текущих строках из A и B.
Merge Join
Еще один метод объединения данных называется Merge Join. Он используется, если объединяемые наборы данных отсортированы (или могут быть отсортированы с небольшими затратами) с помощью ключа join.
У меня нет готового наглядного примера, поэтому я создам его искусственно с помощью подзапросов, которые сортируют данные перед объединением:
Merge Join, как и другие объединения, запускает две субоперации (Sort и Materialize в данном случае). Так как они обе возвращают данные отсортированными и порядок сортировки такой же, как в операции объединения, Pg может сканировать оба набора данных, возвращенных субоперациями, одновременно и просто проверить, совпадают ли идентификаторы.
- если объединяемый столбец справа такой же, как объединяемый столбец слева:
- возвращаем новую объединённую строку, основанную на текущих строках справа и слева;
- берем следующую строку справа (или слева, если справа больше нет строк);
- возвращаемся к шагу 1;
- берем следующую строку справа (если строк больше нет, заканчиваем обработку);
- возвращаемся к шагу 1;
- берем следующую строку слева (если строк больше нет, заканчиваем обработку);
- возвращаемся к шагу 1.
- 44,721 плана, содержащих операцию “Nested Loop";
- 34,305 плана с “Hash Join";
- всего 8,889 плана, использующих “Merge Join".
Модификаторы Hash Join / Nested Loop / Merge Join
Во всех примерах выше я продемонстрировал, что операция Join возвращает строку только когда получает строки с обеих сторон объединения.
Но так бывает не всегда. У нас могут быть левые, правые и полные (LEFT/RIGHT/FULL OUTER JOIN) внешние объединения, а также так называемые анти-объединения (anti-joins).
- Hash Left Join,
- Hash Right Join,
- Merge Left Join,
- Merge Right Join,
- Nested Loop Left Join.
Во всех этих случаях логика проста: у нас есть две стороны объединения – левая и правая. И когда сторона упоминается в объединении, оно возвращает новую строку, даже если на другой стороне нет соответствующих строк.
Так происходит с запросами вроде этого:
Вся остальная информация для Hash Join/Merge Join и Nested Loop одинакова, есть только небольшое изменение в логике того, когда генерируется вывод строки.
Вся обработка происходит так же, как в предыдущих примерах.- Hash Anti Join,
- Merge Anti Join,
- Nested Loop Anti Join.
Как в этом примере:
Здесь Pg выполнил правую сторону (Index Scan по pg_attribute), захэшировал её, а затем выполнил левую сторону (Seq Scan по pg_class), возвращая только те строки, где не было вхождений в Hash для данного pg_class.oid.Materialize
Эта операция уже была продемонстрирована в примере для Merge Join, но она может быть полезна и в других случаях.
У psql есть множество внутренних команд. Одна из них — \dTS, которая составляет список всех системных типов данных. Внутренне \dTS запускает этот запрос:
План у него такой:Правая часть объединения – Seq Scan по pg_namespace. Так что, теоретически, Постгрес должен выполнить последовательное сканирование по pg_namespace 87 раз. Если учесть, что единичное последовательное сканирование этой таблицы занимает 0.003мс, мы можем ожидать, что общее время будет составлять ~ 0.25мс.
Но Постгрес поступает умнее. Он понимает, что будет менее затратно просканировать таблицу один раз и построить в памяти образ всех её строк. Тогда в следующий раз не нужно будет сканировать таблицу, проверять информацию о видимости, парсить страницы данных. Он просто возьмет данные из памяти.
Благодаря этому общее время на всё (однократное чтение таблицы, подготовка образа данных в памяти и сканирование этого образа 87 раз) составило 0.087мс.
Вы можете сказать: «Хорошо, но почему merge join использовал materialize раньше, он ведь просто выполнял одно сканирование?» Давайте вспомним план:
Да, он запускался всего один раз. Проблема в том, что источник данных для Merge Join должен отвечать нескольким критериям. Некоторые из них очевидны (данные должны быть отсортированы), а другие менее очевидны, поскольку являются более техническими (данные должны быть просматриваемыми вперед и назад).Из-за этих не слишком очевидных критериев Постгресу иногда приходится применять Materialize к данным, приходящим из источника (в нашем случае из Index Scan), чтобы у него были все необходимые возможности, когда дело дойдет до их использования.
Короче говоря, Materialize получает данные из нижележащей операции и размещает их в памяти (или частично в памяти), чтобы ими можно было быстрее воспользоваться, или добавляет им дополнительные свойства, которые предыдущая операция не предоставляет.
На сегодня это всё. Я думал, что на этом закончу, но есть ещё много операций, которые стоит описать, так что в этой серии будет ещё как минимум два поста (оставшиеся операции и статистическая информация).
Table Access By Index ROWID
Извлекает строку из таблицы, используя ROWID, полученный из предыдущего поиска по индексу.
Merge Join
А теперь представим, что данные в обоих списках заранее отсортированы, например, по возрастанию. Так бывает, если у нас были индексы по этим таблицам, или же если мы отсортировали данные на предыдущих стадиях запроса. Как вы наверняка помните, два отсортированных списка можно склеить в один отсортированный за линейное время — именно на этом основан алгоритм сортировки слиянием. Здесь нам предстоит похожая задача, но вместо того, чтобы склеивать списки, мы будем искать в них общие элементы.
Итак, ставим по курсору в начало обоих списков. Если ключи под курсорами равны, записываем совпадение в результирующую таблицу. Если же нет, смотрим, под каким из курсоров ключ меньше. Двигаем курсор над меньшим ключом на один вперед, тем самым “догоняя” другой курсор.
Если данные отсортированы, то временная сложность алгоритма линейная O(M+N) и не требуется никакой дополнительной памяти. Если же данные не отсортированы, то нужно сначала их отсортировать. Из-за этого временная сложность возрастает до O(M log M + N log N), плюс появляются дополнительные требования к памяти.Постановка задачи
Людям, которые утверждают, что много и плотно работали с SQL, я задаю на собеседованиях вот такую задачу.
Есть SQL командаНужно выполнить то же самое на Java, т.е. реализовать метод
Я не прошу прям закодить реализацию, но жду хотя бы устного объяснения алгоритма.
Дополнительно я спрашиваю, что нужно изменить в сигнатуре и реализации, чтобы сделать вид, что мы работаем с индексами.
- Знать теорию полезно из чисто познавательных соображений.
- Если вы различаете типы джойнов, то план выполнения запроса, который получается командой EXPLAIN, больше не выглядит для вас как набор непонятных английских слов. Вы можете видеть в плане потенциально медленные места и оптимизировать запрос переписыванием или хинтами.
- В новомодных аналитических инструментах поверх Hadoop планировщик запросов или малость туповат (см. Cloudera Impala), или его вообще нет (см. Twitter Scalding, Spark RDD). В последнем случае приходится собирать запрос вручную из примитивных операций.
Наконец, есть риск, что однажды вы попадете на собеседование ко мне или к другому зануде.Но на самом деле, статья не про собеседования, а про операцию JOIN.
Hash Unique
Более эффективная реализация алгоритма сортировки и устранения дупликатов с использованием хэш-таблицы. Заменяет операцию Sort Unique в определенных обстоятельствах.
Count Stopkey
Прерывает выполение операций, когда было выбрано нужное количество строк.
Nested Loops
Соединение вложенными циклами объединяет две таблицы, выбирая результат из одной таблицы и запрашивая другую таблицу для каждой строки из первой. Встречается очень часто. Выполняет довольно эффективное соединение относительно небольших наборов данных. Соединение вложенными циклами не требует сортировки входных данных.
Sort Unique
Сортирует строки и устраняет дупликаты.
Merge Join
Соединение слиянием объединяет два отсортированных списка. Обе стороны объединения должны быть предварительно отсортированы.
Sort Order By
Сортирует результат в соответствии с предложением ORDER BY. Эта операция требует больших объемов памяти для материализации промежуточного результата.
Nested Loop
Самая простая идея, которая приходит на ум. Бежим в цикле по клиентам и во вложенном цикле бежим по всем посещениям. Проверяем все условия и если находим совпадение - добавляем сумму затрат этого визита в итоговый результат.
Эта идея анимирована ниже:
Алгоритм очень простой, не потребляет дополнительной памяти. Но затратность его O(N²), что будет сказываться на большом числе элементов - чем их больше, тем больше телодвижений необходимо совершить.
Для того, чтобы оценить скорость его работы мы создадим тестовый набор данных с помощью следующего SQL скрипта:
Все на том же компьютере получилось порядка 2.1 миллисекунды на все. И кода заметно меньше. Т.е. в 10 раз быстрее самого метода, не считая логики по извлечению данных из БД и их материализации на стороне приложения.
Hash Join
Если размер одной из таблиц позволяет засунуть ее целиком в память, значит, на ее основе можно сделать хеш-таблицу и быстренько искать в ней нужные ключи. Проговорим чуть подробнее.
Проверим размер обоих списков. Возьмем меньший из списков, прочтем его полностью и загрузим в память, построив HashMap. Теперь вернемся к большему списку и пойдем по нему курсором с начала. Для каждого ключа проверим, нет ли такого же в хеш-таблице. Если есть — запишем совпадение в результирующую таблицу.
Временная сложность этого алгоритма падает до линейной O(N+M), но требуется дополнительная память.
Что важно, во времена динозавров считалось, что в память нужно загрузить правую таблицу, а итерироваться по левой. У нормальных РСУБД сейчас есть статистика cardinality, и они сами определяют порядок джойна, но если по какой-то причине статистика недоступна, то в память грузится именно правая таблица. Это важно помнить при работе с молодыми корявыми инструментами типа Cloudera Impala.Морализаторское послесловие
Если вы дочитали досюда, значит, статья показалась вам интересной. А значит, вы простите мне небольшую порцию нравоучений.
Я действительно считаю, что знания РСУБД на уровне SQL абсолютно не достаточно, чтобы считать себя профессиональным разработчиком ПО. Профессионал должен знать не только свой код, но и примерное устройство соседей по стеку, т.е. 3rd-party систем, которые он использует — баз данных, фреймворков, сетевых протоколов, файловых систем. Без этого разработчик вырождается до кодера или оператора ЭВМ, и в по настоящему сложных масштабных задачах становится бесполезен.
UPD. Несмотря на это послесловие, статья, на самом деле, про JOIN'ы.
Nested Loops Join
Самый базовый алгоритм объединения двух списков сейчас проходят в школах. Суть очень простая — для каждого элемента первого списка пройдемся по всем элементам второго списка; если ключи элементов вдруг оказались равны — запишем совпадение в результирующую таблицу. Для реализации этого алгоритма достаточно двух вложенных циклов, именно поэтому он так и называется.
Основной плюс этого метода — полное безразличие к входным данным. Алгоритм работает для любых двух таблиц, не требует никаких индексов и перекладываний данных в памяти, а также прост в реализации. На практике это означает, что достаточно просто бежать по диску двумя курсорами и периодически выплёвывать в сокет совпадения.Однако ж, фатальный минус алгоритма — высокая временная сложность O(N*M) (квадратичная асимптотика, если вы понимаете, о чем я). Например, для джойна пары небольших таблиц в 100к и 500к записей потребуется сделать аж 100.000 * 500.000 = 50.000.000.000 (50 млрд) операций сравнения. Запросы с таким джойном будут выполняться невежливо долго, часто именно они — причина беспощадных тормозов кривеньких самописных CMS’ок.
Современные РСУБД используют nested loops join в самых безнадежных случаях, когда не удается применить никакую оптимизацию.
UPD. zhekappp и potapuff поправляют, что nested loops эффективен для малого числа строк, когда разворачивать какую-либо оптимизацию выйдет дороже, чем просто пробежаться вложенным циклом. Есть класс систем, для которых это актуально.
Temp Table Generation/Transformation
Создает/преобразует временную таблицу. Используется в специфичных для Oracle преобразованиях типа Star.
С SQL работают почти все, но даже опытные разработчики иногда не могут ответить на простой вопрос. Каким образом СУБД выполняет самый обычный INNER JOIN?
Table Access Full
Полное сканирование таблицы. Читает всю таблицу (все строки и столбцы), в порядке, хранящемся на диске. Хотя многоблочные операции чтения значительно повышают скорость сканирования полной таблицы, это все еще одна из самых дорогих операций. Помимо высоких затрат времени ввода-вывода, полное сканирование таблицы должно проверять все строки таблицы, что также занимает значительное количество процессорного времени.
Hash Join
Хеш-соединение загружает записи-кандидаты с одной стороны соединения в хеш-таблицу, которая затем проверяется для каждой строки с другой стороны соединения. Операция используется всегда, когда невозможно применить другие виды соединения: если соединяемые наборы данных достаточно велики и/или наборы данных не упорядочены по столбцам соединения.
Sort Group By Nosort
Агрегирует предварительно отсортированный набор записей в соответствии с предложением GROUP BY. Эта операция не буферизует промежуточный результат.
Sort Aggregate
Вычисляет суммарные итоги с использованием агрегатных функций SUM, COUNT, MIN, MAX, AVG и пр.
Hash Join
Этот алгоритм подходит для больших массивов данных. Его идея проста. Для каждого из списков считается хэш ключа, далее этот хэш используется для того, чтобы выполнить сам Join. Детально можно посмотреть в видео:
Sort Join
Сортирует набор записей в столбце соединения. Используется в сочетании с операцией Merge Join для выполнения сортировки соединением слияния.
Merge Join
Разница в скорости работы в 20 раз наталкивает на размышления. Скорее всего Nested Loop не очень нам подходити мы должны найти что-то получше. И есть такой алгоритм… Называется Merge Join или Sort-Merge Join. Общая суть в том, что мы сортируем два списка по ключу на основе которого происходит соединение. И делаем проход всего в один цикл. Инкрементируем индекс и если значения в двух списках совпали - добавляем их в результат. Если в левом списке идентификатор больше, чем в правом - увеличиваем индекс массива только для правой части. Если, наоборот, в левом списке идентификатор меньше, то увеличиваем индекс левого массива. Затратность такого алгоритма O(N*log(N)).
Intersection
Выполняет операцию пересечения между двумя источниками.
Sort Group By
Сортирует набор записей по столбцам GROUP BY и агрегирует отсортированный результат на втором этапе. Эта операция требует больших объемов памяти для материализации промежуточного результата.
Hash Group By
Группирует результат, используя хеш-таблицу. Эта операция требует больших объемов памяти для материализации промежуточного набора записей. Вывод не упорядочен каким-либо значимым образом.
Filter
Применяет фильтр к набору строк.
Создает промежуточное представление данных.
Динамический выбор алгоритма
Отлично! Похоже мы нашли универсальный алгоритм, который самый быстрый. Нужно просто использовать его всегда и не беспокоиться более об этом вопросе. Но если мы учтем еще и расход памяти все станет немного сложнее. Для Nested Loop - память не нужна, Merge Join - нужна только для сортировки (если она будет). Для Hash Join - нужна оперативная память.
Оказывается расход памяти - это еще не все. В зависимости от общего числа элементов в массивах скорость работы разных алгоритмов ведет себя по-разному. Проверим для меньшего числа элементов (P, V) равному (50, 100). И ситуация переворачивается на диаметрально противоположную: Nested Loop самый быстрый - 2.202 микросекунды, Merge Join - 4.715 микросекунды, Hash Join - 7.638 микросекунды. Зависимость скорости работы каждого алгоритма можно представить таким графиком:
Я часто собеседую разработчиков и часто задаю им простой, как кувалда, вопрос — как внутри работает JOIN в SQL? В ответ я обычно слышу бессвязное мычание про волшебные деревья и индексы, которые быстрее. Когда-то мне казалось, что каждый
программистспециалист должен знать то, с чем работает. Впоследствии жизнь объяснила мне, что это не так. Но мне все еще не понятно, как можно годами теребить базёнку , даже не догадываясь, а что там у нее «под капотом»?Давайте проведем ликбез и вместе посмотрим, как же работают эти джойны , и даже сами реализуем парочку алгоритмов.
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 ситуация аналогичная, причем все настолько просто, что я даже осилил это закодить:
Работа с несколькими коллекциями
В базе данных (в дальнейшем мы будем использовать PostgreSQL) для двух этих сущностей есть две таблицы с аналогичными полями:
Пусть наша задача сводится к написанию простейшего бизнес-правила - найти общую сумму выручки за 2020 год и ранее, которую принесли клиенты, находящиеся сейчас в активном статусе. Как можно реализовать решение такой простой задачи?
Load As Select
Прямая загрузка с использованием оператора SELECT в качестве источника.
Читайте также: