Алгоритмы соединения на основе блоков

В версиях MariaDB/MySQL до 5.3 был реализован только один алгоритм соединения на основе блоков: алгоритм блочных вложенных циклов (BNL), который мог использоваться только для внутренних соединений.

MariaDB 5.3 усовершенствовал реализацию соединений BNL и предоставляет различные алгоритмы соединений на основе блоков, которые могут использоваться для внутренних соединений, внешних соединений и полусоединений. Алгоритмы соединений на основе блоков в MariaDB используют буфер соединения для накопления записей первого операнда соединения, прежде чем начать поиск совпадений во втором операнде соединения.

На этой странице документированы различные алгоритмы соединения на основе блоков.

• Соединение блочных вложенных циклов (BNL)
• Соединение блочных вложенных циклов с хешированием (BNLH)
• Соединение блочного индекса, известное как соединение пакетного доступа к ключам (BKA)
• Соединение блочного индекса с хешированием, известное как соединение пакетного доступа к ключам с хешированием (BKAH)

Соединение блочных вложенных циклов

Основное различие в реализации соединения BNL в MariaDB 5.3 по сравнению с более ранними версиями MariaDB/MySQL заключается в том, что первая использует новый формат для записей, записываемых в буферы соединения. Этот новый формат позволяет:

• Более эффективное использование места в буфере для значений NULL и значений полей гибкого типа (например, типа varchar)
• Поддержка так называемых инкрементных буферов соединения, экономящих место в буфере для соединений с несколькими способами
• Использование алгоритма для внешних соединений и полусоединений

Как работает соединение блочных вложенных циклов

Алгоритм выполняет операцию соединения таблиц t1 и t2 в соответствии со следующей схемой.
Записи первого операнда записываются в буфер соединения по одной до тех пор, пока буфер не заполнится.
Записи второго операнда считываются из основной/временной таблицы по одной. Для каждой считываемой записи r2 таблицы t2 буфер соединения сканируется, и для каждой записи r1 из буфера, которая соответствует r2, конкатенация интересных полей r1 и r2 отправляется в поток результатов соответствующего частичного соединения.
Для чтения записей t2 выполняется полное сканирование таблицы, полное сканирование индекса или сканирование индекса диапазона. Только записи, которые удовлетворяют условию, поданному в таблицу t2, проверяются на соответствие записям из буфера соединения.
После завершения сканирования таблицы t2 новая порция записей первого операнда заполняет буфер, и ищутся совпадения для этих записей в t2.
Буфер заполняется и сканирование второго операнда, ищущего совпадения в буфере соединения, выполняется снова и снова, пока не будут исчерпаны записи первого операнда.
В итоге алгоритм сканирует второй операнд столько раз, сколько происходит заполнений буфера соединения.

Более эффективное использование места в буфере соединения

Место в буфере соединения не используется для значений NULL.
Значения полей гибкого типа больше не дополняются нулями до максимального размера поля.

Инкрементные буферы соединения

Если у нас есть запрос с соединением трех таблиц t1, t2, t3, при котором таблица t1 соединяется с таблицей t2, а результат этой операции соединения соединяется с таблицей t3, то для выполнения запроса можно использовать два буфера соединения. Первый буфер соединения B1 используется для хранения записей, содержащих интересные поля таблицы t1, а второй буфер соединения B2 содержит записи с полями из частичного соединения t1 и t2. Интересующие поля любой записи r1 из B1 копируются в B2 для любой записи r1, r2 из частичного соединения t1 и t2. Можно предположить хранение в B2 только указателя на позицию полей r1 в B1 вместе с интересными полями из t2. Таким образом, для любой записи r2, соответствующей записи r1, буфер B2 будет содержать ссылку на поля r1 в B1 и поля r2. В этом случае буфер B2 называется инкрементным. Инкрементные буферы позволяют избежать копирования значений полей из одного буфера в другой. Они также позволяют сэкономить значительное количество места в буфере, если для записи из t1 ожидается несколько совпадений из t2.

Использование буферов соединения для простых внешних соединений и полусоединений

Если буфер соединения используется для простого левого внешнего соединения таблиц t1 и t1 t1 LEFT JOIN t2 ON P(t1,t2), то каждой записи r1, хранящейся в буфере, предоставляется флаг совпадения. Изначально этот флаг выключен. Как только будет найдено первое соответствие для r1, этот флаг включается. Когда все соответствующие кандидаты из t2 проверены, записи в буфере соединения сканируются, и для тех из них, у которых флаги соответствия все еще выключены, генерируются строки с заполнением NULL. Тот же флаг соответствия используется для любой записи в буфере соединения, если выполняется операция полусоединения t1 SEMI JOIN t2 ON P(t1,t2) с алгоритмом соединения на основе блоков. Когда этот флаг соответствия установлен в положение «включено» для записи r1 в буфере, больше не ищутся совпадения из таблицы t2 для записи r1.

