Более быстрая структура запроса, чем B + дерево! ! !

Управляемое чтение

Все мы знаем, что индексная структура B+Tree в MySQL очень быстро находит записи на основе определенных условий. Итак, движимые постоянным стремлением к совершенству, задумывались ли вы когда-нибудь о том, будет ли MySQL иметь более быструю структуру данных, чем B+Tree, для ускорения поиска записей? Ответ — да.Чтобы мы могли быстрее получить записи, которые мы хотим найти, MySQL создает хэш-карту часто запрашиваемых условий и результатов дерева индексов в InnoDB, так что запросу не нужно искать B+ каждый раз, когда Tree чтобы найти результат, эта хеш-карта называетсяAHI, полное название Adaptive Hash Index, адаптивный хеш-индекс.

Услышав название, вы, возможно, уже догадались об одном или двух. Верно! На самом деле это HashTable. Когда мы изучали "Структура данных" в колледже, мы все знали, что Hash Table очень быстро находит данные одного из узлов, а временная сложность алгоритма составляет O (1). Следовательно, по сравнению с B+Tree С точки зрения производительности поиска, он должен быть быстрее.

Однако возникает вопрос: почему эта хеш-таблица называется адаптивным хеш-индексом, этот "Адаптивный"Какая концепция?

Сегодня Сяо К. начнет со следующего случая, подробно объяснит AHI и постепенно покажет вам, как понимать AHI.адаптивныйЧто происходит?

Предположим, на нашей платформе знакомств есть функция: отфильтровывать пользователей в возрасте от 15 до 23 лет. Затем мы обычно используем следующую реализацию SQL:

SELECT id, age, sex FROM user WHERE age >= 15 AND age <= 23

Параллельно мы создали индекс для пользовательской таблицыindex_age_sex(age,sex), значит, теперь посмотрим, как этот SQL использует AHI?

AHI

Поскольку AHI также является HashTable, в первую очередь вам обязательно будет интересно, каков ее ключ и какова ее ценность? Итак, давайте сначала рассмотрим ключ и значение AHI.

Мы видим, что условие запроса оператора в «Руководстве»age >= 15 AND age <= 23, в соответствии со значением AHI, которое я сказал выше: создайте хэш-карту условия запроса и его результата, тогда хеш-таблица, которую мы представляем, похожа на следующую:

на фото вышеage >= 15 AND age <= 23Представляет условие запроса, то есть ключ, а нижеследующий индексindex_age_sexЕсть 4 записи, удовлетворяющие условиям запроса, то есть Value. Среди них структура каждой записи[age,sex,id].

Key

Однако, как видно из приведенного выше рисунка, если имя поля условия запроса очень длинное, то пространство для хранения ключей станет очень большим, что определенно неприемлемо для чувствительной к памяти системы, такой как MySQL.Поэтому MySQL следующая структура предназначен для хранения ключей:

На картинке выше показан поисковый индексindex_age_sex, условие запросаage >= 15 AND age <= 23Структура:

• search_info::n_fields: MySQL используетn_fieldsЧтобы выразить поля, используемые индексом запроса, как показано на рисунке1Указывает, что условие запроса использует индексindex_age_sexПервое поле в , т.е.age. (ПС: еслиn_fields=2Указывает, что условие запроса использует индексindex_age_sexсерединаageиsexдва поля). Преимущество этого заключается в том, что мы можем выразить поле индекса, используемое условием запроса, сохраняя числа в памяти, что экономит место для хранения.

• dtuple_t: Поскольку условие запроса является запросом диапазона, MySQL использует дваdtuple_tструктура для представления двух граничных значений в условии. Как показано выше, первый справаdtuple_t15 в условии запроса левое граничное значение15,секундаdtuple_t23 в условии запроса правое граничное значение23.

В конечном итоге MySQL проходит через дваsearch_info::n_fieldsиdtuple_tдля выражения условий запросаage >= 15 AND age <= 23. Эта комбинация представлена ​​двумя стрелками на рисунке выше.

