Проталкивание предикатов
В практических реляционных системах баз данных предикаты выборки проталкиваются как можно ниже в дереве выполнения. Данные фильтруются таким образом, что неподходящие строки не распространяются; в некоторых случах предикаты применяются неявно через путь доступа, выбранный для извлечения данных. Рассмотрим следующий SQL-запрос над базовыми таблицами emp(Eno, Ename, Sal, Bonus, Job, Dno, EkldsN) и dept(Dno, Mgrno, Location):
(Q): SELECT Ename,Mgrno FROM emp, dept WHERE Job = 'Sr Programmer' AND Sal + Bonus > 50000 AND emp.Dno = dept.Dno AND Location = “San Jose" AND P(emp,dept)
Здесь P – это некоторый сложный подзапрос. Система могла бы использовать индекс на Job для доступа только к старшим программистам с немедленным применением предиката на Sal + Bonus, производить доступ к dept с использованием индекса на столбце Dno и немедленным применением предиката на Location, и в заключение выполнять подзапрос P. Использование индексов часто обеспечивает хорошее соотношение «стоимость/эффективность», несмотря на то, что это можно считать дополнительным соединением (с использованием индекса). Индексный доступ может устранять извлечение многих неподходящих строк (и, следовательно, многих нетребуемых страниц данных). Как только мы получаем строку emp, можно передать вниз по дереву emp.Dno, и предикат на Dno можно использовать для доступа к dept (или фильтрации).
Предикат на Sal + Bonus можно было бы применить после выборки dept, но вместо этого «проталкивание предикатов» перемещает его ближе к доступу к данным. Поскольку вычисление таких предикатов обходится недорого, проталкивание предикатов (с возможно быстрейшим устранением ненужных строк) обычно явялется хорошей стратегией.
Эта идея получает дальнейшее развитие в операции полусоединения [BC8l, RBF+80]. Если отдел служащего не находится в Сан-Хосе, этот служащий не является релевантным (для приведенного выше запроса), так же, как если бы служащий был младшим программистом. Путем вычисления SJDno (номеров отделов, располагающихся в Сан-Хосе) система может использовать модифицированный вариант описанного выше плана выполнения, в котором служащие фильтруются (на основе emp.Dno IN SJDno) до соединения с таблицей dept.
Как и при использовании индексов, вводится дополнительная операция (вычисление SJDno и соединение). Применение этой операции означает, что к таблице dept доступ должен производиться дважды: первый раз для вычисления SJDno, а второй – для доступа к соответствующим отделам.
В исходном плане сначала производился доступ к emp, а затем значение Dno передавалось к dept для обеспечения доступа к нужным отделам. Предикат полусоединения, ограничивающий служащих теми, у которых Dno IN SJDno, передается «сторонним образом» в противоположном направлении, от таблицы отделов. Использование информации, передаваемой сторонним образом, является подходом магических множеств – систематическим введением предикатов, основанных на информации, которая передается сторонним образом, так что эти предикаты могут использоваться для как можно более раннего отфильтровывания неуместных данных.
В отличие от стандартного преобразования проталкивания предикатов, магия для конкретного запроса может применяться многими разными способами в соответствии с выбранными «sips» (silde-ways mformatlon passing strategies, стратегиями передачи информации сторонним образом). Sips могут использоваться гибко: для каждого порядка соединений (порядка sips) мы можем выбрать произвольный набор таблиц для генерации связываний и выбрать любой поднабор связываний для проталкивания. Это приводит к обазованию магических предикатов, которые связываются с некоторыми столбцами (аналогично приведенному выше предикату полусоединения для SJDno). Имена, используемые для магических таблиц, показывают, как они создавались – у этих имен имеются верхние индексы, указывающие ограничения на атрибуты таблиц исходного запроса. Эти верхние индексы называются «украшениями» (adornment).
