Введение. В современном мире существует большое количество задач, в рамках которых приходится обрабатывать большие массивы однотипных данных. Яркими примерами являются системы для анализа биржевых котировок, погодных условий, статистики сетевого трафика. Многие из этих систем используют различные реляционные базы данных, в таблицах которых содержатся такие объемы данных, что правильное составление и оптимизация запросов к этим таблицам становится просто необходимым для нормального функционирования системы. В этой статье описаны методы решения ( и сравнительные временные характеристики используемых методов ) нескольких задач по получению данных из таблиц СУБД MySQL, содержащих статистику о проходящем через маршрутизаторы одного из крупных российских сетевых провайдеров сетевом трафике. Интенсивность потока данных, поступающего с главного маршрутизатора такова, что ежесуточно в таблицы базы данных используемой системы мониторинга сетевого трафика поступает в среднем от 400 миллионов до миллиарда записей, содержащих информацию о транзакциях TCP/IP (рассматриваемый маршрутизатор экспортирует данные по протоколу netflow). В качестве СУБД для системы мониторинга используется MySQL.
Использование баз данных. Запросы в теории реляционных баз данных базируются на концепции операций над множествами, а в теории множеств концепция времени отсутствует. В действительности же всё иначе: СУБД реализуют абстрактные концепции на базе реального оборудования. В результате выполнение запросов требует много (иногда чрезвычайно много) времени, и не всегда есть возможность ждать длительное время, поэтому проблема поиска путей ускорения применяемых запросов стоит достаточно остро — благо, эти пути существуют. Один из основных и наиболее часто применяемых способов – индексирование таблиц, позволяющее ускорить их просмотр. Другой способ – создание запросов, оказывающих влияние на механизм планирования, позволяющий запросам различных клиентов взаимодействовать более эффективно. Также существует возможность модифицировать настройки аппаратной части, позволяющие повысить производительность, обойдя физические ограничения, присущие тому или иному типу оборудования.
Работа с индексами. Таблица, в который нет индексов, представляет собой беспорядочный набор строк, и для поиска нужной записи, допустим по id, необходимо проверить все ее строки на совпадение с искомым значением, для этого нужно просканировать всю таблицу от начала до конца. Это может занять много времени и будет исключительно неэффективно, особенно если таблица содержит только несколько записей, удовлетворяющих условию поиска.
В качестве примера рассмотрим таблицу, содержащую подведомственные рассматриваемому интернет-провайдеру организации. В данном контексте в таблице присутствует два поля – id организации (org_id) и название организации (org_name).
Допустим, мы добавили индекс на поле org_id (см. Рис. 1 ). Индекс содержит запись о каждой строке из таблицы, и записи индекса отсортированы по значению org_id. Теперь вместо сканирования всех записей в таблице мы можем воспользоваться индексом. Предположим, что требуется найти строку, содержащую запись об организации (Институт автоматики и электрометрии СО РАН), у которой уникальный идентификатор (org_id) равен 2. Сканирование по индексу возвращает одну строку. Значения в индексе отсортированы по возрастанию, поэтому достижении следующего значения (с org_id равным 3) можно завершать сканирование: после 3 мы уже не найдем нужных значений. В случае, если искомые значения находятся где-то посередине таблицы, с помощью специальных алгоритмов (например, методом бинарного поиска) можно перейти к нужной строке без длительного линейного сканирования таблицы.
Рис. 1. Взаимодействие с таблицей, с использованием индекса
В целом, большинство запросов можно оптимизировать, если правильно создать нужные индексы в таблице и построить запрос так, чтобы они эффективно использовались. Однако существуют такие запросы, скорости выполнения которых отнюдь не помогают индексы — например, в случае, когда по индексу выбирается больше чем около 1/10 всех записей в таблице, оптимизатор предпочтет FTS (Full Table Scan) вместо использования индекса, поскольку последовательное чтение с диска происходит быстрее, чем читать из разных частей диска (передвижение головки по диску — seek — это “дорогая” операция). Оптимизатор можно “заставить” использовать индекс, используя опцию FORCE INDEX, но это обычно не даёт выигрыша в скорости. Также таблицы могут быть такого большого размера, что создание индекса будет непрактичным с точки зрения занимаемого объема или длительности выполнения операции. Кроме того, за удобство использования индексов приходится определенным образом “расплачиваться”, у индексов есть свои недостатки. В большинстве своем они незначительны, но о них стоит знать.
Недостатки использования индексов. Во-первых, индексы ускоряют поиск данных, но замедляют операции добавления, удаления и модификации данных в индексируемых столбцах, поскольку при каждом изменении данных в такой таблице приходится перестраивать индекс. Взаимосвязь тут простая: чем больше индексов имеет таблица, тем больше замедление операций над записями.
Во-вторых, индексный файл занимает определенное место на диске (нередки случаи, когда индексы занимают больше места, чем сами данные). При создании большого количества индексов, размер такого индексного файла может быстро достичь максимального размера. Это может стать причиной достижения предельного размера таблицами быстрее, чем это было бы без использования индексов.
- Для таблиц типа MyISAM излишнее индексирование таблиц может привести к достижению индексным файлом его максимального размера быстрее, чем файлом данных ( проблему можно решить с помощью PARTITIONING).
- Таблицы типа BDB хранят данные и индексы в одном файле. Это, безусловно, является причиной более быстрого достижения максимального размера табличным файлом.
- Таблицы типа InnoDB размещаются в едином табличном пространстве. При добавлении индексов дисковое пространство, отведенное под табличное пространство, будет исчерпано быстрее.
Пользовательские переменные. MySQL поддерживает пользовательские переменные (далее в тексте ПП), начиная с версии 3.23.6. Переменным можно присваивать значения, и обращаться к ним позже — это можно также использовать, когда есть потребность сохранить результаты вычислений для использования в дальнейших запросах.
Например, для того, чтобы найти изделия с минимальной ценой, можно выполнить следующие действия:
SELECT @min_price:=MIN(price) FROM shop;
SELECT * FROM shop WHERE price=@min_price;Пользовательские переменные записываются как @var_name, и могут принимать значения целого (int), дробного (real) и строчного (string) типа. Присваивание переменной значения производится через оператор SET (SET @var1='RUS'), через оператор SELECT (SELECT 'RUS' INTO @var1;) или в ходе выполнения запроса через оператор “:=” (“=” трактуется как равенство) (@var1:=72).
Неинициализированная переменная принимает значение NULL.
Необходимо инициализировать переменные до выполнения запроса, так как иначе тип переменных определится в процессе выполнения самого запроса, а определится он может некорректно, в результате будет получен неверный результат. Пример, обсуждение.
Преимущества использования ПП. Возможность сохранять промежуточные результаты в переменных и оперировать им по ходу дальнейшего выполнения запроса позволяет значительно ускорить выполнение некоторых запросов (за счет меньшего количества сканирований таблицы), а также позволяет выполнять такие запросы, которые в стандартной реляционной модели реализуются очень сложно или вовсе не реализуются.
Недостатки использования ПП.
- Сложная переносимость на другие СУБД (механизм ПП служит определенной надстройкой над реляционной моделью баз данных в рамках СУБД MySQL). Впрочем, данный недостаток не очень критичен, поскольку на данный момент все крупные СУБД имеют свои отклонения от стандарта ANSI SQL.
- Поведение пользовательских переменных будет зависеть от порядка выполнения сложного запроса, который может меняться оптимизатором MySQL (если не используется оператор STRAIGHT_JOIN).
Пример №1. Одной из важных задач в мониторинге сетевого трафика является фиксация пиков загрузки предоставляемых каналов связи от поставщиков интернета (см. Рис. 2).
Рис. 2. График, отображающий динамику загрузки канала
Система мониторинга сохраняет информацию о входящем и исходящем трафике целиком, и в частности, по каждому из каналов в отдельных таблицах. Тип таблицы – MyISAM.
Упрощенная форма таблицы такого типа:
| t (временная метка) | src (количество отданных байт) | dst (количество принятых байт) |
Для поиска максимального скачка входящего (также как и исходящего, но в этом случае идёт работа с полем src) трафика необходимо просканировать всю таблицу, при этом сравнивая значения поля dst, соответствующие меткам tprev (временная метка на предыдущем шаге ) и tcurr (временная метка на текущем шаге). В этом и состоит основная сложность: в рамках реляционной модели невозможно запомнить предыдущее значение в процессе сканирования таблицы и использовать его напрямую. Его можно вычислить с помощью подзапроса
SELECT dst FROM t t2 WHERE t2.t<t1.t ORDER BY t2.t DESC LIMIT 1;где t1.t – текущее значение временной метки), но такая конструкция сильно усложняет запрос, в общем случае сложность запроса с O(n) увеличивается до O(n2) (из-за того, что приходится для каждой временной метки вычислять предыдущую путём сканирования всей таблицы), что сильно сказывается на скорости выполнения запроса. В случае наличия в таблице уникального индекса на поле t, вычисление будет проводиться значительно быстрее, но это тогда, когда точно известно, что в таблице нет пропущенных временных меток (а такая идеальная ситуация практически не встречается), и предыдущая временная метка вычисляется просто вычитанием нужного интервала из текущей (по уникальному индексу выборка проходит очень быстро). В общем же случае значение временной метки на предыдущем шаге приходится вычислять подзапросом, основанным не на строгом равенстве, а на нестрогом, используя сортировку, и такой запрос, естественно, работает значительно дольше. В реляционном варианте в подзапросе для более быстрой выборки данных требуется индекс на поле t, а во внешнем запросе идёт работа с полем dst, поэтому в данном случае в таблице создан составной индекс t_dst на поля (t, dst).
Вариант запроса в рамках реляционной модели БД:
SELECT MAX(t1.dst-(SELECT dst FROM t t2 WHERE t2.t<t1.t ORDER BY t2.t DESC LIMIT 1)) FROM t t1;Как видно из запроса, приходится приходить по таблице n + 1 раз. пользовательские переменные позволяют реализовать такой запрос за один проход по таблице. для того чтобы запрос, который осуществляет один проход по таблице сработал корректно, необходимо, чтобы данные выбирались в порядке возрастания временной метки.
этого можно достичь следующими путями.
- Отсортировать данные в таблице (если это требуется) запросом
ALTER TABLE `t` ORDER BY `t`(для таблиц типа MyISAM – рабочее решение) до выполнения запроса. В случае, если данные были вставлены последовательно, но из таблицы было удалено несколько записей, нужно дефрагментировать таблицу запросомOPTIMIZE TABLE `t`. Поскольку данные отсортированы заранее, то в запросе применяется инструкцияIGNORE INDEX(t_dst), чтобы данные выбирались не по индексу, а последовательно. - Наличие составного индекса на выбираемые (используемые в WHERE/ORDER BY/GROUP BY) поля позволяет выбирать по нему (по индексу) данные – то есть в порядке возрастания выбираемого поля. В данном случае наличие составного индекса t_dst на поля (t,dst) обеспечивает выборку данных в порядке возрастания метки t. Для того чтобы оптимизатор обязательно использовал индекс при выборке, нужно применить инструкцию
FORCE INDEX(t_dst). - Выбирать данные не из таблицы t, а из созданной из нее динамической выборки, отсортированной по полю t по возрастанию (
SELECT * FROM `t` ORDER BY `t`).
Возможность выбрать данные за один проход основана на том, что есть возможность запомнить значение столбца dst на предыдущей строке таблицы в пользовательскую переменную и сравнить его со значением dst на текущей строке таблицы.
Запрос, работающий с таблицей, где данные расположены в нужном порядке.
SET @data=NULL, @next_data=NULL, @max_value=0;
SELECT @next_data:=`dst` `nextdata`,IF (@next_data- @data>@max_value, @max_value:=@next_data-@data, @max_value), @data:=dst FROM `t` IGNORE INDEX(t_dst);
SELECT @max_value;Запрос, выбирающий данные в нужном порядке по индексу:
SET @data=NULL, @next_data=NULL, @max_value=0;
SELECT @next_data:=`dst` `nextdata`,IF (@next_data- @data>@max_value, @max_value:=@next_data-@data, @max_value), @data:=dst FROM `t` FORCE INDEX(t_dst);
SELECT @max_value;Запрос, сортирующий данные в процессе выборки:
SET @data=NULL, @next_data=NULL, @max_value=0;
SELECT @next_data:=`dst` `nextdata`, IF (@next_data - @data > @max_value, @max_value:=@next_data-@data, @max_value), @data:=dst FROM (SELECT * FROM `t` ORDER BY t) t1;
SELECT @max_value;В таблице 1 приведены длительности выполнения запросов (при разном количестве строк в таблице). Количество строк в таблице определяется длительностью интервала. В данном случае рассматриваются интервалы длительностью в одну минуту.
| Период | Количество строк | Реляционный вариант запроса | Запрос с ПП (последовательная выборка) | Запрос с ПП (сортировка в процессе выполнения) | Запрос с ПП (сортировка осуществляется за счет выборки по индексу) |
| 1 день | 1,440 | 2,67 сек | 0.00 сек | 0.00 сек | 0.00 сек |
| 1 неделя | 10,080 | 2 мин 11 сек | 0.00 сек | 0.01 сек | 0.02 сек |
| 1 месяц | 43,200 | 40 мин 1 сек | 0.02 сек | 0.04 сек | 0.07 сек |
| 1 год | 525,600 | Более трёх суток | 0.54 сек | 0.68 сек | 0.94 сек |
Таблица 1. Измерения длительностей выполнения запросов из примера №1.
Результаты измерений длительностей выполнения запросов подтверждают то, что реляционный вариант запроса в данном случае абсолютно неприменим, а все варианты запросов с пользовательскими переменными выполняются быстрее чем за секунду, что в большинстве случаев приемлемо.
Пример №2. Для анализа загрузки канала регулярно приходится оценивать загрузку за определенные временные промежутки (по несколько секунд, несколько минут). В данном случае выбран интервал с длительностью 5 секунд. Структура таблицы, из которой выбираются данные — такая же, как в примере №1, временная метка t должна иметь тип TIMESTAMP.
Реляционным запросом такая выборка реализуется через группировку с последующей сортировкой результатов:
SELECT `t`-INTERVAL(UNIX_TIMESTAMP(`t`)%5) SECOND AS s5,SUM(`dst`) AS `d` FROM `t` GROUP BY s5 ORDER BY `tПомимо полного прохода по таблице в данном запросе еще реализуется группировка и сортировка результатa.
Тот же запрос можно реализовать через пользовательские переменные с меньшей нагрузкой за счет отсутствия явной группировки, и, следовательно, сортировки (при условии, что в таблице нет пропущенных временных меток).
Запрос, работающий с таблицей, где данные расположены в нужном порядке:
SET @c:=0;
SELECT `t`, `dst` FROM ( SELECT `t`, IF(UNIX_TIMESTAMP(`t`) % 5, @c := @c+`dst`, @c := `dst`) AS `dst`, IF ((UNIX_TIMESTAMP(`t`) + 1) % 5, 1,0) AS `mark` FROM `t` IGNORE INDEX(`t_dst`)) t1 WHERE mark = 0;Запрос, выбирающий данные в нужном порядке по индексу:
SET @c:=0;
SELECT `t`, `dst` FROM ( SELECT `t`, IF(UNIX_TIMESTAMP(`t`) % 5, @c := @c+`dst`, @c := `dst`) AS `dst`, IF ((UNIX_TIMESTAMP(`t`) + 1) % 5, 1,0) AS `mark` FROM `t` FORCE INDEX(`t_dst`)) t1 WHERE mark = 0;Запрос, сортирующий данные в процессе выборки:
SET @c:=0;
SELECT `t`, `dst` FROM ( SELECT `t`, IF(UNIX_TIMESTAMP(`t`) % 5, @c := @c+`dst`, @c := `dst`) AS `dst`, IF ((UNIX_TIMESTAMP(`t`) + 1) % 5, 1,0) AS `mark` FROM ( SELECT * FROM `t` ORDER BY `t`) t1) t2 WHERE mark = 0;В рамках выполнения подзапроса сперва идёт суммирование в переменную @c, и в случае, если временная метка соответствует пятисекундному интервалу, то обнуляется счетчик и метке markприсваивается значение 1. Далее внешний запрос выбирает те строки, у которых mark равен 1, то есть искомые.
В таблице 2 приведены длительности выполнения запросов (при разном количестве строк в таблице).
| Период | Количество строк | Реляционный вариант запроса | Запрос с ПП (последовательная выборка) | Запрос с ПП (сортировка в процессе выполнения) | Запрос с ПП (сортировка осуществляется за счет выборки по индексу) |
| 1 день | 86,400 | 0.11 сек | 0.05 сек | 0.1 сек | 0.08 сек |
| 1 неделя | 604,800 | 0.86 сек | 0.33 сек | 0.73 сек | 0.6 сек |
| 1 месяц | 2,592,000 | 33.72 сек | 1.65 сек | 3.62 сек | 2.83 сек |
| 1 сезон (3 месяца) |
7,776,000 | 2 мин 45 сек | 4,87 сек | 10.46 сек | 8.36 сек |
Таблица 2. Измерения длительностей выполнения запросов из примера №2
Как и в первом примере, приведенные варианты запросов с использованием пользовательских переменных MySQL работают в несколько раз быстрее.
Пример №3. С точки зрения работы сети подведомственные организации описываются определенными техническими характеристиками, в частности, выделенными для организации диапазонами IP-адресов. Иногда возникает потребность вычленить самые крупные непрерывные блоки IP-адресов, выделенные для организации.
Таблица организаций и их сетевых диапазонов (nets) представлена следующим образом:
| org_id (id организации) |
org_name (название организации) |
net (адрес сети, 4 байта) |
net (маска сети, 4 байта) |
В случае, если нужно выбрать самый крупный непрерывный сетевой диапазон у каждой организации, особых сложностей нет. Но если необходимо выбрать по два самых крупных сетевых диапазона – реляционный вариант запроса на выборку становится достаточно сложным – необходимо для каждого диапазона посчитать количество более крупных сетевых диапазонов, после отсеять те, которые меньше первых двух (подробнее см. здесь).
Вариант запроса в реляционной модели:
SELECT
t1.org_id,
t1.org_name,
(SELECT
count(*)
FROM
`nets` t2
WHERE
t2.org_id = t1.org_id AND ((t2.mask<<32)+t2.net) < ((t1.mask<<32)+t1.net)
) c,
inet_ntoa(t1.net),
inet_ntoa(t1.mask)
FROM
nets t1
HAVING
c<2
ORDER BY
org_id, mask;
С помощью пользовательских переменных можно в рамках одного прохода подсчитывать количество выведенных сетевых диапазонов и обнулять счетчик при смене организации. В случае, если счетчик достигает нужного значения (в данном случае 2), записи не выводятся. Саму таблицу перед использованием нужно отсортировать по размерам сетевых диапазонов в рамках организации.
Вариант запроса с пользовательскими переменными MySQL:
set @i=0, @p=0;
SELECT
t.org_id,
t.org_name,
inet_ntoa(t.net), inet_ntoa(t.mask)
FROM
( SELECT * FROM `nets` ORDER BY `org_id`, `mask` ) AS t
WHERE
( (if (@p=org_id, @i:=@i+1,(@i:=0) or (@p:=org_id))) and @i<2);Большая эффективность запроса с ПП истекает из того, что в реляционном варианте запроса присутствует подзапрос, который обрабатывает каждую запись в таблице.
Пример №4. В предыдущих экспериментах ни разу не рассматривался вариант модификации структуры таблицы (в реальной жизни далеко не всегда ее можно или удобно менять). Однако при работе с темпоральными таблицами просто напрашивается решение сделать еще одну колонку, которая будет содержать предыдущее значение prev измеряемого параметра. Для наиболее высокой скорости поиска максимального перепада значении можно добавить поле, которая будет содержать разницу diff между текущим значением измерения d и предыдущим.
Рассмотрим вариант изменения структуры таблицы – добавление колонки prev. Исходная таблица с данными такова:
| t (временная метка) | d (данные измерения) |
Таблица не содержит индексов и первичного ключа – при наличии индекса на поле t или составного индекса на поля (t,d) реляционный вариант запроса работает значительно медленнее.
Вариант модификации в рамках реляционной модели БД:
CREATE TABLE `t_modifyed` SELECT t, (SELECT `d` FROM `t` `in` where `in`.t < `out`.`t` order by t desc limit 1 ) prev, d FROM `t` `out` ORDER BY `t`;Вариант модификации с использованием пользовательских переменных:
set @v = NULL; CREATE TABLE `t_moifyed` SELECT t, @v prev, @v:=d d FROM `t` ORDER BY `t`;В таблице 3 приведены длительности выполнения запросов (при разном количестве строк в таблице).
| Период | Количество строк | Реляционный вариант запроса | Запрос с ПП (последовательная выборка) | Запрос с ПП (сортировка в процессе выполнения) |
| 1 день | 1,440 | 0.35 сек | 0.00 сек | 0.00 сек |
| 1 неделя | 10,800 | 12.33 сек | 0.00 сек | 0.01 сек |
| 1 месяц | 43,200 | 3 мин 45 сек | 0.10 сек | 0.15 сек |
| 1 год | 525,600 | более 5 часов | 0.54 сек | 0.96 сек |
Таблица 3. Измерения длительностей выполнения запросов из примера №4.
Другие способы применения. Многие реляционные СУБД позволяют в ходе выполнения запроса использовать номер текущей строки вывода.
- Oracle (переменная: rownum)
- Microsoft SQL (функция ROW_NUMBER())
- PostgreSQL (функция ROW_NUMBER())
В MySQL rownum можно корректно эмулировать только с помощью пользовательских переменных:
set @n:=0;
select @n:=@n+1 as rownum, t.* from t;Строго говоря, в MySQL нет небходимости использовать rownum: для ограничения количества возвращаемых запросом строк существует инструкция LIMIT, но иногда может потребоваться.
Вывод. Использование пользовательских переменных в определенном типе запросов позволяет добиться большей скорости при выполнении запросов, чем в их реляционных аналогах. Это может возникать в тех случаях, если:
- запрос таков, что не может эффективно использовать индексы (количество выбранных значений по индексу чересчур велико и оптимизатор делает FTS);
- в ходе выполнения запроса используются вычисленные на предыдущих шагах и занесенные в пользовательские переменные значения.
Аналогичная возможность в других реляционных СУБД. Механизм, аналогичный механизму пользовательских переменных имеется почти во всех современных реляционных СУБД. В данном разделе приведены примеры для PostgreSQL и Microsoft SQL. В случае использования функций, приведенных ниже необходимо учитывать то, что при их создании не были предприняты никакие действия для того, чтобы строки выбирались из таблицы в нужном порядке (по возрастанию метки t ).
PostgreSQL: СУБД PostgreSQL не поддерживает возможность использовать пользовательские переменные в процессе выполнения запроса. Но начиная с версии 9.0 в PostgreSQL есть возможность создавать анонимные блоки кода. К сожалению, они не поддерживают формальных параметров и не возвращают значений. Однако есть возможность создать функцию в схеме pg_temp, что обеспечит автоматическое удаление функции из схемы по завершении сессии. Пример функции, вычисляющей максимальный перепад:
DROP FUNCTION IF EXISTS pg_temp.max_drop();
CREATE FUNCTION pg_temp.max_drop() returns int as $$
DECLARE
prev INTEGER; curr INTEGER; max_ INTEGER;
begin
max_ := 0; prev := 0;
FOR curr IN SELECT d FROM pogoda
LOOP
IF (curr - prev > max_) THEN max_ := curr - prev; END IF;
prev := curr;
END LOOP;
RETURN max_;
end
$$ lANGUAGE plpgsql;Microsoft SQL: Основное отличие запроса от запроса с использованием ПП MySQL в том, что у переменной нужно задавать тип заранее.
DECLARE @diff int;
DECLARE @prev int;
set @diff = 0;
set @prev = 0;
select @diff = case when @diff> (d-@prev) then @diff else (d-@prev) end, @prev = d from npogoda;
select @diff;Oracle: на момент написания этой статьи в языке Oracle SQL отсутствует возможность использовать пользовательские переменные — такая возможность имеется лишь в языке PL/SQL и таких расширениях, как SQLPLUS, Oracle XE, и. т. д.