Соединение блочного хеширования

Алгоритм соединения блочного хеширования — это новый вариант, который может использоваться для операций соединения в MariaDB 5.3. Он может использоваться в случаях, когда существуют подусловия эквисоединения для соединенных таблиц, другими словами, когда можно извлечь равенства вида t2.f1= e1(t1),...,t2.fn=en(t1) из полного условия соединения. Как любой алгоритм соединения на основе блоков, этот алгоритм использует буфер соединения, заполненный записями первого операнда, и ищет совпадения для записей в буфере в записях второго операнда.

Как работает соединение блочного хеширования

Для каждого заполнения буфера соединения и каждой записи r1 из него алгоритм строит таблицу хеширования с ключами, построенными на значениях e1(r1),...en(r1). Затем сканируются записи t2. Для каждой записи r2 из t2, которая соответствует условию, поданному в таблицу t2, вычисляется хеш-ключ по полям r2.f1,..., r2.fn для запроса в таблицу хеширования. Запрос возвращает те записи из буфера, к которым r2 соответствует. Как и в случае с алгоритмом соединения BNL, этот алгоритм сканирует второй операнд столько раз, сколько происходит заполнений буфера. Тем не менее, он должен искать только в одной корзине таблицы хеширования, когда ищет записи, к которым соответствует запись из t2, а не во всех записях в буфере соединения, как это делает алгоритм BNL. Реализация этого алгоритма в MariaDB строит таблицу хеширования с хеш-ключами в самом конце буфера соединения. Поэтому количество записей, записываемых в буфер за одно заполнение, меньше, чем в алгоритмах соединения BNL. Однако гораздо более короткий список возможных совпадающих кандидатов делает алгоритм соединения блочного хеширования обычно намного быстрее, чем BNL-соединение.

Соединение пакетного доступа к ключам

Алгоритм соединения пакетного доступа к ключам выполняет поиск по индексу при поиске возможных совпадающих кандидатов, предоставленных вторым операндом соединения. В этом отношении алгоритм ведет себя как обычный алгоритм соединения. Однако BKA выполняет поиск по индексу для набора записей из буфера соединения. Для обычных баз данных, таких как InnoDB/MyISAM, это позволяет извлекать совпадающие кандидаты оптимальным способом. Для баз данных с удаленным хранилищем, таким как FederateX/Spider, алгоритм позволяет экономить на передачах между узлом MySQL и узлами хранилища данных.

Как работает соединение пакетного доступа к ключам

Реализация алгоритма в версии 5.3 в значительной степени использует многодиапазонный интерфейс чтения и его свойства. Интерфейс скрывает фактический механизм извлечения возможных кандидатов для соответствия записям из таблицы, подлежащей соединению. Как и любой алгоритм соединения на основе блоков, соединение BKA многократно заполняет буфер соединения записями первого операнда и для каждого заполнения находит записи из таблицы соединения, которые могут соответствовать записям в буфере. Для поиска таких записей он обращается к интерфейсу MRR для выполнения поиска по индексу с ключами, построенными на всех записях из буфера. Вместе с каждым ключом интерфейс получает обратный адрес — ссылку на запись, по которой был построен этот ключ. Фактические функциональные возможности интерфейса MRR каким-то образом организуют и оптимизируют процесс извлечения записей соединенной таблицы по полученным ключам. Каждая извлеченная запись r2 дополняется обратным адресом, связанным с ключом, по которому была найдена запись, и результат передается процедуре соединения BKA. Процедура берет запись r1 из буфера соединения по обратному адресу, соединяет ее с r2 и проверяет условие соединения. Если условие вычисляется как истинное, соединенные записи отправляются в поток результатов операции соединения. Таким образом, для каждой записи, возвращенной интерфейсом MRR, обращается только к одной записи из буфера соединения. Количество записей из таблицы t2, извлеченных соединением BKA, точно такое же, как и для обычного алгоритма соединения вложенных циклов. Тем не менее, соединение BKA позволяет оптимизировать порядок извлечения записей.

Взаимодействие соединения BKA с функциями MRR

