Введение В настоящее время очень популярна тема оптимизации работы с различными СУБД.
На многочисленных форумах идут дискуссии о «лучшей СУБД в мире», но зачастую все это превращается в голословные вопли о том, что «я познал смысл жизни и понял, что лучшее хранилище данных — это Х».
Да, конечно, сейчас мы видим активное развитие NoSQL-решений, которые позволяют нам многое.
Но эта статья не о них.
Так получилось, что я сменил работу и получил один очень интересный проект на связке php+MySQL. В нем много хороших решений, но он не был написан для большой аудитории.
За несколько лет существования количество активных пользователей стало приближаться к цифрам с 7 нулями.
Поскольку проект представляет собой своего рода социальную сеть с элементами игры, таблица с пользователями получилась не самой «тяжелой» из всех.
Мне достались по наследству таблицы с десятками миллионов элементов пользователей, личных сообщений, записей биллинга и т. д. Проект начали рефакторить, разбили на несколько серверов и добились значительных результатов.
Сейчас все стабильно.
Но недавно мне прислали по электронной почте новое задание.
Целью было собрать статистику.
Проанализировав требования, я понял, что для его реализации достаточно написать один-единственный запрос, выполняющий 3 INNER JOIN над таблицами, размеры которых были впечатляющими.
Каждая таблица содержала в среднем 40 миллионов записей.
Получается, что временная таблица будет состоять из 4*4*4*10^21 = 64*10^21 записей.
Это колоссальная цифра.
А загружать СУБД таким запросом для сбора статистики – непозволительная роскошь.
Далее, собственно, я хочу представить решение этой абстрактной проблемы, которая пришла мне в голову, когда я вспоминал уроки информатики на первом курсе университета.
(в проекте используется СУБД MySQL, но особенностей алгоритм не имеет)
Что такое двоичный поиск
Я думаю, что многие из вас писали лабораторные работы по поиску элемента в массиве с помощью бинарного алгоритма.Попробую кратко изложить ее суть.
Пусть у нас есть отсортированный массив н элементы: Первый элемент массива = 1 Последний элемент массива = n Нам нужно найти индекс элемента со значением ж .
Каждый шаг заключается в том, что мы вычисляем середину массива: Середина массива = раунд (первый элемент + последний элемент)/2 Затем вычисляем значение этого элемента и проверяем, больше или меньше полученное значение желаемого.
ж .
Диапазон поиска сокращается в 2 раза: Если > е, тогда Последний элемент массива = среднее значение В противном случае Первый элемент массива = среднее значение Эти шаги повторяются до тех пор, пока не произойдет одно из следующих условий:
- Модуль разницы между значениями среднего и ж меньше, чем некоторые эпсилон (где эпсилон, какая-то ошибка)
- Количество итераций превысило значение log2 (количество элементов в массиве)
Таким образом, мы существенно ускоряем поиск искомого элемента за счет сокращения диапазонов поиска, но жертвуем некоторой точностью вычислений (для статистики это не критично, если не учтена пара элементов из миллионов.
В противном случае необходимо сделать эпсилон нулевым и завершить поиск только после достижения последнего дерева уровня).
Перейдем к практике
Допустим, нам нужно выполнить INNER JOIN для трех таблиц, а затем установить условие «столбец Икс в диапазоне от 10 до 20".При этом столбец Икс не имеет индекса.
Это займет очень много времени.
Вот тут-то и приходит на помощь этот простой метод. Берем таблицу с этим самым столбцом и с помощью бинарного поиска находим по ней диапазон первичных ключей, удовлетворяющих условию 10<= Икс <=20. Considering that for such a sample we will use only indices, we will very soon get the desired pair of values. Стоит сказать, что двоичный поиск используется для поиска одного элемента, а не диапазона, но никто не мешает нам найти первый элемент со значением 10 и последний элемент со значением 20. Их первичными ключами будут ограничения по диапазону.
С этим диапазоном мы возвращаемся к нашему запросу, но теперь вместо условия ГДЕ x > = 10 И x <= 20 мы пишем ГДЕ id_x МЕЖДУ min_id_x И max_id_x , Где min_id_x И max_id_x — значение нижней и верхней границ диапазона, удовлетворяющее условию.
Что получаем: теперь делаем выборку не по определенному столбцу Икс , но по первичному ключу.
Время, потраченное на обход одной таблицы, экономится.
Аналогичную процедуру можно провести и с другими условиями в запросе.
Я не вижу смысла приводить здесь код, потому что.
код двоичного поиска можно найти в Википедии, но в самом запросе нет ничего сверхъестественного.
выводы
Этот алгоритм позволяет перенести условия из полей без индексов в первичные ключи, что существенно ускоряет запрос.Но метод нельзя считать панацеей.
Во-первых , сложно подготовить универсальное решение для всех запросов.
В любом случае придется учитывать детали реализации конкретной таблицы и, как следствие, каждый раз тратить время на оптимизацию.
Во-вторых , этот метод подходит не для всех решений, так как строки в таблице должны быть отсортированы в каком-то порядке.
Теги: #MySQL #базы данных #бинарные деревья #оптимизация #Алгоритмы #MySQL
-
Сделать Свою Прошивку Для Nokia 5530
19 Oct, 24 -
Почему Люди Победят Киборгов
19 Oct, 24 -
«Анализ Данных В Python» В Двух Частях
19 Oct, 24
