Классика баз данных - статьи
Пример дерева
Теперь мы покажем, как выполняется поиск для примера соединения на . Прежде всего, мы находим все разумные пути доступа к одиночным отношениям с применением только локальных предикатов. Результаты для этого примера показаны на рис. 2. Для таблицы EMP имеется три пути доступа: индекс на DNO, индекс на JOB и сегментное сканирование. Интересными порядками являются DNO и JOB. Индекс на DNO обеспечивает кортежи в порядке DNO, и индекс на JOB обеспечивает кортежи в порядке JOB. Для наших целей путь доступа через сегментное сканирование считается неупорядоченным. Для этого примера мы предполагаем, что индекс на JOB является наиболее дешевым путем, поэтому сегментный путь доступа отсекается. Для отношения DEPT имеется два пути доступа: индекс на DNO и сегментное сканирование. Мы предполагаем, что индекс на DNO дешевле, поэтому сегментный путь доступа отсекается. Для отношения JOB имеется два пути доступа: индекс на JOB и сегментное сканирование. Мы предполагаем, что сегментный путь доступа дешевле, поэтому сохраняются оба пути. Только что описанные результаты сохраняются в дереве поиска, как показано на . На этих рисунках обозначения C(EMP.DNO) или C(E.DNO) обозначают стоимость сканирования EMP через DNO с применением всех предикатов, которые применимы, при том, что кортежи из указанных отношений уже прочитаны. Обозначение Ni представляет мощности различных частичных результатов.
Рисунок 3. Дерево поиска для одиночных отношений
Далее находятся решения для пар отношений путем присоединения второго отношения к результатам для одиночных отношений, показанных на рис.3. Для каждого одиночного отношения мы находим пути доступа для соединения с каждым вторым отношением, для которого существует предикат, соединяющий его с первым отношением. Сначала мы производим выбор путей доступа для соединений вложенными циклами. В этом примере мы предполагаем, что соединение EMP-JOB является наиболее дешевым при доступе к JOB через индекс JOB. Это вполне вероятно, поскольку позволяет прямо считывать кортежи о соответствию JOB (без потребности в сканировании всего отношения).
