Методы оптимизации выполнения запросов в реляционных СУБД


Логическая оптимизация запросов - часть 3


Выбор канонической формы зависит от общей организации оптимизатора. Например, специфика оптимизации в СУБД INGRES [13] требует приведения логического условия к конъюнктивной нормальной форме.

При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия), и, кроме того, может быть произведено упрощение логического выражения за счет, например, выявления конъюнкции взаимно противоречащих предикатов. Так, если в логическом выражении встречается фрагмент ...(A>5)AND(A<5)..., то его можно заменить на ...FALSE... Возможны и более "умные" упрощения. Например, фрагмент логического выражения ...(A>B)AND(B=5)... можно заменить на ...(A>5)... Как видно из последнего примера, такие упрощения могут оказаться очень существенными для дальнейшей обработки запроса: в запросе с логическим условием первого вида предполагалось выполнение соединения двух отношений; после преобразования запрос уже не требует соединения.

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

- (A JOIN B) WHERE restriction-on-A AND restriction-on-B эквивалентно выражению (A WHERE restriction-on-A) JOIN (B WHERE restriction-on-B); - (A WHERE restriction-1) WHERE restriction-2 эквивалентно выражению A WHERE restriction-1 AND restriction-2; - (A [attribute-list-1]) [attribute-list-2] эквивалентно выражению A [attribute-list-2]; - (A [attribute-list-1) WHERE restriction-1 эквивалентно выражению (A WHERE restriction-1) [attribute-list-1].

Здесь JOIN обозначает реляционный оператор естественного соединения отношений; A WHERE restriction - оператор ограничения отношения A в соответствии с предикатом restriction (т.е.


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