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

Оптимизация запросов на основе стоимости исследует пространство эквивалентных планов выполнения для запроса и выбирает тот, который имеет наименьшую оценочную стоимость, используя статистику о данных и модель стоимости выполнения.

Definition

Оптимизация запросов на основе стоимости — это процесс оценки, на основе статистики данных и модели стоимости, стоимости выполнения альтернативных эквивалентных планов для запроса и выбора плана с наименьшей оценочной стоимостью, обычно с порядком соединений, выбранным с помощью динамического программирования.

Scope

Эта тема охватывает то, как оптимизатор выбирает план: пространство поиска планов, генерируемое эквивалентностями реляционной алгебры и альтернативными физическими операторами, модель стоимости, которая оценивает планы (главным образом по вводу-выводу и ЦП), оценку кардинальности и селективности на основе статистики и гистограмм, а также подход динамического программирования к перечислению порядков соединений, представленный System R. Она исключает реализацию самих операторов и логическую перестройку на основе правил, выходящую за рамки того, что используется для генерации планов.

Core questions

• Как генерируется и отсекается пространство эквивалентных планов выполнения?
• Как оптимизатор оценивает кардинальность и селективность операций?
• Как динамическое программирование эффективно перечисляет порядки соединений?
• Что учитывает модель стоимости и как комбинируются затраты на ввод-вывод и ЦП?
• Почему ошибки оценки кардинальности приводят к плохому выбору плана?

Key concepts

• пространство поиска планов
• модель стоимости (ввод-вывод и ЦП)
• оценка селективности и кардинальности
• гистограммы и статистика
• перечисление порядков соединений
• динамическое программирование
• интересные порядки
• оптимизация на основе преобразований

Key theories

Оптимизация с помощью динамического программирования в System R

Оптимизатор Селингера перечисляет порядки соединений снизу вверх с помощью динамического программирования, сохраняя самый дешевый план для каждого подмножества отношений (и каждого интересного порядка сортировки), что делает поиск в большом пространстве порядков соединений управляемым.

Оценка кардинальности и селективности

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

Модели стоимости и стратегии поиска

Планы оцениваются по модели стоимости, объединяющей эффекты ввода-вывода, ЦП и памяти; помимо динамического программирования System R, оптимизаторы на основе преобразований исследуют планы с помощью правил перезаписи, чтобы расширить оптимизацию на более сложные операторы и распределенные среды.

Clinical relevance

Оптимизатор — это компонент, который позволяет пользователям писать декларативный SQL, не указывая, как его выполнять; качество его оценок стоимости и поиска напрямую определяет, насколько быстро выполняются запросы к большим базам данных, поэтому оптимизация на основе стоимости является одной из наиболее изученных и коммерчески важных частей систем баз данных.

History

Оптимизатор System R 1979 года, разработанный Селингером и его коллегами, представил оптимизацию на основе стоимости с динамическим программированием порядка соединений и оценкой стоимости на основе селективности, определив эту область. Позднее оптимизаторы на основе преобразований, такие как Volcano и Cascades, обобщили поиск, а текущая работа по оценке кардинальности, включая обучаемые модели, устраняет центральный недостаток этой структуры.

Debates

Оценка кардинальности против адаптивного выполнения

Поскольку оптимизация на основе стоимости настолько хороша, насколько хороши ее оценки размера, которые часто ошибочны для коррелированных данных, исследователи спорят, стоит ли инвестировать в улучшенную статистику и машинное обучение оценщиков или больше полагаться на адаптивную, повторную оптимизацию во время выполнения, которая исправляет плохие планы во время выполнения.

Key figures

• Patricia Selinger
• Goetz Graefe
• Surajit Chaudhuri

Seminal works

• selinger1979
• graefe1993

Frequently asked questions

Почему оптимизатор иногда выбирает плохой план?

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

Почему для упорядочивания соединений используется динамическое программирование?

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