После разговора о ключе давайте посмотрим, как MySQL создает значение HashTable?

Value

Конечно, если мы будем следовать структуре приведенной выше HashTable, мы должны думать, что условия запросаage >= 15 AND age <= 23, его значением в HashTable является запись ниже 1-1 на приведенном выше рисунке. Однако давайте теперь рассмотрим следующий сценарий:

Предположим, теперь я изменяю условие запроса вage >= 15 AND age < 16, то эта HashTable становится такой:

на фото вышеage >= 15 AND age < 16Представляет условие запроса, ниже приведен индексindex_age_sex2 записи, соответствующие условиям запроса в , где структура каждой записи[age,sex,id].

Сравнив два приведенных выше рисунка 1-1 и 1-2-1, мы обнаружили, что в результатах запроса есть повторяющиеся записи, соответствующие двум условиям запроса.15,0,2и15,0,5. Теперь есть только 2 условия запроса, которые будут иметь повторяющиеся записи.Тогда, если есть десятки или даже сотни условий запроса, которые будут содержать повторяющиеся записи в будущем, то, если HashTable хранится для каждого условия и соответствующего результата, сохраняется ли он в HashTable?

Поэтому, чтобы сэкономить место для хранения результатов запроса, мы можем объединить две вышеупомянутые хэш-таблицы запросов в следующую структуру:

Рисунок MySQL выполнит условиеage >= 15 AND age <= 23и условияage >= 15 AND age < 16Соответствующие записи объединяются в 4 записи:

• состояниеage >= 15 AND age <= 23Две записи перед картой. Зеленая стрелка, как указано выше.
• состояниеage >= 15 AND age < 16Сопоставьте две последние записи. Красная стрелка, как показано выше.

Однако, говоря о структуре ключа, я сказал, что структура ключа, фактически разработанная MySQL, показана на рисунке 1-1-1, что соответствует рисунку 1-2-2.Очевидно, что ключ на рисунке 1-2 -2 на самом деле не хранится в структуре MySQL. Затем, в сочетании с концептуальной диаграммой HashTable 1-2-2, давайте посмотрим, как MySQL проектирует отображение ключа и значения AHI?

Как показано на рисунке выше, это структура хранения полного AHI MySQL. Среди них часть над значением является ключом, Я объяснил структуру ключа выше, поэтому я не буду повторяться здесь. Мы в основном смотрим на часть Value:

• Cell: позвонил в AHIhash_cell_t,hash_cell_tupleаббревиатура от. То есть часть клетки на рисунке. Это массив, как показано выше, это массив, содержащий 2 ячейки. Граничное значение каждого условия запроса может быть расположено в определенной ячейке с помощью операции хеширования. Например:

  • Состояние на картинкеage >= 15 AND age <= 23Левое граничное значение 15 в , находит первую ячейку с помощью хэш-операции.
  • Состояние на картинкеage >= 15 AND age < 16Левое граничное значение 15 в также находит первую ячейку с помощью операции хеширования.
  • Состояние на картинкеage >= 15 AND age <= 23Правое граничное значение 23 в , также находит первую ячейку посредством операции хеширования.
  • Состояние на картинкеage >= 15 AND age < 16Правое граничное значение 16 находится во второй ячейке посредством хэш-операции.

