«Это 15-й день моего участия в ноябрьском испытании обновлений. Подробную информацию об этом событии см.:Вызов последнего обновления 2021 г."
предисловие
Я помню, как однажды шел на собеседование, и интервьюер задал вопрос о базе данных, общее содержание вопроса таково:
Интервьюер: Вы обычно пишете SQL?
Я: Конечно, ты не можешь писать по тысяче строк каждый день.
Интервьюер: Тогда вы знаете, что существует связь между несколькими таблицами данных, как вы проверяете данные?
Я: ПРИСОЕДИНЯЙСЯ.
Интервьюер: Это работает?
Я: Вор прост в использовании, я особенно LEFT JOIN, я использую вора умело и пишу каждый день.
Опрашивающий: Эмм... тогда вернитесь и ждите уведомления.
Я не знаю, сталкивались ли вы с такой проблемой, или как вы обычно работаете с данными, относящимися к нескольким таблицам?Вы также используете оператор JOIN для решения этой проблемы?
Давайте не будем прямо определять, что не так с оператором JOIN, давайте сначала рассмотрим простой пример.
Подготовка тестовых данных
Здесь я использую базу данных mysql.Поскольку тест требует, чтобы мы сначала создали две таблицы t/t2, оператор относительно прост
CREATE TABLE `t` (
`id` int(11) NOT NULL,
`a` int(11) NOT NULL,
`b` int(11) NOT NULL,
PRIMARY KEY (`id`),
KEY `a` (`a`),
KEY `b` (`b`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
CREATE TABLE `t2` (
`id` bigint(19) NOT NULL,
`a` int(11) DEFAULT NULL,
`c` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
Затем используйте функцию для создания некоторых тестовых данных, здесь я создаю их в таблице tдесять миллионов, созданный в таблице t2Десять тысяч.
CREATE DEFINER=`root`@`localhost` PROCEDURE `testdata`()
begin
declare item int;
set item=1;
while(item<=10000000)do
insert into t values(item, item, item);
set item=item+1;
end while;
end
ПРИСОЕДИНЯЙТЕСЬ к тесту
Сначала напишите предложение, которое учащиеся начальной школы могут использовать для его проверки, но здесь мы используемstraight_join, цель состоит в том, чтобы позволить MySQL использовать фиксированное соединение для выполнения запроса, чтобы оптимизатор присоединялся только так, как мы указываем. Это фиксирует, что таблица t является ведущей таблицей (внешняя таблица), а t2 — управляемой таблицей (внутренняя таблица):
select t.*,t2.* from t straight_join t2 on t.a = t2.a
эмм... Я не знаю, как долго я ждал, но это еще не конец, поэтому я добавил ограничение лимита и запрашиваю только 10 фрагментов данных.
select t.*,t2.* from t straight_join t2 on t.a = t2.a limit 10000,10
............ Прошло десять минут, еще одно долгое ожидание, перестаньте ждать и немедленно остановитесь.
Давайте попробуем две таблицы в обратном порядке
select t.*,t2.* from t2 straight_join t on t.a = t2.a limit 1000,10
Скорость очень онемела, это заняло всего 0,01 секунды, и предварительная оценка связана с количеством ведущих столов и ведомых столов.
анализ проблемы
Если вы хотите понять, почему это занимает так много времени, вы должны сначала понять, как реализован процесс запроса, а затем вы можете сделать вывод, можно ли использовать JOIN.
Первый взгляд на план выполнения
Три наиболее важных параметра:
- type: Определите, является ли это полным сканированием таблицы или сканированием индекса, здесь мыALL, то есть полное сканирование таблицы;
- ряды: в процессе нахождения конечного результата количество строк, которые необходимо просмотреть, чем меньше, тем лучше;
- Extra: Дополнительная информация, которая не подходит для отображения в других столбцах, в этом случае мы ориентируемся наBlock Nested Loop, анализ будет продолжен во второй половине этой статьи.
- отфильтровано: количество возвращаемых строк в процентах от количества прочитанных строк, чем больше, тем лучше.
Весь процесс JOIN можно представить как следующие два шага:
- Загрузить все данные таблицы t в память (join_buffer, размер по умолчанию 256k);
- Сканируем таблицу t2, извлекаем каждую строку данных из таблицы t2, сравниваем ее с данными в join_buffer и выясняем, соблюдены ли условияt.a = t2.aстроки для формирования набора результатов.
Описанный выше процесс относительно прост. Соответствующая реализация в JAVA представляет собой двухуровневый цикл for. Первый уровень просматривает данные в таблице t, сравнивает каждую строку данных с данными в таблице t2 и, наконец, получает набор результатов. процессы сравнения находятся в памяти.join_buffer сравнивается, вызывается алгоритмБлокировать вложенный цикл.
временная сложность:
- Количество строк развертки: M+N, M управляет табличными данными, N - управляемыми табличными данными.
- Временная сложность: M*N.
По временной сложности видно, что он потребляет много памяти, например, количество сравнений в этом примере достигает 100 миллиардов раз, что очень трудоемко.
Предварительная оптимизация
Друзья, которые немного разбираются в базе данных, наверное, спрашивали, а почему бы не добавить индекс к полю a в таблице t2, не будет ли быстрее добавить его?
Нет проблем, не будем сначала говорить о принципе, попробуем сначала добавить индекс, а потом посмотрим, сколько времени займет запрос того же sql.
Боже мой, это не одна точка и не две.Теперь на один запрос требуется всего 0,04 с, что почти летит
Давайте еще раз посмотрим на план выполнения:
В это время таблица t все еще является полным сканированием таблицы. Разница в том, что тип в таблице t2 — ref, что означает, что мы используем индекс в это время. Давайте посмотрим на весь процесс выполнения:
- Читать часть данных R из таблицы t;
- Выньте значение поля a из данных R и найдите его в таблице t2;
- По индексу a совпадение удовлетворяет условиюt.a = t2.aСтроки формируют результирующий набор;
- Повторяйте вышеуказанные шаги, пока не будут пройдены все данные в таблице t.
Можно обнаружить, что вышеуказанные шаги по-прежнему имеют двойную вложенность.Первый слой обходит таблицу t, извлекает данные из таблицы t и ищет данные, соответствующие условиям в таблице t2, и, наконец, формирует набор результатов, поскольку индекс ведомой таблицы используется снова. Этот алгоритм называетсяIndex Nested-Loop Join, именуемыйНЛЖ.
Почему добавление индекса происходит так быстро:Условия сопоставления ведущей таблицы напрямую сопоставляются с индексом внутренней таблицы, избегая сравнения с каждой записью ведомой таблицы, так что запрос с использованием индекса сокращает время сопоставления внутренней таблицы и значительно повышает производительность. присоединиться.
временная сложность:
- Временная сложность одного запроса:1 + 2log2N, N — количество строк в ведомой таблице t2.
- Общая временная сложность: M * (1 + 2log2M), M управляет данными таблицы, N управляет данными таблицы, log2M - это сложность поиска дерева, потому что это общий индекс, поэтому при поиске по всем полям текущего дерева вам нужно пройти индекс первичного ключа еще раз, поэтому сложность поиска строки данных 1+ 2*log2M.
Сравнительный анализ алгоритмов JOIN в MySQL
В реализации MySQL есть 3 алгоритма соединения с вложенным циклом:
- Simple Nested-Loop Join
Алгоритм представляет собой вложенный цикл, который считывает данные в ведущей таблице по очереди, и каждый раз сравнивает вынимаемые данные с ведомой таблицей.Например, в этом примере мы гоним данные таблицы (10000000) * ведомая таблица данные (10000) = временная сложность 10000000000 миллиардов раз,Конечно, этот алгоритм не будет использоваться без базы данных..
- Block Nested-Loop Join
Алгоритм заключается в том, что когда мы не добавляем индекс, движок MySQL InnoDB будет использовать этот алгоритм Конкретный процесс такой же, как указано выше, а временная сложность такая же, как и в приведенном выше алгоритме, который составляет M * N, но он оптимизирован ссылаясь на buffer_join.
- Index Nested-Loop Join
Алгоритм заключается в увеличении индекса, MySQL будет использовать алгоритм, конкретный процесс был представлен выше.
Можно ли использовать JOIN
Если мы используем алгоритм Index Nested-Loop Join, он не оказывает большого влияния и полностью удовлетворяет использование большинства сценариев.
Если используется алгоритм блочного соединения с вложенным циклом, это приведет к большому количеству сканируемых строк, особенно к десяткам миллионов или даже сотням миллионов данных в этом примере, что приведет к многократному сканированию управляемой таблицы. крайне не рекомендуется занимать большое количество системных ресурсов и ресурсов кэша.
Что касается вопроса интервьюера, упомянутого в начале, это действительно произошло.Интервьюер хотел, чтобы ответ обрабатывал табличные данные в памяти и запрашивал только одну таблицу при выполнении sql?На самом деле, на этот раз сложность не уменьшается , но это увеличит количество выполнений sql.Я не знаю, как вы его используете?
В следующей главе мы обсудим, как оптимизировать JOIN при их использовании? А что такое кеш (join_buffer) в данном примере и как его можно оптимизировать? И другие эффективные средства повышения эффективности запросов.