Что такое hash join oracle
Hash join - это алгоритм обработки базы данных для объединений в несколько таблиц. Для объединений в несколько таблиц существует два наиболее часто используемых метода: sort merge-join и вложенный цикл. Чтобы более четко представить сценарии использования хеш-соединения и почему вводится такой алгоритм соединения, здесь также кратко представлены два метода соединения, упомянутых выше.
Какое понятие является методом подключения, или почему у нас есть и есть несколько, для тех, кто не понимает базу данных, это может быть началом сомнений. Проще говоря, мы храним данные в разных таблицах, и разные таблицы имеют свою собственную структуру таблиц. Разные таблицы могут быть связаны. В большинстве практических случаев нам не нужна только одна таблица информации. Например, вам нужно найти учеников в Ханчжоу из таблицы классов, а затем использовать эту информацию для получения их математических оценок в таблице оценок. Если нет соединения с несколькими таблицами, вы можете только вручную запросить информацию в первой таблице как первую. Получая информацию из двух таблиц для запроса окончательного результата, можно представить, насколько это будет громоздко.
Для нескольких распространенных баз данных, таких как oracle, postgresql, все они поддерживают hash-join, mysql не поддерживает. В этом отношении oracle и pg работают относительно хорошо, реализация самого hash-join не очень сложна, но требует реализации оптимизатора для взаимодействия, чтобы максимизировать его преимущества, я думаю, что это самое сложное место.
Метод запроса многостолового соединения делится на следующие типы: внутреннее соединение, внешнее соединение и кросс-соединение. Внешние соединения делятся на: левое внешнее соединение, правое внешнее соединение и полное внешнее соединение. Для разных методов запросов использование одного и того же алгоритма соединения также будет сопряжено с разными затратами. Это тесно связано с методом его реализации. Необходимо рассмотреть, как реализовать разные методы запроса. Определенный используемый метод соединения определяется оптимизатором. В зависимости от измерения стоимости, расчет стоимости нескольких методов подключения будет кратко представлен позже. На самом деле, есть много мест, где можно рассмотреть и реализовать хеш-джойн, например, как справляться с серьезным перекосом данных, как справляться с внутренним хранилищем, как справляться с конфликтами и т. Д., Они не являются предметом данной статьи, более подробно не рассматриваются Я могу поговорить еще об одном.
nested loop join
Соединение с вложенным циклом - более общий метод соединения. Он делится на внутреннюю и внешнюю таблицы. Каждая строка данных, отсканированных во внешней таблице, должна быть найдена во внутренней таблице. Сложность без индекса составляет O (N * M), Эта сложность очень невыгодна для больших наборов данных, и, вообще говоря, индексы будут использоваться для повышения производительности.
Объединение слиянием должно сначала отсортировать две таблицы в соответствии со связанными полями и взять строку данных из двух таблиц для сопоставления, при необходимости поместить их в набор результатов, если не совпадает, выбросить меньшую строку и продолжить сопоставление с другой таблицей. Одна строка обрабатывается по очереди, пока не будут взяты данные двух таблиц. Большая часть стоимости объединения слиянием тратится на сортировку, и это также является основной причиной, по которой оно хуже, чем хеш-соединение при тех же условиях.
Partitioned Hash Joins¶
For two tables that are equijoined and both partitioned identically, Oracle does a full partition-wise join, which shows up as a PARTITION HASH parent operation to the HASH JOIN in the execution plan. Similarly it can pop up in a parallel SQL statement as PX PARTITION HASH . Each parallel query server reads data from a particular partition of the first table and joins it with the appropriate rows from the corresponding partition of the second table. Query servers have no need to communicate to one another, which is ideal. The only downside is if there is at least one partition that is significantly larger than all the others, as this may affect the balancing of the load.
When only one table is partitioned, Oracle can go with a (parallel) partial partition-wise join. It (re)partitions the other table on the fly based on the partitioning scheme of the reference table. Once the partitioning is out of the way, the database proceeds as it does with a full partition-wise join.
It is generally recommended to use hash instead of range partitioning for partition-wise joins to be effective, mainly because of possible data skew that leads to some partitions being larger than others. Furthermore, the number of partitions in relation to the DOP is relevant to the performance. Ideally, the number of partitions is a multiple of the number of query servers.
Both hash and sort-merge joins are possible for full partition-wise joins. More details can be found in the excellent book Expert Oracle SQL.
Nested Loop
Самая простая идея, которая приходит на ум. Бежим в цикле по клиентам и во вложенном цикле бежим по всем посещениям. Проверяем все условия и если находим совпадение - добавляем сумму затрат этого визита в итоговый результат.
Эта идея анимирована ниже:
Алгоритм очень простой, не потребляет дополнительной памяти. Но затратность его O(N²), что будет сказываться на большом числе элементов - чем их больше, тем больше телодвижений необходимо совершить.
Для того, чтобы оценить скорость его работы мы создадим тестовый набор данных с помощью следующего SQL скрипта:
Все на том же компьютере получилось порядка 2.1 миллисекунды на все. И кода заметно меньше. Т.е. в 10 раз быстрее самого метода, не считая логики по извлечению данных из БД и их материализации на стороне приложения.
2. Реализация хеш-соединения
Реализация хеш-соединения разделена на таблицу построения, которая представляет собой небольшую таблицу и таблицу зондов, используемые для построения хэш-карты.Вначале данные небольшой таблицы считываются последовательно, и для каждой строки данных в соответствии с условиями соединения генерируется кортеж в хэш-карте. Кэшируется в памяти, если внутренней памяти недостаточно, выведите дамп на внешнюю память. Сканируйте таблицу зондов по очереди, чтобы получить каждую строку данных, чтобы сгенерировать карту хеш-ключей в соответствии с условием соединения. Соответствующий кортеж в хэш-карте, строка, соответствующая кортежу, и строка таблицы зондов имеют одинаковый хэш-ключ, тогда нет уверенности в том, что эти две строки Данные, которые удовлетворяют условию, должны пройти через условие соединения и снова фильтроваться, а набор данных, который удовлетворяет условию, возвращает необходимый столбец проекции.
Hash объединить несколько деталей
1. Реализация хеш-соединения сама по себе не должна определять, является ли она маленькой таблицей. Оптимизатор уже определил порядок соединения таблицы при создании плана выполнения. Чтобы создать хеш-таблицу с левой таблицей в качестве маленькой таблицы, соответствующая модель затрат будет левой таблицей. Стоимость получается в виде небольшой таблицы, так что путь, сгенерированный в соответствии со стоимостью, соответствует требованиям реализации.
2. Размер хеш-таблицы и количество сегментов, которые должны быть выделены. Это нужно сделать с самого начала. Сколько выделения является проблемой. Слишком большое выделение приведет к потере памяти. Слишком маленькое выделение приведет к слишком малому количеству сегментов и слишком длинной открытой цепочке. Производительность ухудшается. Как только здесь будет превышен лимит памяти, будет рассмотрен дамп во внешнее хранилище. Различные базы данных имеют свою собственную реализацию.
3. Как хешировать данные, разные базы данных имеют свои собственные способы, и разные методы хеширования также будут оказывать определенное влияние на производительность.
В предыдущих постах этой серии я писал о том, как интерпретировать отдельно взятую строку в выводе анализа 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 получает данные из нижележащей операции и размещает их в памяти (или частично в памяти), чтобы ими можно было быстрее воспользоваться, или добавляет им дополнительные свойства, которые предыдущая операция не предоставляет.
На сегодня это всё. Я думал, что на этом закончу, но есть ещё много операций, которые стоит описать, так что в этой серии будет ещё как минимум два поста (оставшиеся операции и статистическая информация).
С SQL работают почти все, но даже опытные разработчики иногда не могут ответить на простой вопрос. Каким образом СУБД выполняет самый обычный INNER JOIN?
1. Базовые знания
1. Первый шаг, он должен пройти лексический и грамматический анализ, вывод этой части - грамматическое дерево с узлами токена.
Грамматический анализ, как следует из названия, эта часть является только анализом грамматического уровня. Оператор SQL строки обрабатывается в дерево узлов со структурой прототипа. Каждый узел имеет свой собственный специальный логотип, но этот узел не анализируется и не обрабатывается. Специфическое значение и ценность.
2. Второй шаг - это семантический анализ и переписывание.
Разные процессы перезаписи могут иметь разные базы данных, некоторые могут быть объединены с процессом выполнения логики, а некоторые могут быть отдельными.
Форма дерева после этого шага, как правило, соответствует дереву синтаксического анализа, но узлы в это время несут определенную информацию. Возьмем выражение, где в качестве примера каждый узел этого инфиксного выражения. Точка имеет свой собственный тип и определенную информацию, и ей все равно, какое значение. После завершения этого шага начинается процесс перезаписи. Перезапись - это логический метод оптимизации, который делает некоторые сложные операторы SQL проще или больше в соответствии с базой данных. Поток процесса.
3. Оптимизатор обработки
Обработка оптимизатора является относительно сложной, и это также самое трудное место модуля sql. Оптимизация бесконечна, поэтому у оптимизатора нет оптимального, а только лучше. Оптимизатор должен учитывать все аспекты факторов, не только быть очень универсальными, но и обеспечивать сильную способность и правильность оптимизации.
Наиболее важной ролью оптимизатора является выбор пути: для соединений с несколькими таблицами, как определить порядок и метод соединения для соединений с таблицами, разные базы данных имеют разные методы обработки, pg поддерживает алгоритмы динамического программирования, а генетические алгоритмы используются, когда таблиц слишком много. , Определение пути зависит от реализации модели затрат. Модель затрат содержит некоторую статистическую информацию, такую как максимальные, минимальные значения, значения NDV и DISTINCT столбца. Через эту информацию можно рассчитать коэффициент выбора для дальнейшего расчета стоимости.
Возвращаясь к тексту, здесь определяется, какой метод подключения использовать. Для хеш-соединения требуется таблица размеров, поэтому сформированный здесь план отличается от t1-t2 или t2-t1. Каждый метод подключения имеет свой собственный Метод расчета стоимости.
Оценка стоимости хеш-соединения:
COST = BUILD_COST + M_SCAN_COST + JOIN_CONDITION_COST + FILTER_COST
Проще говоря, стоимость хеш-соединения заключается в основном в создании хеш-таблицы, сканировании таблицы M, соединении условного соединения и фильтрации фильтрации, для S-таблицы и М-таблицы нужно сканировать только один раз, фильтрация фильтра относится к t1.c2> t2. Условная фильтрация, такая как c2, для условий, таких как t1.c1> 1, которые включают только одну таблицу, будет передана и отфильтрована до установления соединения.
После обработки оптимизатором будет сгенерировано дерево плана выполнения, и реальный процесс реализации будет рекурсивно обрабатывать данные снизу вверх в соответствии с данными операции процесса плана выполнения и возвращать данные.
Примеры
Следующие примеры используют эту схему:
Начнём с простого примера:
334 1 |--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]),RESIDUAL:([T2].[a]=[T1].[a]))
1000 1 |--Table Scan(OBJECT:([T1]))
10000 1 |--Table Scan(OBJECT:([T2]))
Обратите внимание, что у T2 строк в десять раз больше чем у T1, и поэтому оптимизатор использует T1 в качестве таблицы потока компоновки, а T2 в качестве таблицы пробного потока.
Теперь рассмотрим соединение трёх таблиц:
334 1 |--Hash Match(Inner Join, HASH:([T1].[b])=([T3].[a]),RESIDUAL:([T1].[b]=[T3].[a]))
334 1 |--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]),RESIDUAL:([T1].[a]=[T2].[a]))
1000 1 | |--Table Scan(OBJECT:([T1]))
10000 1 | |--Table Scan(OBJECT:([T2]))
100000 1 |--Table Scan(OBJECT:([T3]))
Обратите внимание, что оптимизатор выбрал план с густым слева деревом. Сначала соединяются две маленькие таблицы, T1 и T2. Результаты этого соединения выдаёт всего 334 строки, которые используются для формирования хеш-таблицы перед соединением с большой таблицей T3.
Теперь посмотрим, что случится, если добавить предикат, ограничивающий размер меньшей из двух таблиц (единственным условием для оптимизатора может быть: "T2.a < 100" from "T1.a < 100" and "T1.a = T2.a").
17 1 |--Hash Match(Inner Join, HASH:([T2].[a])=([T1].[a]),RESIDUAL:([T1].[a]=[T2].[a]))
50 1 |--Hash Match(Inner Join, HASH:([T1].[b])=([T3].[a]),RESIDUAL:([T1].[b]=[T3].[a]))
100000 1 |--Table Scan(OBJECT:([T3]))
На сей раз оптимизатор для плана выбрал густое справа дерево. T1 и T2 теперь настолько малы (34 и 50 строк), что лучше формировать хеш-таблицу по этим двум таблицам, а на стадии проб использовать большую таблицу T3, формируя хеш-таблицу на промежуточном уровне хэш-соединения.
Merge Join
Разница в скорости работы в 20 раз наталкивает на размышления. Скорее всего Nested Loop не очень нам подходити мы должны найти что-то получше. И есть такой алгоритм… Называется Merge Join или Sort-Merge Join. Общая суть в том, что мы сортируем два списка по ключу на основе которого происходит соединение. И делаем проход всего в один цикл. Инкрементируем индекс и если значения в двух списках совпали - добавляем их в результат. Если в левом списке идентификатор больше, чем в правом - увеличиваем индекс массива только для правой части. Если, наоборот, в левом списке идентификатор меньше, то увеличиваем индекс левого массива. Затратность такого алгоритма O(N*log(N)).
2. Принцип и реализация
Проще говоря, для двух таблиц, hash-join, даже если маленькая таблица (называемая S) в двух таблицах используется в качестве хэш-таблицы, а затем сканирует каждую строку данных в другой таблице (называемой M), используя полученные данные строки в соответствии с Условия соединения используются для отображения установленной хеш-таблицы Хеш-таблица помещается в память, чтобы можно было быстро получить соответствующие строки таблицы S и таблицы М.
Для случая, когда результирующий набор очень большой, объединение слиянием должно сортировать эффективность не очень высоко, а объединение с вложенным циклом - это метод запроса с вложенным циклом, несомненно, более непригоден для подключения больших наборов данных, а хеш-соединение является положительным Он был создан, чтобы иметь дело с этим сложным методом запроса, особенно в случае большой таблицы и маленькой таблицы, в основном нужно сканировать таблицу размеров только один раз, чтобы получить окончательный набор результатов.
Однако hash-join применим только к соединениям с равными значениями.Для соединений запросов, таких как>, =, по-прежнему необходим общий алгоритм соединения, такой как вложенный цикл. Если ключ подключения изначально заказан или должен быть отсортирован, то стоимость использования merge-join может быть меньше, чем hash-join, и merge-join будет иметь преимущество.
Ну, много глупостей, давайте поговорим о реализации, возьмем простую многостабильную SQL-инструкцию запроса, чтобы получить каштан: select * из t1 объединить t2 на t1.c1 = t2.c1, где t1.c2> t2. c2 и t1.c1> 1. Такой SQL входит в систему базы данных, как она обрабатывается и анализируется? sql: призрак знает, что я испытал. , ,
Hash Join
Этот алгоритм подходит для больших массивов данных. Его идея проста. Для каждого из списков считается хэш ключа, далее этот хэш используется для того, чтобы выполнить сам Join. Детально можно посмотреть в видео:
Работа с несколькими коллекциями
В базе данных (в дальнейшем мы будем использовать PostgreSQL) для двух этих сущностей есть две таблицы с аналогичными полями:
Пусть наша задача сводится к написанию простейшего бизнес-правила - найти общую сумму выручки за 2020 год и ранее, которую принесли клиенты, находящиеся сейчас в активном статусе. Как можно реализовать решение такой простой задачи?
Динамический выбор алгоритма
Отлично! Похоже мы нашли универсальный алгоритм, который самый быстрый. Нужно просто использовать его всегда и не беспокоиться более об этом вопросе. Но если мы учтем еще и расход памяти все станет немного сложнее. Для Nested Loop - память не нужна, Merge Join - нужна только для сортировки (если она будет). Для Hash Join - нужна оперативная память.
Оказывается расход памяти - это еще не все. В зависимости от общего числа элементов в массивах скорость работы разных алгоритмов ведет себя по-разному. Проверим для меньшего числа элементов (P, V) равному (50, 100). И ситуация переворачивается на диаметрально противоположную: Nested Loop самый быстрый - 2.202 микросекунды, Merge Join - 4.715 микросекунды, Hash Join - 7.638 микросекунды. Зависимость скорости работы каждого алгоритма можно представить таким графиком:
Когда Вы встречаете случай использования оператора Hash Join (хэш-соединение), это говорит о наличии тяжелого запроса. В отличие то соединения Nested Loops Join, которое хорошо для относительно маленьких наборов данных, и от соединения Merge Join, которое помогает при умеренных размерах наборов данных, хэш-соединение превосходит другие типы соединений при необходимости соединения огромных наборов данных. Хэш-соединения распараллеливается и масштабируется лучше любого другого соединения и сильно выигрывает при большой производительности информационных хранилищ (я вернусь к обсуждению параллельного выполнения запросов в следующей серии статей).
Хэш-соединение имеет много общего с соединением слиянием. Подобно соединению слиянием, для него требуются не менее одного предиката объединения по эквивалентности, оно поддерживает остаточные предикаты, а также все внешние соединения и полусоединения. В отличие от соединения слиянием, для него не требуется наличие упорядоченных входных потоков и для поддержки полного внешнего соединения требуется наличие предиката соединения по эквивалентности.
Сравнение Left Deep, Right Deep и Bushy - деревьев хэш-соединений
Эти термины относятся к форме плана исполнения запроса, что проиллюстрировано на этом рисунке:
Сравнение Left Deep, Right Deep и Bushy
Форма дерева соединения особенно важна для хэш-соединений, поскольку от этого зависит потребление памяти.
В густом слева дереве, выходной поток одного хэш-соединения является входным потоком компоновки следующего хэш-соединения. Поскольку хэш-соединения должны получить весь входной поток компоновки до того, как начнётся стадия проб, в густом слева дереве активными одновременно могут быть только смежные пары хэш-соединений. Например, на показанном выше рисунке всё начинается с построения хеш-таблицы для HJ1. Когда HJ1 перейдёт на стадию проб, становится возможным использовать выходной поток HJ1, который нужен для формирования хеш-таблиц для HJ2. Когда HJ1 прошёл стадию проб, используемая для хеш-таблиц память может быть освобождена. Только после этого можно начинать стадию проб для HJ2 и строить хеш-таблицу для HJ3. Таким образом, HJ1 и HJ3 никогда не будут активны одновременно и поэтому могут использовать одно и то же распределение памяти. Полный объем необходимой памяти займёт: max(HJ1 + HJ2, HJ2 + HJ3).
В густом справа дереве, выходной поток одного хэш-соединения является входным пробным потоком следующего хэш-соединения. Все хэш-соединения должны полностью сформировать свои хеш-таблицы до того, как начнётся стадия проб. Все хэш-соединения активны одновременно и не могут использовать одну и ту же память совместно. Когда начинается стадия проб, поток строк заполняет дерево хэш-соединений, без использования блокировок. Таким образом, полный объем необходимой памяти будет равен: HJ1 + HJ2 + HJ3.
Join Orders and Join Trees¶
When you hash-join several row sources with an inner join, Oracle can in principle swap the order without affecting the result set. Why would it want to do that? Well, the optimizer may discover that one particular join order is better than all the others. For an inner join of \(n\) tables, there are \(n!\) possible join orders. For four tables, we have \(4! = 4\cdot 3\cdot 2\cdot 1 = 24\) possibilities. So the chances are that there is at least one that is significantly better and one that is the absolute worst.
Let’s take four tables: T1, T2, T3, and T4. A so-called left-deep join tree is obtained in the following way:
- Place T1’s hash cluster in a workarea.
- Join T1 and T2. Call the intermediate result set J12.
- Place J12’s hash cluster in a workarea.
- Drop T1’s workarea.
- Join J12 and T3. Call the intermediate result set J123.
- Place J123’s hash cluster in a workarea.
- Drop J12’s workarea.
- Join J123 and T4.
- Drop J123’s workarea.
The italicized items are the actual logical steps in the join order. The left row source is always the driving row source in our notation, and the right row source is always the probe row source. We can also write this succinctly as ( ( T1 → T2 ) → T3 ) → T4.
For a right-deep join tree we have the following steps:
- Place T4’s hash cluster in a workarea.
- Place T3’s hash cluster in a workarea.
- Place T2’s hash cluster in a workarea.
- Join T2 and T1. Call the intermediate result set J21.
- Place J21’s hash cluster in a workarea.
- Drop T2’s workarea.
- Join T3 and J21. Call the intermediate result set J321.
- Place J321’s hash cluster in a workarea.
- Drop T3’s workarea.
- Join T4 and J321.
- Drop all remaining workareas.
We can write this as T4 → ( T3 → ( T2 → T1 ) ).
What is hopefully clear from these sequences is that a left-deep join tree requires two concurrent workareas, whereas a right-deep join tree has as many workareas as row row sources. So, why on earth do we ever want a right-deep join tree?
Suppose for a second that T1 is enormous and the remaining tables are relatively small, which often happens in data warehouses. Just think of T1 as being the fact table (e.g. sales) and T2, T3, and T4 dimension tables (e.g. products, customers, and suppliers). In a left-deep join tree we would create a large workarea with T1, and potentially do a couple of Cartesian joins on the dimension tables as these often do not have join conditions with one another. This would leave us with a monstrous hash cluster for T1 that will likely not fit in memory. Moreover, the hash clusters of the Cartesian joins of the dimension tables may also easily be more than Oracle can handle. The right-deep join tree places the smaller tables in workareas and finally scans the large table T1 instead. In doing so, we have more workareas but they are all likely to fit in memory, thus allowing us to feel the wind of linear scalability in our hair as we speed through the joins.
Let’s not get carried away now. How do we obtain a right-deep from a left-deep join tree? We can go from a left-deep join tree to a right-deep join tree in the following manner:
- Swap T4: T4 → ( ( T1 → T2 ) → T3 ).
- Swap T3: T4 → ( T3 → ( T1 → T2 ) ).
- Swap T2: T4 → ( T3 → ( T2 → T1 ) ).
Notice that in the first swap we have obtained an intermediate result set as a probe row source.
The corresponding (simplified) execution plans would look something like the ones shown below. In particular, for the left-deep join tree we have:
And for the right-deep join tree we see:
These are of course not all of Oracle’s options. Bushy joins (yes, they are really called that) or zigzag join trees have some of the row sources swapped but not all as in the case of left-deep and right-deep join trees. An example of such a zigzag tree would be the following: ( T1 → T2 ) → ( T3 → T4 ). To be specific, we obtain that particular join order as indicated:
- Join T1 and T2. Call the intermediate result set J12.
- Join T3 and T4. Call the intermediate result set J34.
- Join J12 and J34.
Interestingly, bushy joins are never considered by the optimizer. Hence, if you believe a bushy join to be the best join order possible, you have to force Oracle with the leading hint.
Что далее?
После того, как я закончил краткий обзор трёх операторов соединения, в следующих статьях я планирую резюмировать некоторые характеристики этих операторов и показать несколько примеров того, как ведёт себя SQL Server при некоторых вариантах соединений таблиц.
In a hash join, Oracle hashes the join key of the ‘driving’ row source in memory, after which it runs through the ‘probe’ row source and applies the hash to obtain the matches. We have placed the words ‘driving’ and ‘probe’ in quotes to indicate that the nomenclature is slightly different for hash joins though still applicable. Because of the hashing it is clear that an index on the probe row source will not improve the performance of the hash join. The only indexes that are beneficial in a hash join are indexes on predicates in the WHERE clause, but that is — as we have said — not specific to hash joins at all. Moreover, when the probe row source is table, a hash join does not visit blocks multiple times, since the database goes through the probe row source once. In fact, if Oracle decides to do a full table scan on the probe row source it may also decide to do multi-block reads to bump its retrieval efficiency.
It’s not all peachy though. Suppose that the probe row source is huge but only very few rows match the join clause and that we have no predicate or one that is barely selective. With a hash join he database visits many blocks that contain no data we’re interested in, because we cannot retrieve the rows through an index. Whether the balance is tipped in favour of nested loops with an index lookup of the probe row source, if of course available, that perhaps visits blocks over and over again, or a hash join with a single scan of each block depends mainly on the selectivity of the join condition and the clustering factor of the index. In these cases it is often advantageous to fix the execution plan with hints once you have discovered and argued that one consistently outperforms the other.
Hash joins scale linearly too, but there is one caveat — isn’t there always? The entire hash table has to fit in memory. If it does not, the hash table will spill onto disk, which ruins the linear scalability to the ground. As always, select only the columns you need as the size of the hash table may increase dramatically and thus ruin the performance benefit when Oracle runs out of memory.
Another gotcha with hash joins is that they can only be used with equality join conditions.
Алгоритм
Хэш-соединение выполняется в две стадии: компоновка и проба. Во время компоновки осуществляется чтение всех строк первого входного потока (часто, его называют левым потоком или потоком компоновки), хеширование строк по ключам соединения эквивалентности и создание в оперативной памяти хеш-таблицы. Во время пробы осуществляется чтение всех строк второго входного потока (часто его называют правым потоком или пробным потоком), хеширование строк этого потока по тем же ключам соединения эквивалентности, а потом осуществляется просмотр или поиск соответствий строк в хеш-таблице. Так как хеш-функции могут быть подвержены коллизиям (два разных значения ключа имеют одинаковый хэш), приходится проверять каждое потенциальное соответствие, что необходимо для гарантии того, что в этом случае действительно совпадение обусловлено соединением, а не коллизией.
Алгоритм в псевдокоде:
for each row R1 in the build table
calculate hash value on R1 join key(s)
insert R1 into the appropriate hash bucket
for each row R2 in the probe table
calculate hash value on R2 join key(s)
for each row R1 in the corresponding hash bucket
if R1 joins with R2
Обратите внимание, что в отличие от вложенных циклов и слияния, которые немедленно начинают выдавать результат, хэш-соединение блокируют вывод до окончания компоновки. То есть вначале должны быть полностью прочитан и обработан поток компоновки, и только потом могут быть возвращены какие-либо строки. Кроме того, в отличие от других методов соединения, хэш-соединение требует предоставления памяти для хранения хеш-таблиц. Таким образом, существует предел числа параллельных хэш-соединений, которые SQL Server может поддерживать в какой то момент времени. Хотя эти ограничения не являются проблемой для информационных хранилищ, они могут оказаться нежелательными для большинства OLTP приложений.
Память и сброс на диск
До начала выполнения хэш-соединения, SQL Server пытается оценить, сколько памяти потребуется для хеш-таблиц. Выполняется оценка кардинальности элементов для размера потока компоновки, базирующаяся на ожидаемом среднем размере строк, что позволяет оценить требующийся объем и конфигурацию памяти. Для уменьшения задействуемой хэш-соединением памяти, в качестве таблицы потока компоновки выбирается самая маленькая из двух таблиц. После этого выполняется попытка резервирования такого объёма памяти, который бы гарантировал успешное выполнение хэш-соединения.
Что же случается, если хэш-соединению будет предоставлено меньше памяти, чем было запрошено, или если оценка оказалось слишком низкой? В этих случаях, на стадии компоновки хэш-соединение может выйти за пределы памяти. Если хэш-соединение вышло за пределы памяти, начинается сброс на диск небольшого процента от всей хеш-таблицы (во временный объект tempdb). Хэш-соединение следит, какие разделы хеш-таблицы все еще находятся в памяти, а какие были сброшены на диск. Поскольку каждая новая строка читается из таблицы компоновки, можно легко проверить, является ли она хэшем раздела в оперативной памяти, или она находиться в разделе на диске. Если это хэш в оперативной памяти, всё происходит по обычной схеме. Если это хэш на дисковом разделе, осуществляется запись строки на диск. Этот процесс позволяет управлять превышением памяти и сбросом разделов на диск, и он может занимать много времени, до тех пор, пока стадия компоновки не будет закончена.
Подобный процесс исполняется во время стадии пробы. Для каждой новой строки из таблицы пробного потока выполняется проверка, является ли она хэшем раздела в оперативной памяти или на диске. Если это хэш раздела в оперативной памяти, берутся пробы из хеш-таблицы, генерируются соответствующие условиям соединения строки, и после этого строка отбрасывается. Если это хэш раздела на диске, осуществляется запись строки на диск. Как только будет завершен первый проход таблицы пробного потока, процесс возвращается поочерёдно к другим разделам, которые были сброшены на диск, считывает в память строки потока компоновки, восстанавливает хеш-таблицу для каждого из разделов, и затем считывает соответствующее разделы пробного потока, завершая соединение.
Читайте также: