Оптимзация запросов в YDB

В YDB используются два типа оптимизаторов запросов: оптимизатор, основанный на правилах, и стоимостной оптимизатор. Стоимостной оптимизатор применяется для сложных запросов, как правило, аналитических (OLAP), а оптимизация по правилам работает на всех запросах.

План запроса представляет собой граф операций, таких как чтение данных из источника, фильтрация потока данных по предикату, а также более сложные операции, например JOIN и GROUP BY. Оптимизаторы в YDB принимают на вход начальный план запроса и преобразуют его в более эффективный план, эквивалентный начальному с точки зрения возвращаемого результата.

Оптимизатор запросов основанный на правилах

Значительная часть оптимизаций в YDB применима практически для любых планов запросов, что устраняет необходимость в анализе альтернативных планов и их стоимости. Оптимизатор, основанный на правилах состоит из набора эвристических правил, которые применяются всегда, когда это возможно. Например, практически в любом запросе полезно отфильтровывать неиспользуемые данные как можно раньше в плане исполнения. У каждого правила оптимизатора есть условия срабатывания и логика переписывания плана. Правила применяются итеративно до тех пор, пока существуют правила, применимые к текущему плану.

Стоимостной оптимизатор запросов

Для более сложных оптимизаций, таких как выбор оптимального порядка джоина и алгоритмов джоинов используется стоимостной оптимизатор. Для каждого запроса стоимостной оптимизатор рассматривает большое количество альтернативных планов выполнения и выбирает из них лучший на основе оценки стоимости каждого варианта. На текущий момент этот оптимизатор работает только с планами, где есть операции JOIN. Он выбирает наилучший порядок исполнения этих операций, а также выбирает самую эффективную реализацию для каждого Join в плане.

Стоимостной оптимизатор состоит из трех основных компонент:

• Модуль перебора порядка соединений;
• Модуль оценки стоимости плана;
• Модуль статистики, на которую опирается оценка стоимости.

Перебор порядка соединений

Текущий стоимостной оптимизатор в YDB перебирает все полезные варианты соединения таблиц с помощью оператора Join, для которых определены условия соединений. Берется исходный план запроса, из которого строится граф соединений. В зависимости от исходного запроса могут получиться разные топологии этого графа, которые существенно влияют на объем множества альтернативных планов, которое требуется сравнить.

Например, вот типичный пример популярной топологии «звезда», где основная таблица фактов соединяется с многочисленными таблицами измерений:

SELECT
    P.Brand,
    S.Country AS Countries,
    SUM(F.Units_Sold)

FROM Fact_Sales F
INNER JOIN Dim_Date D    ON (F.Date_Id = D.Id)
INNER JOIN Dim_Store S   ON (F.Store_Id = S.Id)
INNER JOIN Dim_Product P ON (F.Product_Id = P.Id)

WHERE D.Year = 1997 AND  P.Product_Category = 'tv'

GROUP BY
    P.Brand,
    S.Country

В графе этого запроса все таблицы Dim... соединяются c таблицей фактов Fact_Sales:

К типичным топологиям также относятся «цепочка» и «клика». «Цепочка» - это топология, где таблицы соединены друг с другом последовательно и каждая таблица участвует не более, чем в одном соединении. «Клика» — полностью связанный граф, где каждая таблица соединяется с другой.

На практике в OLAP запросах часто встречается топология, представляющая из себя комбинацию «звезы» и «цепочки», сложные топологии вроде «клики» встречаются очень редко.

Топология сильно влияет на количество альтернативных планов, которые требуется рассмотреть оптимизатору. Следовательно, стоимостной оптимизатор ограничивает количество соединений, которые сравниваются полным перебором, в зависимости от топологии исходного плана. Возможности точной оптимизации в YDB приведены в следующей таблице:

YDB использует модификацию алгоритма DPHyp для перебора порядка соединений. Это самый современный алгоритм динамического программирования для оптимизации запросов. Посредством построения гиперграфов запросов он избегает перебора лишних альтернатив и позволяет оптимизировать планы с операторами JOIN, сложными предикатами, а также с операторами GROUP BY и ORDER BY.

Оценка стоимости планов

Сравнение сложности планов основано на стоимостной функции, которая оценивает ресурсоёмкость каждой операции плана. Основные параметры стоимостной функции — это прогнозы размера входных данных для каждого оператора и размера его результата. Эти прогнозы выполняются на основе статистики, собранной по таблицам YDB, а также анализа самого плана.

Статистики для стоимостного оптимизатора

Стоимостной оптимизатор использует статистики как по таблице целиком, так и по отдельным колонкам. YDB собирает и поддерживает статистку в актуальном состоянии в фоновом режиме. Форсировать сбор статистики можно с помощью команды ANALYZE.

Текущий набор статистик по таблицам:

• Количество записей таблицы;
• Размер таблицы в байтах.

Текущий набор статистик по колонкам:

• Count-min sketch.

Текущие уровни стоимостной оптимизации

В YDB можно выставить уровень стоимостной оптимизации через прагму CostBasedOptimizationLevel