• Node: позвонил в AHIha_node_t,hash_node_tupleаббревиатура от. Ячейка может содержать несколько узлов, то есть несколько граничных значений условий запроса могут быть расположены в ячейке с помощью хэш-операции, а записи узлов, соответствующие каждому граничному значению, хранятся в ячейке. сформировался.

  • Например, условие запроса на графикеage >= 15 AND age <= 23Левое граничное значение 15 находится в первой ячейке посредством хеш-операции, а первый узел под ячейкой сохраняет запись, соответствующую 15.(15,0,2)Связанная информация.

  • Аналогично, запрос фигурыage >= 15 AND age <= 23Правое граничное значение 23 в , также находит первую ячейку с помощью операции хеширования, а второй узел под ячейкой хранит относящуюся к записи информацию, соответствующую 23.

  • Точно так же условия запроса на рисункеage >= 15 AND age < 16Правое граничное значение в 16 с помощью хеш-операции находит вторую ячейку, а первый узел под ячейкой сохраняет запись, соответствующую 16.(16,0,3)Связанная информация.

  • Эти два узла образуют односвязный список.

  NodeОсновные элементы в основном 3:

  • block: Храните соответствующую информацию, соответствующую результатам хеш-карты. Среди них основные элементы включаютleft_sideиpage.

    • Например, в блоке слева на рисункеcurr_left_side = true, представляющий запись в узле<15,0,2>это условие запросаage >= 15 AND age <= 23иage >= 15 AND age < 16Крайняя левая граничная запись .
    • Например, в блоке слева на рисункеpage（10）Представляет запись в этом узле<15,0,2>в дереве индексовindex_age_sexвнутри 10-го листового узла.
    • Например, в блоке справа на рисункеcurr_left_side = false, представляющий запись в узле<16,0,3>это условие запросаage >= 15 AND age < 16самая правая граница записи.
    • Например, рисунок на правом блоке вpage（20）Представляет запись в этом узле<16,0,3>в дереве индексовindex_age_sexв пределах 20-го листового узла.

  • data: результат хеш-карты.

    • Например, в первом узле на рисунке<15,0,2>состояниеage >= 15 AND age <= 23иage >= 15 AND age < 16Запись, соответствующая левому граничному значению 15.
    • Например, в третьем узле на рисунке<16,0,3>состояниеage >= 15 AND age < 16Запись, соответствующая правому граничному значению 16.

Теперь мы знаем полную структуру AHI. Благодаря этой структуре мы обнаруживаем, что MySQL напрямую не отображает условия и результаты запроса, а связывает условия и результаты через ячейки. Преимущество этого в том, что узлы, соответствующие граничным значениям те же условия Он может быть разделен в памяти, экономя место для хранения.

Запрос AHI

Он так много сказал, не найден так, как будто структура AHI не полностью сохранила запрос, соответствующий всем результатам, записанным (в конце концов, мне нужна запись четырех, соответствует условиям OH!), Что MySQL является тем, как от AHI найти все Познакомьтесь с условиями записи это? Здесь мы должныage >= 15 AND age < 16Это условие запроса является примером, давайте посмотрим на этот процесс поиска:

1. В соответствии с условным левым граничным значением 15 выполните хеш-операцию, вычислите значение кратности и найдите первую ячейку через это значение.

2. Пройдитесь по узлам под первой ячейкой и найдите первый узел, соответствующий граничному значению 15.

3. Найдите соответствующую запись по первому узлу<15,0,2>,page（10)иcurr_left_side=true.

4. Согласно предыдущему шагуpageНомер 10 и запись<15,0,2>, в дереве индексовindex_age_sexНайдите совпадение в 10-м листовом узле в<15,0,2>запись о<15,0,2>.

5. В соответствии с условным правым граничным значением 16 выполните хэш-операцию, вычислите значение кратности и найдите вторую ячейку через это значение.

6. Пройдите узлы под второй ячейкой и найдите первый узел, соответствующий граничному значению 16.

7. Найдите соответствующую запись по первому узлу<16,0,3>,page（11)иcurr_left_side=false.

8. Согласно предыдущему шагуpage№ 11 и рекорды<16,0,3>, в дереве индексовindex_age_sexСовпадение найдено в 11-м листовом узле<16,0,3>запись о<16,0,3>.

9. Как записано на шаге 3<15,0,2>в узлеcurr_left_side=true, запись описания<15,0,2>Крайняя левая запись для условия запроса, следовательно, из дерева индексовindex_age_sexвнутри 10-го листового узла<15,0,2>Запись начинается и пересекает другие записи в обратном направлении.

