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



              


Синтаксическая оптимизация


Первый успех в оптимизации запросов состоял в нахождении способа переформулирования запроса таким образом, чтобы новое представление запроса обеспечивало тот же результат, но было более эффективно для обработки СУБД.

Пример. Рассмотрим следующий запрос, который делает выборку данных из таблиц PRODUCT (ПРОДУКЦИЯ) и VENDOR (ПРОИЗВОДИТЕЛЬ):

SELECT VENDOR_CODE, PRODUCT_CODE, PRODUCT_DESC FROM VENDOR, PRODUCT WHERE VENDOR.VENDOR_CODE = PRODUCT.VENDOR_CODE AND VENDOR.VENDOR_CODE = "100";

Наиболее очевидный путь обработки этого запроса состоит в следующем:

  1. Формируем декартово произведение таблиц PRODUCT и VENDOR.
  2. Ограничиваемся в результирующей таблице строками, которые удовлетворяют условию поиска в предложении WHERE.
  3. Выполняем проекцию результирующей таблицы на список колонок, указанный в предложении SELECT.

Оценим стоимость процесса обработки этого запроса в терминах операций ввода/вывода. Пусть для определенности таблица VENDOR содержит 50 строк, а таблица PRODUCT - 1000 строк. Тогда формирование декартова произведения потребует 50050 операций чтения и операций записи (в результирующую таблицу). Для ограничения результирующей таблицы потребуется более 50000 операций чтения и, если 20 строк удовлетворяют условиям поиска, то 20 операций записи. Выполнения операции проекции вызовет еще 20 операций чтения и 20 операций записи. Таким образом, обработка этого запроса обойдется системе в 100090 операций чтения и записи.

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

(A JOIN B) WHERE restriction on A v (A WHERE restriction on A) JOIN B.

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


Содержание  Назад  Вперед