Классика баз данных - статьи
В 1987 г. мы ввели
В 1987 г. мы ввели эффективное соединение слиянием отношений A и B по атрибуту X с использованием индекса на B.X. Если для некоторого разрыва между двумя соседними значениями A.X имеется несколько значений B.X, которые нужно пропустить, эти значения B.X пропускаются в манере зигзаг путем испытания всех ключей в текущей индексной странице, а затем (для больших разрывов) спуска от корня B-дерева к концу разрыва.
Затем мы обратили внимание, что прохождение значения конца разрыва от A к B можно также осуществить через агрегат, определенный на B.X, и реализовали зигзагообразный пропуск разрыва над одним или несколькими агрегатами. Далее, при оптимизации выборки с несколькими диапазонами мы применили зигзагообразный пропуск к разрывам в упорядоченном списке диапазонов. Наконец, оптимизации соединения слиянием и списка диапазонов были интегрированы в динамическую стратегию выборки, называемую «Leaf». Если для поддержки дополнительных ограничений были доступны индексы, отличные от B.X (скажем, B.Y), то на начальной стадии применялась тактика организации конкуренции «Sorted», при которой:
- B.X и B.Y сканирутся в параллель;
- на стороне X читаются и выдаются записи в желаемом порядке сортировки;
- на стороне Y строится фильтр ID записей для дополнительного ограничения Y;
- после заполнения фильтра начинается пропуск записей на стороне X, не входящих в фильтр Y.
Рис. 2. SQL-запрос и план выполнения с использованием технологии пропусков
На рис. 2 показан SQL-запрос, в котором все методы пропуска, описанные выше, объединяются в единый план выполнения, напечатанный утилитой Rdb выдачи дампа стратегии. Концевые значения разрывов передаются из цикла Outer в цикл Inner через Aggregate к Leaf#01 для пропуска через FgrNdx BX (индекс переднего плана). Одновременно к индексу BX для пропуска передаются концы разрыва в списке диапазонов [2:2], [4:4], [8:8], [16:16], [32:32]. В то же самое время, сканируется BgrNdx1 BY (индекс заднего плана), и его список ID записей, ограничиваемый B.Y < 1, используется для конструирования фильтра «B.Y < 1».Если фоновое сканирование BY завершается раньше BX, полный фильтр, произведенный BY, используется для избежания чтения записей в сканировании BX. В противном случае BX быстрее достигает цели без фильтрации, и выборка из B завершается.
Приведенный пример иллюстрирует, как свойство кластеризации структуры индекса может быть использовано разными способами для выборки требуемых данных из непрерывных частей диска и для пропуска ненужных записей путем распространения разрыва и использования фильтров. Для очень больших баз данных остается потребность в разработке более изощренных и интегрированных методов обработки, основанных на индексах и их свойствах поддержки упорядоченности, кластеризации и декластеризации. Проблема состоит в эффективном отделении требуемых непрерывных и упорядоченных частей от разрывов и хаоса и последующем решении о целесообразности применения соединения с хэшированием и агрегации к некластеризованным индексам и областям с бесполезным упорядочением.