10. Как записано на шаге 7<16,0,3>в узлеcurr_left_side=false, запись описания<16,0,3>Это самая правая запись условия запроса, поэтому предыдущий шаг переходит к записи<16,0,3>Заканчивать.

11. Наконец, в дереве индексовindex_age_sexнайти все условия вage >= 15 AND age < 16запись о.

Среди них подробный процесс шагов 4, 8 ~ 11, вы можете обратиться к статье«Выполняет ли InnoDB последовательный поиск листовых узлов B+Tree? 》

Построить время AHI

Теперь, когда мы знаем, как MySQL находит записи, соответствующие условиям, через AHI, когда и как был создан этот AHI?

Во «Введении» я сказал, что MySQL строит AHI для часто используемых условий запроса, то есть отношения отображения между условиями и результатами. Следовательно, мы должны посмотреть, как MySQL определяет, часто ли используется это условие запроса?

Чтобы подсчитать частоту использования условия, MySQL разработал следующую структуру.

Разве это не немного знакомо? На самом деле фигураsearch_infoЭто структура информации запроса На рисунке 1-1-1 я говорил оsearch_infoатрибут вn_fields, а теперь позвольте мне поговорить о другом свойствеhash_analysis.

Когда запрос завершается успешно, MySQL записывает количество успешных запросов, накапливая этот атрибут. Например, изначальноhash_analysis=0, то условиеage >= 15 AND age < 16Запрос выполнен успешно,hash_analysis + 1 = 1, снова добиться успеха,hash_analysis + 1 = 2, и так далее, сколько раз это удалось,hash_analysisэто сколько.

когдаhash_analysisКогда значение превышает 17, MySQL создает AHI для запроса.

Однако, если запрос выполнен успешно, должен ли быть создан AHI? Ответ не обязательно! Давайте рассмотрим следующий сценарий:

SELECT age, sex FROM user WHERE age >= 15 AND age <= 18

В приведенном выше заявлении MySQL индексируетindex_age_sexЛистовые узлы в , найдите следующие 4 записи, которые удовлетворяют условиям:

<15,0,2>,<16,0,3>,<18,0,4>,<18,0,5>

На этот раз давайте посмотрим на процесс нахождения AHI с этим условием:

1. В соответствии с условным левым граничным значением 15 выполните хеш-операцию, вычислите значение кратности и найдите первую ячейку через это значение.

2. Пройдитесь по узлам под первой ячейкой и найдите первый узел, соответствующий граничному значению 15.

3. Найдите соответствующую запись по полученному узлу<15,0>,page（10)иcurr_left_side=true.

4. Согласно предыдущему шагуpageномер 10 и запись в дереве индексовindex_age_sexНайдите соответствующую запись узла в 10-м листовом узле.<15,0>Первая запись<15,0,2>.

5. В соответствии с условным правым граничным значением 18 выполните хеш-операцию, вычислите значение кратности и найдите вторую ячейку через это значение.

6. Пройдитесь по узлам под второй ячейкой и найдите первый узел, соответствующий граничному значению 18.

7. Найдите соответствующую запись по полученному узлу<18,0>,page（11)иcurr_left_side=false.

8. Согласно предыдущему шагуpageномер 11 и запись в дереве индексовindex_age_sexСоответствующая запись узла найдена в 11-м листовом узле.<18,0>первая запись о<18,0,4>.

9. Как записано на шаге 3<15,0>в узлеcurr_left_side=true, запись описания<15,0,2>Крайняя левая запись для условия запроса, следовательно, из дерева индексовindex_age_sexвнутри 10-го листового узла<15,0,2>Запись начинается и пересекает другие записи в обратном направлении.

10. Как записано на шаге 7<18,0>в узлеcurr_left_side=false, запись описания<18,0,4>Это самая правая запись условия запроса, поэтому предыдущий шаг переходит к записи<18,0,4>Заканчивать.

Среди них подробный процесс шагов 4, 8 ~ 10, вы можете обратиться к статье«Выполняет ли InnoDB последовательный поиск листовых узлов B+Tree? 》

