Операторы выполнения запросов

Операторы выполнения запросов — это физические алгоритмы (сканирование, выборка, проекция, сортировка, агрегация и объединение), которые механизм базы данных компонует в план и запускает для получения результата запроса.

Definition

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

Scope

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

Core questions

• Как итераторная модель (открытие-следующий-закрытие) позволяет компоновать операторы в конвейер?
• Когда результат обрабатывается конвейерно, а когда материализуется на диск?
• Как физически реализуются выборка, проекция и устранение дубликатов?
• Как внешняя сортировка слиянием обрабатывает данные, превышающие объем памяти?
• Как бюджет памяти и стоимость операций ввода-вывода влияют на производительность оператора?

Key concepts

• итератор / модель открытия-следующего-закрытия
• сканирование таблиц и индексов
• операторы выборки и проекции
• внешняя сортировка слиянием
• группировка на основе хеширования
• операторы агрегации
• устранение дубликатов
• конвейерная обработка в сравнении с материализацией

Key theories

Итераторная модель (Volcano)

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

Конвейерная обработка в сравнении с материализацией

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

Внешняя сортировка и агрегация

Когда данные превышают объем памяти, внешняя сортировка слиянием и группировка на основе хеширования обрабатывают их за несколько проходов по диску; эти алгоритмы лежат в основе ORDER BY, GROUP BY, устранения дубликатов и сортировки-слияния.

Clinical relevance

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

History

Итераторная модель была кристаллизована в фреймворке оценки запросов Volcano Грефе и его обзоре методов оценки запросов 1993 года, в котором каталогизировались физические операторы, используемые реляционными механизмами. Единый интерфейс модели сделал расширяемые, компонуемые механизмы запросов практически применимыми и остается стандартом, при этом более поздние работы добавили векторизованное и скомпилированное выполнение для повышения эффективности.

Key figures

• Goetz Graefe
• Jeffrey D. Ullman

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

Что такое итераторная модель?

Это подход к проектированию, при котором каждый физический оператор реализует один и тот же интерфейс — обычно open, next и close — и производит кортежи по одному, когда его родитель вызывает next. Поскольку все операторы используют этот интерфейс, их можно объединять в произвольные деревья планов, и кортежи перемещаются вверх по дереву по требованию.

Почему некоторые операторы называются блокирующими?

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