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


Выбор и оценка альтернативных планов выполнения запросов - часть 9


Наконец, для сложных запросов, включающих, например, соединения более двух отношений, требуется оценивать размеры возникающих в процессе выполнения запроса промежуточных временных отношений. Как известно, соединение двух отношений R1 и R2 в соответствии с предикатом соединения R1.C1 op R2.C2, где op операция сравнения, концептуально интерпретируется как ограничение отношения R, полученного в результате декартова произведения отношений R1 и R2, предикатом R1.C1 op R2.C2. Для того, чтобы оценить мощность результирующего отношения, вообще говоря, необходимо знать степень селективности предиката соединения по отношению к прямому произведению отношений-операндов. В общем случае степень селективности такого предиката невозможно определить на основе простой статистической информации. Обычно применяются достаточно грубые эвристические оценки, хотя предлагаются и подходы, обеспечивающие большую точность.

Прежде, чем приступить к рассмотрению современных подходов к решению отмеченных проблем, приведем короткий обзор подхода, применяемого для оценок стоимостей планов выполнения запроса в System R. При этом мы преследуем две цели. Во-первых, этот подход является достаточно распространенным и, как утверждают многие (например, [5]), оправданным на практике. Во-вторых, в нашем изложении мы постараемся выделить основные недостатки этого подхода, преодолению которых посвящено много работ.

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


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



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