Из приведенного выше процесса мы обнаружили проблему: записи Mingming в конечном узле 11.<18,0,5>также выполнить условияage >= 15 AND age <= 18, однако запрос AHI игнорирует эту запись. Как показано выше, запись отмечена пунктирной линией.PS: На девятом шаге выше записи, которые удовлетворяют правильному граничному значению 18, теперь являются условиями 2. Что, если записей больше 1k и 1w? Позволить MySQL пройти 1k, 1w записей конечных узлов, чтобы найти самую большую запись? Этот спектакль можно представить. . .

Следовательно, мы обнаруживаем, что эти запросы не поддерживаются AHI, мы не можем просто думать, что раз запрос успешен, значит, можно построить AHI.

Для этого MySQLsearch_infoВводится новое свойство, давайте посмотрим:

как на фото вышеn_hash_potentialИменно это новое свойство представляет количество раз, когда запрос может потенциально успешно построить AHI. Используйте его для решения проблемы описанного выше сценария:

Только в результатах, полученных запросом, значение поля выбора (например: выберите возраст, пол) в самой большой записи уникально,n_hash_potentialбудет накапливаться.

Таким образом, MySQL делает два перехвата, прежде чем на самом деле строить AHI:

• пройти черезhash_analysisПерехватите запрос со значением атрибута меньше 17. Только значение атрибута больше или равно 17, этот запрос может построить AHI
• еслиhash_analysisбольше или равно 17, затем проверьте еще разn_hash_potentialАтрибут, если значение атрибута меньше 100, то запрос будет перехвачен, иначе АИЧ может быть построен только по этому запросу

Затем возникает следующий вопрос: поскольку я уже знаю, что невозможно построить AHI в приведенном выше сценарии, почему я должен позволять обработке запросов входить в две вышеупомянутые проверки перехвата?

Поэтому, чтобы не входить в вышеописанную проверку на перехват, MySQL снова находится вsearch_infoСвойство вводится в:

на фотоlast_hash_succСвойство, указывающее, был ли AHI успешно построен в прошлый раз.

С этим атрибутом, если MySQL обнаружит, что приведенный выше сценарий вообще не может построить AHI, он установит его напрямую.last_hash_succ=false, то после того, как тот же запрос придет в следующий раз, он сразу же будет найденlast_hash_succ=false, последние две проверки перехвата больше не выполняются.

На основе приведенного выше анализа мы пришли к выводу, что запрос запускает процесс проверки построения AHI:

1. еслиlast_hash_succ=false, запрос не может построить AHI, иначе переходим к следующей проверке

2. еслиhash_analysis < 17, запрос не может построить AHI, иначе переходим к следующей проверке

3. еслиn_hash_potential < 100, запрос не может построить AHI, иначе он может построить AHI

Построить АИ

После разговора об условиях срабатывания, созданных Ai, давайте посмотрим, как mysql создает AHI?

Из объяснения раздела «Запросить AHI» мы знаем, что в процессе запроса AHI в Node in Aii есть несколько основных элементов.block,left_sideиpage, Следовательно, пока мы знаем, как строятся эти основные элементы, мы можем ясно описать процесс построения AHI.

Я беру следующее утверждение в качестве примера, чтобы увидеть процесс построения AHI:

SELECT id, age, sex FROM user WHERE age >= 15 AND age <= 18

Обратите внимание на красную линию на рисунке:

1. Согласно условному левому граничному значению 15, в индексовом деревеindex_age_sexНайдите первую запись, которая удовлетворяет граничному значению в 10-м узле листьев в<15,0,2>.

2. Поскольку существует только одна запись, удовлетворяющая левому граничному значению 15, MySQLup_match + 1 = 1, что указывает на то, что только одна запись удовлетворяет левому граничному значению. так какup_match > low_match,следовательно,search_infoсерединаleft_sideУстановите значение «истина».

3. Согласно условному левому граничному значению 15, выполните хеш-операцию на нем и найдите первую ячейку в AHI.

