Обзор методов оптимизации запросов в реляционных системах


Группировки и соединения


При традиционном выполнении SPJ-запроса с группировкой вычисление SPJ-компонента запроса предшествует группировке. Набор преобразований, описываемых в этом подразделе, делает возможным выполнять операцию группировки до соединения. Эти преобразования применимы к запросам с SELECT DISTINCT, так что это специальный случай группировки. Выполнение операции GROUP BY потенциально может привести к значительному сокращению числа кортежей, поскольку для каждого раздела отношения, выделяемого операцией группировки, она генерирует только один кортеж. Поэтому в некоторых случаях при выполнении сначала группировки стоимость соединения может быть существенно уменьшена. Более того, при наличии подходящего индекса операция группирования может быть выполнена недорого. Для случая, когда операцию группирования можно выполнить после соединения, существуют двойники таких преобразований. Эти преобразования описаны в [5, 60, 25, 6] (обзор см. в [4]).

Группировка и соединение

Рис. 4. Группировка и соединение

В этом подразделе мы кратко обсудим конкретные случаи, в которых применимы преобразования, вызывающие выполнение группировки до соединения. Рассмотрим дерево запроса на рис. 4(a). Пусть R1 и R2 соединяются по внешнему ключу, столбцы агрегирования G все взяты из R1, а в состав набора столбцов группировки входит внешний ключ R1. Для такого запроса рассмотрим соответствующее дерево операций на рис. 4(b), где G1 = G. В этом дереве завершающее соединение может только сократить набор потенциальных разделов R1, созданных G1, но не может повлиять на разделы и на агрегаты, вычисляемые G1 на этих разделах, поскольку каждый кортеж R1 соединяется не более чем с одним кортежем R2. Следовательно, мы можем протолкнуть группировку вниз (как показано на рис. 4(b)) и сохранить эквивалентность для произвольных агрегатных функций без побочного эффекта. На рис. 4(c) иллюстрируется пример, где преобразование вводит группировку, и представляется класс полезных примеров, где операция группировки выполняется поэтапно.


Начало  Назад  Вперед



Книжный магазин