Соединение BKA взаимодействует с функциями MRR, соблюдая следующий контракт. Процедура соединения вызывает функцию MRR multi_range_read_init, передавая ей функции обратного вызова, которые позволяют инициализировать чтение ключей для записей в буфере соединения и итерировать по этим ключам. Она также передает параметры буфера для потребностей MRR, выделенных в пространстве буфера соединения. Затем соединение BKA многократно вызывает функцию MRR multi_range_read_next. Функция работает как функция-итератор по записям, извлеченным по поиску по индексу с ключами, сгенерированными функцией обратного вызова, установленной при вызове multi_range_read_init. Вызов функции multi_range_read_next возвращает следующую извлеченную запись через выделенный буфер записей и соответствующую ссылку на сопоставленную запись из буфера соединения в качестве выходного параметра функции.

Управление использованием алгоритмов соединения на основе блоков

В настоящее время поддерживается 4 разных типа алгоритмов соединений на основе блоков. Для конкретной операции соединения каждый из них может быть использован с обычным (плоским) буфером соединения или с инкрементным буфером соединения.

Три переключателя оптимизатора — join_cache_incremental, join_cache_hashed, join_cache_bka — и переменная системы join_cache_level управляют тем, какой из 8 вариантов алгоритмов соединений на основе блоков будет использоваться для операций соединения.

Если join_cache_bka выключено, то алгоритмы соединения BKA и BKAH запрещены. Если join_cache_hashed выключено, то алгоритмы соединения BNLH и BKAH запрещены. Если join_cache_incremental выключено, то инкрементные варианты алгоритмов соединений на основе блоков запрещены.

По умолчанию переключатели join_cache_incremental, join_cache_hashed, join_cache_bka установлены в 'включено'. Однако это не означает, что по умолчанию разрешено использовать любой из алгоритмов соединения на основе блоков. Все они разрешены только если переменная системы join_cache_level установлена в 8. Эта переменная может принимать целое значение в интервале от 0 до 8.

Если значение установлено в 0, для операции объединения нельзя использовать алгоритм на основе блоков. Значения от 1 до 8 соответствуют следующим вариантам алгоритмов объединения на основе блоков:

• 1 – Плоский BNL
• 2 – Инкрементный BNL
• 3 – Плоский BNLH
• 4 – Инкрементный BNLH
• 5 – Плоский BKA
• 6 – Инкрементный BKA
• 7 – Плоский BKAH
• 8 – Инкрементный BKAH

Если значение join_cache_level установлено в N, любые алгоритмы на основе блоков с уровнем, превышающим N, запрещены.

Итак, если join_cache_level установлен в 5, использование BKAH запрещено, а также использование инкрементного BKA запрещено, в то время как использование всех остальных вариантов контролируется настройками переключателей оптимизатора join_cache_incremental, join_cache_hashed, join_cache_bka.

По умолчанию join_cache_level установлен в 2. Другими словами, разрешено только использование плоского или инкрементного BNL.

По умолчанию алгоритмы на основе блоков могут использоваться только для обычных (внутренних) операций объединения. Чтобы разрешить их для внешних операций объединения (левые внешние объединения и правые внешние объединения), необходимо установить переключатель оптимизатора outer_join_with_cache в «включено». Установка переключателя оптимизатора semijoin_with_cache в «включено» позволяет использовать эти алгоритмы для операций полуобъединения.

В настоящее время только инкрементные варианты алгоритмов объединения на основе блоков могут использоваться для вложенных внешних объединений и вложенных полуобъединений.

Размер буферов объединения

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

MariaDB 5.3 представила системную переменную join_buffer_space_limit, которая ограничивает общее использование памяти для буферов объединения в запросе.

Для оптимизации использования буферов объединения в пределах ограничения, установленного join_buffer_space_limit, следует использовать переключатель оптимизатора optimizer switch optimize_join_buffer_size=on. Когда этот флаг установлен в «выкл.» (по умолчанию до MariaDB 10.4.2), размер используемого буфера объединения берется непосредственно из системной переменной join_buffer_size. Когда этот флаг установлен в «вкл.» (по умолчанию начиная с MariaDB 10.4.3), размер буфера зависит от оценочного количества строк в частичном объединении, записи которых должны храниться в буфере.

Связанные настройки MRR

Для использования алгоритмов объединения BKA/BKAH для InnoDB/MyISAM необходимо установить переключатель оптимизатора mrr в «включено». При использовании этих алгоритмов для InnoDB/MyISAM общую производительность операций объединения можно значительно улучшить, если переключатель оптимизатора mrr_sort_keys установлен в «включено».