4. Обнаруживается, что в ячейке нет узлового узла, и создается узел. То есть узел серого цвета на рисунке.

5. Создайте блок в node. Светло-голубой блок, показанный выше.

6. индексное деревоindex_age_sexИнформация о 10-м листовом узле в блоке записывается вpageАтрибуты.

7. будет получено на шаге 2left_sideнаписано в блокеcurr_left_side.

8. Запись, полученная на шаге 1<15,0,2>Написать в узел.

9. Точно так же процесс построения AHI аналогичен условному правому граничному значению 18.

замок АХИ

Поняв процесс построения AHI, мы далее будем думать, что если AHI строится одновременно, возникнет проблема покрытия узлов. Следовательно, чтобы решить эту проблему, MySQL должен добавить блокировку в AHI, чтобы избежать проблемы покрытия узлов во время параллельного построения.

Конечно, мы не можем добавить глобальную блокировку на весь AHI, потому что это сильно повлияет на производительность запроса, поэтому MySQL проектирует блокировки таким образом.

Когда MySQL начинается, изinnodb_buffer_poolНесколько хэш-таблиц разделены на AHI. На рисунке я нарисовал 2 hashtables: hashtable [0] и hashtable [1]. Предположим, что MySQL получает 4 складывания через хеш-операцию 4 условий запроса. Как показано на рисунке выше, значения 4-кратных составляют 1, 2, 9 и 17 соответственно.

Затем MySQL блокирует AHI следующим образом:fold % 8Возьмем по модулю:

• После взятия по модулю 1 и 2 получается 0. Следовательно, запрос, соответствующий этим двум сверткам, строит AHI в HashTable[0], и в то же время добавляет ту самую блокировку Lock0.
• По модулю 9 и 17 получается 1. Следовательно, запрос, соответствующий этим двум сверткам, строит AHI в HashTable[1] и одновременно добавляет ту самую блокировку Lock1.

Таким образом, MySQL может распределять блокировки на разные HashTable, чтобы свести к минимуму проблемы с производительностью, вызванные блокировками конструкции HashTable, вызванными параллелизмом.

Тюнинг AHI

MySQL по умолчанию включает AHI, так как мы знаем, что MySQL разбивает блокировки AHI на несколько HashTable по модулю fold, а это означает, что чем больше HashTable разбивается, тем больше разбивается блокировок AHI, и степень детализации блокировок выше. лучше.

Поэтому MySQL оставляет нам параметр для более тонкой детализации блокировки, который называетсяinnodb_adaptive_hash_index_parts: количество осколков HashTable, по умолчанию 8.

Нам нужно только выполнить следующую инструкцию, чтобы увеличить этот параметр и более точно разбить детализацию блокировки:

set global innodb_adaptive_hash_index_parts=16;

резюме

В этой главе Xiao K подробно объясняет принципы структуры AHI, запроса, строительства и блокировки. В то же время он предоставляет методы настройки параметра AHI.

Теперь отвечая на вопросы с самого начала статьи: почему MySQL называется этим Hashtable Adaptive Hashi?

В процессе построения AHI мы обнаружили, что узлы в ячейках, построенных несколькими запросами, могут быть увеличены или уменьшены, именно по этой причине MySQL называет такой HashTable AHI, то есть адаптивным хеш-индексом.

мыслительные вопросы

Наконец, оставьте вопрос для размышления: в части текста «Построение AHI» я упомянулup_matchиlow_matchатрибут, мы можем, очевидно, передать условие запроса>или<судитьleft_sideЭто правда или ложь, зачем проходитьup_matchиlow_matchсудить?

Совет: подумайте об этом в сочетании со сценариями запроса индекса с несколькими столбцами.

Наконец, Сяок стремится подробно объяснить сложную технологию.Даже если вы не в этой области, я надеюсь, что вы что-то получите.Если вы считаете, что статья неплохая, не забудьте поставить лайк и подписаться~~

Если вам что-то непонятно, спрашивайте в комментариях~