Использование статистики для оптимизации запросов
Что произошло до сих пор?
Этот пост является частью серии блогов о ходе написания оптимизатора запросов для Hyrise, исследовательской базы данных, ориентированной на столбцы основной памяти.
До сих пор мы писали о:
За последние недели мы провели довольно много исследований о том, как работают другие оптимизаторы запросов, какие из их стратегий применимы и будут полезны для Hyrise, а также как наш оптимизатор может использовать концепции, характерные для Hyrise, для дальнейшего улучшения планов запросов.
В качестве общей темы, мы заметили несколько вещей:
- Оптимизаторы запросов в значительной степени полагаются на оценки селективности.
- Оценки селективности основаны на статистике распределения ценности.
- Эта статистика часто неверна.
В результате оценки также часто оказываются неверными. Это можно объяснить двумя основными причинами. Во-первых, изменение операций с данными изменяет распределение значений. Обновление статистики при каждом изменении влечет за собой значительные затраты и поэтому обычно не используется в других базах данных.
Во-вторых, оценки обычно рассчитываются на основе определенных предположений о данных. Самое главное, одно предположение состоит в том, что значения двух столбцов не зависят друг от друга. Однако это часто неверно для реальных данных. Например, модель автомобиля не зависит от производителя (не каждый производитель предлагает все модели).
К сожалению, из-за отсутствия альтернатив статистика — это почти все, что у нас есть, и мы используем ее как можно лучше. может. Как будто Эндрю Лэнг думал о нас, когда писал:
«Он использует статистику, как пьяный человек использует фонарные столбы —
для поддержки, а не для освещения».
— Эндрю Лэнг
Поддержка поиска оптимального планирования запросов
Внедрение статистики в Hyrise
Для уменьшения сложности мы решили отделить реализацию статистики от оптимизатора и инкапсулировать ее. Цель состоит в том, чтобы иметь возможность предсказать размер вывода любого из операторов Hyrise. Мы придерживаемся концепции цепочки операторов, которая позволяет нам использовать прогнозируемый результат для одного оператора в качестве входных данных для следующего прогноза для следующего оператора.
Чтобы проиллюстрировать это, мы рассмотрим запрос SELECT, который возвращает заказы клиента с идентификатором 8169 за 2017 год. В таблице содержится 1 000 000 заказов 10 000 клиентов за последние 25 лет. Мы предполагаем равномерное распределение стоимости. Чтобы получить ожидаемый размер вывода нашего запроса, необходимо выполнить три шага:
- Сначала извлеките количество записей в таблице заказов: 1 000 000.
- Затем предскажите, сколько из, например, 1 000 000 заказов поступило от клиента с идентификатором 8169:100.
- Наконец, используя промежуточный результат 100 заказов, спрогнозируйте количество заказов с 2017 года: 4.
Теперь, когда мы знаем, как оптимизатор использует компонент статистики, мы рассмотрим, как работает предсказание размера результата.
Типичными вариантами использования статистики являются вычисление ожидаемых выходных размеров для предикатов и соединений. Эти размеры зависят только от значений в отфильтрованных столбцах, соответственно от столбцов, используемых условием соединения. Поэтому статистика рассчитывается по столбцам. Статистика столбца включает в себя количество различных элементов, а также минимальное и максимальное значения столбца. Статистика столбца представляет собой либо базовую статистику столбца, вычисленную с использованием фактических значений столбца, либо отфильтрованную статистику столбца. Эта отфильтрованная статистика вычисляется с использованием значений фильтра, операнда фильтра и соответствующей статистики столбца. Наша текущая реализация вычисляет статистику базового столбца по запросу, а затем кэширует ее. Этот подход не обновляет уже вычисленную статистику для вставок, обновлений или удалений. Вся статистика столбца таблицы вместе с размером таблицы является частью статистики таблицы. Статистические данные таблицы со статистикой отфильтрованных столбцов описывают результаты промежуточного оператора и поэтому не кэшируются. Оптимизатор ожидает табличную статистику и считывает из нее только размер таблицы.
Промежуточные результаты должны быть как можно меньше
Предикатный порядок
Одной из основ оптимизации запросов является стремление сократить количество обрабатываемых данных как можно раньше и в максимально возможном объеме, поскольку меньшее количество данных позволяет ускорить обработку.
Чем меньше, тем лучше, если вы не Эл Гор.
— Джефф Рич
Прямой подход к уменьшению объема данных заключается в оптимизации порядка выполнения TableScan в одной и той же таблице. В настоящее время в Hyrise мы выполняем TableScans одно за другим. В результате, если первый фильтр уже значительно уменьшает объем данных, второму фильтру нужно проверять меньшее количество значений. Рассмотрим следующий простой запрос, который извлекает общую сумму всех заказов для данного клиента в этом году:
Чтобы решить, какой из двух фильтров мы применяем первым, нам нужно подумать об их избирательности. С помощью статистики, которую мы собираем о столбцах, мы можем оценить, сколько значений мы ожидаем в результате операции фильтра.
В данном примере базовые данные, вероятно, содержат больше строк, соответствующих первому фильтру, чем второму. . То есть, вероятно, в текущем году заказов было намного больше, чем у одного клиента. Прямо сейчас мы пришли бы к такому выводу, основываясь на количестве различных значений в столбце. Предположим, что в заказах есть 10 000 различных customer_id, мы сохранили заказы за последние 25 лет, и у нас есть 1 000 000 заказов всего. Тогда мы ожидаем получить около 1 000 000 / 25 = 40 000 заказов в 2017 году, но только 1 000 000 / 10 000 = 100 заказов для каждого customer_id. Поэтому мы бы переупорядочили фильтры и сначала выполнили фильтр customer_id.
На сегодняшний день Hyrise может переупорядочивать предикаты равенства, исходя из предположения, что все значения в колонки распределяются равномерно.
Набор правил для их оптимизации
Преобразования на основе правил
Тип преобразований, который мы только что рассмотрели, основан на статистике. Однако существуют также оптимизации на основе правил, которые можно применять независимо от фактических данных. Эти логические преобразования запроса применяются уже много лет и, скорее всего, реализуются любым оптимизатором запросов в этой области.
Простым примером такого логического преобразования может быть упрощение выражений путем свертки констант. Особенно в тех случаях, когда SQL-запросы генерируются во время выполнения, запрос может содержать константные выражения. Мы надеемся, что при оценке такого рода выражений на этапе оптимизации этап выполнения станет дешевле и, следовательно, быстрее.
Рассмотрим следующий запрос, в котором мы можем упростить предикат:
Возможны и более сложные логические преобразования, например. невложенность подзапросов. В SQL подзапросы обычно выполняются независимо от родительского запроса. Таким образом, такие преобразования, как порядок соединений и выбор пути доступа для родительского запроса, не могут включать подзапрос.
Однако существуют правила, которые позволяют удалять вложенные подзапросы, заменяя их эквивалентным соединением. Давайте посмотрим на следующий запрос:
Мы можем преобразовать подзапрос в следующее соединение, если customer.id уникален:
Существуют десятки других правил логического преобразования, таких как расширение OR в UNIONs или разложение на множители. Общим для всех этих правил является то, что они улучшают запрос в основном бесплатно, так как не нуждаются ни в статистике, ни в оценке стоимости.
Традиционно расширение предикатов также является частью набора правил. Однако для Hyrise мы хотим использовать стоимостную модель, чтобы решить, стоит ли опускать предикат, например. через присоединение. Давайте посмотрим на пример, чтобы прояснить это. Обычно вы хотите отфильтровать входные данные соединения, чтобы получить небольшие промежуточные результаты. Но предположим, что у вас есть условие фильтра, которое на самом деле не уменьшает ваш объем данных значительно. Далее предположим, что ваше условие соединения является очень строгим, что дает результат соединения всего с несколькими строками. В этом случае наша модель затрат должна учитывать, что нажатие на предикат фильтра приведет к еще одному дорогостоящему полному сканированию таблицы, которое в любом случае должно выполняться соединением (из-за предиката с низкой селективностью). С другой стороны, сканирование таблицы по результату соединения довольно дешево, и в подобных ситуациях его следует отдавать предпочтение.
Специализированные структуры для задач
Выбор промежуточных представлений запроса
Как описано в предыдущих разделах, существуют различные методы, которые оптимизатор может использовать для создания хорошего плана запроса. В настоящее время мы выделяем три основных этапа: применение набора правил, которые повсеместно приводят к улучшенному плану запроса (например, устранение вложенности подзапросов), использование статистики для изменения порядка частей запроса (например, порядок предикатов) и, наконец, определение хорошего соединения. порядке, если применимо.
Поскольку оптимизатор также отвечает за выбор наилучшего оператора для определенной части запроса, мы хотим смоделировать эти части как можно ближе к структуре оператора. Мы решили преобразовать вывод парсера в бинарное дерево, поскольку все наши операторы (см. наш первый пост в блоге) имеют от нуля до двух входных данных. Мы будем использовать бинарное дерево для первых двух этапов.
Как только они будут завершены, в настоящее время мы планируем использовать структуру графа соединений, предложенную в Vertica, которая сама относится к Starburst, для перечисления возможных порядков соединения и выберите тот, который, как ожидается, будет работать быстрее всего. Эта структура фокусируется на элементах, которые должны быть объединены, и поэтому не обязательно нуждается в дополнительной информации, включенной в двоичное дерево.
Впереди
Дальнейшие шаги
Одной из наших основных задач в ближайшие недели будет реализация представления запроса в виде двоичного дерева, а затем первая оптимизация с использованием этой структуры.
Кроме того, мы продолжим расширять и улучшать как точность, так и производительность статистика, которую мы собираем. Гистограммы будут иметь решающее значение для оценки кардинальности более сложных запросов, и мы считаем их нашей следующей вехой в этой области.
