Содержание к диссертации
Введение
2. Предпосылки СУБД-ОП 10
2.1. Особенности архитектур современных компьютеров 10
2.1.1. Процессоры 10
2.1.1.1. Внутренний параллелизм 11
2.1.1.2. Предсказание переходов 12
2.1.2. Система памяти 15
2.1.2.1. Кэш-память 15
2.1.2.2. Характеристики кэш-памяти 17
2.1.2.3. Виды кэш-промахов 18
2.1.2.4. Явное управление кэш-памятью 19
2.1.2.5. Устройство трансляции адресов 20
2.1.2.6. Стоимость доступа к памяти 21
2.1.2.7. Методы измерения эффективности доступа к памяти 23
2.1.2.8. Пример 25
2.1.3. Особенности многопроцессорных систем 27
2.2. Архитектура традиционных СУБД и СУБД-ОП 29
2.2.1. Компоненты архитектуры традиционной СУБД . 29
2.2.1.1. Приложение 31
2.2.1.2. Менеджер соединений 31
2.2.1.3. Оптимизатор запросов 31
2.2.1.4. Менеджер ввода-вывода 33
2.2.1.5. Менеджер транзакций 35
2.2.1.6. Менеджер восстановления 35
2.2.1.7. Индексы 37
2.2.1.8. Операционная система 37
2.2.1.9. Аппаратное обеспечение 39
2.2.2. Отличия архитектуры СУБД-ОП 39
2.2.2.1. Отличия оптимизатора запросов 41
2.2.2.2. Отличия менеджера транзакций . 42
2.2.2.3. Отличия менеджера восстановления 43
2.2.2.4. Отличия индексных структур 44
2.2.2.5. Выводы 44
3. Общие методы оптимизации алгоритмов и структур данных для улучшения использования кэш-памяти 46
3.1. Оптимизация структур данных 47
3.1.1. Структура узлов 48
3.1.1.1. Удаление ключевых полей 48
3.1.1.2. Перегруппировка полей 49
3.1.1.3. Компрессия ключевых полей 50
3.1.1.4. Удаление указателей 51
3.1.2. Взаимное расположение узлов 53
3.2. Оптимизация алгоритмов 54
3.2.1. Модель локальности ссылок 54
3.2.2. Различные методы доступа к памяти 57
3.2.3. Методы оптимизации для уменьшения пространственного интервала 59
3.2.3.1. Введение временных структур данных . 59
3.2.3.2. Изменение порядка обхода структуры данных 60
3.2.4. Методы оптимизации для уменьшения интервала пе
реиспользования 61
3.2.4.1. Разбиение структуры данных на блоки . 61
3.2.4.2. Распределение структуры данных 62
3.2.4.3. Логическое распределение 65
3.2.5. Использование явной предвыборки 67
4. Алгоритмы выполнения операции соединения для СУБДОП 70
4.1. Модели хранения данных 70
4.2. Операция естественного соединения 73
4.2.1. Естественное соединение в СУБД-ОП 73
4.2.1.1. Близкие работы 74
4.2.1.2. Мульти-индексы — структура для эффективного естественного соединения в СУБД-ОП 77
4.2.1.2.1. Организация мульти-индекса 79
4.2.1.2.2. Экспериментальная проверка эффективности мульти-индекса 81
4.2.1.2.3. Запросы, включающие естественное соединение и выборку. 84
4.3. Операция соединения по предикату над множественнозначными атрибутами 85
4.3.1. Известные алгоритмы 88
4.3.1.1. Алгоритм вложенных циклов (SNL) 88
4.3.1.2. Алгоритм распределения (PSJ) 91
4.3.1.3. Алгоритм вложенных циклов с использованием инвертированных списков (IFNL) 93
4.3.1.4. Алгоритм соединения инвертированных файлов (IFJ) 95
4.3.1.5. Алгоритм, использующий индекс пересечения (IX) 98
4.3.1.6. Обработка случая пустого множества в алгоритмах, основанных на инвертированных списках 100
4.3.2. Предварительные эксперименты с алгоритмами со единения SNL, PSJ и IX 101
4.3.2.1. Набор данных Classes 103
4.3.2.2. Набор данных SD1: варьирующийся \Domain{A)\ 103
4.3.2.3. Выводы из предварительных экспериментов 104
4.3.3. Модификация алгоритмов IFNL и IF J для лучшего использования кэш-памяти 105
4.3.3.1. Алгоритм IFNL 105
4.3.3.2. Алгоритм IF J 108
4.3.4. Экспериментальная проверка алгоритмов IFNL(k) и
IFJ(l) 110
4.3.4.1. Эксперимент 1: оптимальное количество этапов для IFJ(n) 110
4.3.4.2. Эксперимент 2: сравнение IFNL и IFJ{1) . 112
4.3.4.3. Эксперимент 3: эффект сжатия списков . 113
4.3.4.4. Эксперимент 4: сравнение IFJ(l) с другими известными алгоритмами 114
4.3.5. Выводы 116
5. Заключение
- Внутренний параллелизм
- Архитектура традиционных СУБД и СУБД-ОП
- Перегруппировка полей
- Мульти-индексы — структура для эффективного естественного соединения в СУБД-ОП
Введение к работе
В течение нескольких последних десятилетий системы управления базами данных (СУБД) стали одним из основных приложений вычислительной техники. Сегодня успешная деятельность многих организаций, таких как государственные учреждения, предприятия, банки, магазины напрямую зависит от СУБД. Объемы данных, хранимые в таких системах, огромны и часто достигают многих терабайт [3]. Более того, требования прикладных областей к размерам хранимых данных постоянно растут [3, 1].
Организация таких объемов данных является нетривиальной задачей, различными аспектами которой исследователи в области СУБД занимаются начиная примерно с 70х гг. 20 века [4, 1]. База данных размером в несколько терабайт малополезна, если нет эффективного способа доступа к хранимым данным. Запросы пользователей к базе данных могут иметь различный характер - в одних случаях для получения ответа требуется просмотреть все содержимое базы данных, но не менее часто запросы затрагивают лишь небольшую часть хранимых данных. Типичным примером второго рода является проведение операции снятия денег со счета через банкомат. Для такой операции обычно интерес представляет лишь счет данного пользователя, идентифицируемый номером его кредитной карточки. Просмотр счетов всех пользователей банка в таком случае был бы очевидно неэффективным решением.
Традиционно СУБД хранят данные во вторичной памяти, такой как жесткие диски [3, 1]. Основной причиной этого является большой объем данных, который не может быть размещен в основной (оперативной) памяти компьютера. С другой стороны, архитектуры современных вычислительных систем ориентированы исключительно на обработку данных в основной памяти. В частности, процессор предоставляет обычно лишь инструкции для работы с данными, находящимися в памяти и во встроенных регистрах [43, 26]. В результате традиционные СУБД вынуждены значительное время тратить на пересылку данных из вторичной памяти в основную и обратно [1].
В контексте вышесказанного естественной является идея разместить базу данных не во вторичной, а в основной памяти, приводящая к появлению СУБД в основной памяти (СУБД-ОП) [1, 34]. Первые исследования, относящиеся к таким системам, появились примерно в начале 80х гг. 20 века [34, 3]. Наиболее привлекательная черта СУБД-ОП — отсутствие необходимости обращаться к медленной вторичной памяти для выполнения пользовательских запросов, что дает выигрыш на величину порядка по сравнению с традиционными СУБД [1, 19, 62]. Разумеется, ограниченный объем основной памяти влияет на максимальный размер базы данных, которую можно разместить в основной памяти. Однако не всегда объем БД исчисляется терабайтами, для многих приложений достаточно и нескольких гигабайт. Кроме того, на протяжении последних десятилетий наблюдается устойчивая тенденция быстрого роста объема ОП в компьютерах [26, 58], частично связанная с удешевлением микросхем памяти [58, 11, 21].
Например, рассмотрим гипотетическую реляционную БД, содержащую информацию о жителях крупного города с населением 4 млн человек. Одно из отношений, Citizens, может иметь вид:
Размер записи этого отношения составит примерно 80 байт, и для хранения информации о всех жителях города потребуется, таким образом, около 400 мегабайт. С учетом того, что в 2005 году объем ОП в 2 гигабайта не является редкостью для серверной системы, вся БД (состоящая из нескольких отношений) может быть целиком размещена в памяти сервера СУБД.
Проблемы оптимизация выполнения запросов в традиционных реляционных СУБД хорошо формализованы и исследованы [1]. На протяжении последних десятилетий были разработаны критерии эффективности методов выполнения запросов, и современные реляционные СУБД, как правило, способны выбирать наиболее эффективные пути выполнения запросов без помощи пользователя или администратора [1, б]. Однако с переносом данных в ОП традиционные критерии эффективности перестают иметь смысл [11, 21]: в традиционных СУБД оптимизация запросов обычно направлена на минимизацию числа обращений к медленной вторичной памяти, а в СУБД-ОП такие обращения не происходят вообще. Таким образом, необходимы новые критерии эффективности и, возможно, иные методы выполнения запросов.
Эффективное выполнение запросов в СУБД-ОП и является основным предметом данной работы. Наши исследования касаются эффективных индексных структур и методов выполнения запросов, которые позволяют полностью использовать возможности современных компьютеров. Мы систематизируем методы оптимизации работы с данными в ОП, а также предлагаем ряд новых индексных структур и алгоритмов выполнения операций и оцениваем их эффективность [51, 52, 54, 53].
Данная работа имеет следующую структуру. В главе 2 рассматриваются особенности современных компьютерных архитектур и обосновывается, почему традиционные СУБД, рассчитанные на хранение данных на диске, не позволяют получить максимальную производительность при использовании их в качестве СУБД-ОП. Там же показано, какие компоненты СУБД требуют пересмотра для СУБД-ОП. Глава 3 описывает общие идеи, кото рые применяются для повышения эффективности алгоритмов и структур данных в предположении, что данные располагаются в основной памяти. Эти идеи проиллюстрированы небольшими примерами, поясняющими их применение для простых задач, которые являются частями более сложных проблем, возникающих при реализации СУБД. В главе 4 мы применяем эти общие идеи к задачам оптимизации операции естественного соединения и соединения по предикату над множественнозначными атрибутами. Мы предлагаем мульти-индексы — структуру, которая в компактном виде хранит результат естественного соединения и допускает быстрое обновление при изменении индексируемых отношений. Мы также исследуем производительность нескольких алгоритмов для выполнения операции соединения по предикату над множественнозначными атрибутами в СУБД-ОП и выясняем, что наиболее эффективными являются методы, основанные на использовании инвертированных списков. Мы предлагаем модификацию этих методов, учитывающую специфические для СУБД-ОП критерии эффективности, и экспериментально демонстрируем, что эта модификация сокращает время выполнения соединения.
Внутренний параллелизм
Проблему для внутреннего параллелизма, однако, представляют инструкции перехода. Поскольку значение, которое получает регистр указатель команд (и, следовательно, адрес следующей выполняемой инструкции), вообще говоря, достоверно неизвестно до выполнения инструкции условного перехода или перехода с выборкой целевого адреса из таблицы, устройство выборки и декодирования вынуждено делать предположения об этом значении, чтобы продолжать пополнять конвейер инструкциями и избежать простоя, связанного с необходимостью ожидания, пока адрес перехода будет известен, и последующего заполнения конвейера. Этот процесс называется предсказанием переходов. Помещение в конвейер инструкций, которые, возможно, будут выполнены (при справедливости предположения об адресе перехода) приводит к их спекулятивному выполнению. Если при выполнении самой инструкции перехода оказывается, что предположение об адресе перехода было неверным, то процессор, во-первых, вынужден аннулировать результаты спекулятивного выполнения инструкций по неправильно предсказанному адресу, а во-вторых, заполнять конвейер новыми инструкциями с правильного адреса. Все это приводит к существенным задержкам.
Данная проблема с неправильным предсказанием переходов имеет непосредственное отношение к программисту. Алгоритмы предсказания переходов в процессоре основаны на эвристических ( условный переход назад, скорее всего, выполнится, поскольку это, вероятно, переход на очередную итерацию цикла ) и статистических (процессор поддерживает специальные таблицы со статистикой о том, как выполнялись инструкции перехода в прошлом) соображениях. Такие алгоритмы хорошо работают в простых ситуациях, но, разумеется, процессор не может правильно предсказать переходы в тех случаях, когда факт выполнения условного перехода нетривиальным образом зависит от данных, с которыми работает алгоритм.
Проиллюстрируем это на примере. Предположим, нам необходимо найти первую из записей отношения Students (ID, FirstName, LastName, Age), имеющую данное значение атрибута LastName. Предположим также, что отношение не имеет индекса по атрибуту LastName и хранится в полностью декомпозированной форме [3], т.е. каждый атрибут хранится в отдельной (неупорядоченной) таблице / массиве. Подобная схема, например, используется в СУБД-ОП Monet [12]. Псевдокод последовательного поиска, решающий эту задачу, мог бы тогда выглядеть следующим образом: int FindRecNoByLastName (string [] lastNames, string name) і for (int і = 0; і lastNames.Length; i++) if(lastNames [i] == name) return i; return -1; } Заметим, что условие внутри цикла оказывается вплоть до заключительной итерации ложным. Поэтому процессор легко может определить что ветка then условного оператора не выполняется, и количество ошибочных предсказаний минимально (они возможны только на первых итерациях цикла, пока не накоплена статистика). Допустим теперь, что в тех же условиях нам необходимо найти всех студентов моложе заданного возраста: void FindStudentsYoungerThanAge (int [] ages, int age, int[] result, out int totalRecords) { int pos = 0; for (int і = 0; і ages.Length; i++) if (ages [i] age) result[pos++] = i; totalRecords = pos; } (здесь для упрощения мы опускаем код, занимающийся расширением массива result по мере добавления туда записей). Теперь условие внутри цикла оказывается истинным, предположительно, намного чаще. Более того, если записи в отношении не упорядочены по возрасту, нет никакой зависимости значения условия от номера итерации. Алгоритм предсказания переходов, основанный на статистике, не работает, и в худшем случае ошибка предсказания перехода может происходить на каждой итерации цикла. Более эффективный код, решающий ту же задачу, выглядит так: void FindStudentsYoungerThanAge (int [] ages, int age, int [] result, out int totalRecords) і int pos = 0; for (int і = 0; і ages.Length; i++) { result [pos] = i; pos += (int) (ages [i] age); } totalRecords = pos; } Здесь выражение (int) (ages [i] age) принимает значения 0 или 1. Модифицированный вариант выполняет лишние присваивания, зато не содержит условных переходов внутри цикла. Как показано в [49], такой вариант, как правило, выполняется быстрее на современных компьютерах. Мы провели небольшой эксперимент, заключающийся в выполнении обоих вариантов алгоритма на компьютере с процессором Intel Pentium 4 2.8 GHz и 1 гигабайтом оперативной памяти при условиях \аггау\ = 9 107 и селективности (т.е. отношения количества записей, удовлетворяющих критерию отбора, к общему их числу) « 0.8. Среднее время выполнения первого варианта составило 0.78 с, второго — 0.67 с. При уменьшении селективности выигрывал, как правило, первый вариант.
Архитектура традиционных СУБД и СУБД-ОП
Упрощенная схема архитектуры СУБД представлена на рисунке 2.2 [1]. В последующих разделах мы рассмотрим функциональность каждого из компонентов схемы. При этом мы в основном будем концентрировать внимание на аспектах, имеющих отношение к устройству хранения данных (диску).
Оптимизатор запросов в первую очередь транслирует запрос из кода на языке запросов во внутреннее представление [1], пригодное для анализа и преобразований. Внутреннее представление обычно является деревом операций, взятых из множества операций некоторой алгебры, например, реляционной алгебры [3]. Это представление называется логическим планом запроса, поскольку указывает лишь операции алгебры, необходимые для выполнения запроса, но не реализации этих операции. Например, в логическом плане может присутствовать логическая операция соединения, которая может быть реализована многими способами (вложенные циклы, индексы, хэш-соединение, сортировка-слияние и т.д.)
При анализе и преобразовании логического плана оптимизатор использует статистическую информацию, которая поддерживается при участии других компонентов СУБД (отсюда на рисунке 2.2 стрелки от индексов и менеджера ввода-вывода к оптимизатору запросов). Статистическая информация может содержать данные о количестве записей в отношениях, количестве различных значений атрибута отношений, количестве записей с данным значением атрибута [1, 32]. Задача оптимизатора состоит в выборе лучшего из множества эквивалентных планов, т.е. планов, выполнение которых даст одно и то же множество записей. Критерием для сравнения между собой двух логических планов является размер промежуточных отношений, которые получаются при выполнении операций плана: чем меньше этот размер, тем лучше план. Основанием для этого является тот факт, что на обработку отношений меньшего размера уходит, вообще говоря, меньше времени. При преобразовании логических планов используются алгебраические свойства операций, такие как ассоциативность, коммутативность и дистрибутивность. Например, типичными методами преобразования логического плана запроса являются перестановка операций соединения и сдвиг операций выборки вниз по дереву [1].
Один и тот же логический план можно выполнить разными способами, и задачей оптимизатора является подбор такой реализации логического плана, которая, предположительно, является наиболее эффективной (физический план запроса). Выбор конкретного алгоритма реализации логической операции зависит как от размера входных отношений — аргументов операции, так и текущих доступных ресурсов системы — загруженности процессора и количества свободной оперативной памяти. Например, если входные отношения не помещаются в оперативную память, то лучшим алгоритмом для операции соединения будет сортировка-слияние, а если оба отношения помещаются в буфер, то больше подойдет хэш-соединение. На решение оптимизатора о выборе физического плана влияет также наличие индексов, которые могут использоваться для реализации операций выборки или соединения. Если ожидаемая селективность выборки велика, т.е. количество записей, отвечающих критерию выборки, мало, то индекс может существенно ускорить выполнение. Если же в результат выборки попадают почти все записи отношения, то выгоднее применить последовательное сканирование записей.
Для сравнения различных физических планов оптимизатор использует стоимость планов. Стоимость плана формулируется как суммарная стоимость различных операций, входящих в план, т.е. TotalCost(P) = TotalCostio). овР Основными компонентами стоимости для традиционных СУБД являются стоимость ввода-вывода и вычислительная стоимость, т.е. количество примитивных операций, выполняемых процессором для данной операции. Другими словами, TotalCost(o) = N + NPU, где NQ — количество операций ввода-вывода, a N pu — количество примитивных операций (сложение, умножение, присваивание). В зависимости от реализации модели стоимости могут быть и более детальными, например, различать типы примитивных операций. Например, для операции чтения отношения в память N ep = 0 и TotalCost{read) = Nb, где Nb — количество дисковых блоков, занимаемых отношением. Для операции сортировки отношения в памяти N msort = 0 и TotalCost(memsort) = NlogN, где N — количество записей в отношении.
Перегруппировка полей
Компрессия ключевых полей позволяет уменьшить размер ключевых полей и, следовательно, количество кэш-блоков, занимаемых узлом (или поместить больше узлов в один кэш-блок). Часто ключевые ПОЛЯ являются неотрицательными целыми числами, причем располагаются в узле в порядке возрастания — например, так было в рассмотренном в предыдущем примере fc-арном дереве. В этом случае может быть применим один из методов компрессии возрастающей последовательности неотрицательных целых чисел, рассмотренных в [66]. Такие методы основаны на том, что вместо самого числа хранится разность между данным числом и предыдущим, которая является (предположительно небольшим) положительным числом, и это число кодируется с помошью одного из методов кодирования, например, 7_ или ( -кодирования [66]. Недостатком данного метода является то, что после его применения ключевые поля могут быть доступны только для последовательного просмотра, поскольку для декодирования очередного значения требуется предыдущее. Кроме того, закодированные числа могут занимать не целое число байт, и для доступа к ним требуются сравнительно медленные на современных процессорах инструкции сдвига битов и побитового AND [29]. В качестве средства исправления последнего недостатка можно выравнивать закодированные числа по границам байта, но это уменьшает эффект от компрессии [20].
Другим методом компрессии, который применяется в ситуации, когда ключевые поля имеют большой размер и переменную длину (в частности, являются строковыми значениями), является отделение от каждого ключевого значения префикса фиксированной длины [10]. Длинное ключевое значение в узле при этом заменяется на префикс и указатель на само ключевое значение: keyi ь- (prefiXi,key_pointeri) (заметим, что key_pointeri является информационным полем в смысле используемой терминологии, хотя и содержит указатель на строку). Основанием для этого является тот факт, что во многих случаях вместо ключа можно использовать префикс -например, при сравнении строк можно сравнить префиксы, и обращаться к самим строкам только в случае совпадения префиксов.
Пример 1. Вновь рассмотрим узел 5-арного дерева Node — (1980, 1998, 2002, 2004, 2005, ptro, ptri, ptr2, ptr , ptr , ptr ). Используя компрессию целых чисел, мы преобразуем последовательность ключевых значений в (1980, 18, 4, 2, 1). При использовании кодирования целых чисел с выравниванием по границе байта каждое ключевое значение, начиная со второго, занимает 1 байт, таким образом, всего мы сэкономили 4(sizeof(int) - 1) = 12 байт.
Пример 2. Пусть ключевые значения являются строками. Рассмотрим узел 3-арного дерева:
Node = ( Ivanovsky , Lebedev , Pavlovsky , Petrovsky , ptro, ptfi, ptr2, ptrs, ptr4). Вместо строк будем использовать 2-х символьные префиксы: keyi і— (prefix?, key_pointerІ), получим: Node = ( Iv , be , Pa , Pe , keyjptri, key_ptr2, key_ptr%, key_ptrA, ptr0, ptru ptr2, ptr , ptr4). В результате мы сэкономим 3 9 + 7 — (3 2 + 3 4) = 16 байт в узле, кроме того, сравнение коротких префиксов быстрее, чем исходных строк.
Обычно поля, являющиеся указателями, не используются в функции ExamineNode — на очередной итерации цикла в алгоритме 3.1 происхо дит обращение лишь к одному из указателей узла, который выбирается в результате вызова ExamineNode. Уменьшив количество указателей, можно уменьшить количество кэш-блоков, занимаемых узлом. Заметим, что указатели нужны лишь для поддержания связей в структуре, поэтому их можно заменить на другой способ поддержания этих связей — в частности, на их вычисление. Как правило, вычисление связей основано на том, что, при наличии в структуре определенной регулярности, адрес дочернего узла можно рассчитать исходя из адреса родительского узла и порядкового номера дочернего узла среди дочерних узлов родительского узла.
Пример 1. Рассмотрим &-арное дерево, Node = (keyo,...,keyk,ptro,...,ptrk). Предположим, что все дочерние узлы располагаются в памяти последовательности, так что ptr{ = ptro + і sizeof(Node). В этом случае можно удалить из узла все указатели, кромеріго, сэкономив тем самым (к — 1) sizeof(ptr) = 4(к — 1) байт в кэш-блоке. Разумеется, это требует специальной поддержки при модификации дерева, в частности, при добавлении новых узлов и увеличивает общий объем памяти, занимаемой деревом [48].
Пример 2. В условиях предыдущего примера предположим, что дерево является полным и хранится в памяти так, что все уровни и все узлы на одном уровне располагаются последовательно. Смещение і-го узла на уровне 1 (I 1) относительно начала дерева addrO в памяти в этом случае равно (1 + к-\- ...-\-к1 1 + Ї) sizeof(Node). Это дает возможность, зная адрес currentNode в алгоритме 3.1, определить уровень I узла currentNode, что позволяет найти адрес дочернего узла, зная его порядковый номер среди дочерних узлов currentNode. Чтобы избежать вычисления уровня / на каждой итерации алгоритма 3.1, можно поддерживать І в качестве дополнительной переменной цикла, увеличивая ее на каждой итерации. Таким образом, в данной ситуации хранение указателей на дочерние узлы вообще не требуется, однако такая структура данных непригодна, если в дерево могут добавляться новые ключи [47].
Мульти-индексы — структура для эффективного естественного соединения в СУБД-ОП
В данном разделе мы рассматриваем мульти-индексы — индексную структуру, предназначенную для оптимизации операции естественного соединения в СУБД. Мы предполагаем, что эта структура, как и хранимые отношения, целиком размещается в оперативной памяти, а доступ к диску не происходит вообще. Это предположение оправдано, поскольку поддержание в актуальном состоянии индексной структуры в СУБД-ОП не влечет дополнительных обращений к диску. Действительно, индексная структура представляет собой "вторичные данные" в том смысле, что она может быть всегда восстановлена (в частности, после сбоя СУБД) по исходным отношениям, поэтому изменения в ней не нуждаются в протоколировании.
Основная идея мульти-индекса заключается в хранении и обновлении специализированной структуры данных, которая позволяет легко вычислить результат соединения. Эта идея является более общей и применима не только к естественным соединениям [63]. Таким образом, можно утверждать, что мульти-индекс является специальной формой индекса соединения. Заметим, что работы [63, 36], где шла речь об индексе соединения, не уточняли, как именно реализован этот индекс, рассматривая его как отношение, состоящее из пар идентификаторов записей (r,s), возможно, отсортированных по первому или второму компоненту пары. Поскольку мы рассматриваем не произвольные соединения, а естественные, т.е. соединения по равенству значений атомарного атрибута, мы можем использовать более эффективное представление индекса соединения, содержащее меньшее количество повторяющейся информации.
Для дальнейшего обсуждения нам понадобятся несколько формальных определений. Пусть R и S - отношения, А\ и Л2 — атрибуты R и S, со ответственно, причем Domain(Ai) = Domain(A2) = Domain(A). Тогда мульти-иидекс является отображением IR S Domain(A) — {п}, где Т{ — идентификаторы записей из отношений R или S. Нашей задачей является построение эффективной реализации этого отношения для СУБД-ОП. Результирующая структура данных должна обновляться при изменении отношений R и S, т.е. при удалении, добавлении или изменении записей. Основные требования к ней следующие: Эффективное выполнение операции естественного соединения Незначительные накладные расходы на поддержание индекса при обновлении отношений R и S Возможность использования индексной структуры в качестве обычного индекса для отношений R и S по атрибутам А\ и A i
Совокупность этих требований позволяет надеяться на пригодность мульти-индексов к практическому использованию. Как обычно, под эффективностью мы понимаем не только вычислительную сложность, но и количество кэш-промахов, возникающих при выполнении той или иной операции.
Следует заметить, что в дальнейшем под задачей выполнения естественного соединения мы будем понимать построение индекса соединения, т.е. нахождение всех пар (г.rid, s.rid), г Є R, s Є S, г.A = s.A. Эта задача формально является лишь частью проблемы построения результата естественного соединения (в смысле определения естественного соединения, приведенного выше), поскольку для конструирования записей результата соединения требуется также получение атрибутов соответствующих записей исходных отношений. Эффективные методы конструирования результата соединения по индексу соединения для СУБД-ОП рассмотрены в работе [41]. В экспериментах для конструирования записей результата мы использовали прямолинейный алгоритм, который обходит индекс соединения и получает атрибуты соответствующих записей г и s по r.rid и s.rid.
Организация мульти-индекса. Для мульти-индекса мы предлагаем двухуровневую структуру [51], в которой на нижнем уровне информация о соответствующих парах RID (r,s) хранится в виде записей (индексных записей), организованных в страницы. На верхнем уровне находятся стандартные индексные структуры (В-деревья или хэш-таблицы), отображающие значения Domain(A) в записи нижнего уровня. Такая структура используется в СУБД для хранения отношений с данными, однако особенностью предлагаемой структуры является организация индексных записей, показанная на Рис. 4.3. Индексная запись содержит информацию обо всех записях отношений R и S, имеющих данное значение v атрибутов Лі и А2.
Индексная запись содержит не более Rmax идентификаторов записей отношения Лине более Smax идентификаторов записей отношения S. Поля Rcount и Scount хранят информацию о действительном количестве идентификаторов записей из R и S, содержащихся в данной индексной записи. Массивы Ro,...,RRmax_i и So,...,Ssmax-i содержат сами идентификаторы записей R и S.
Алгоритм выполнения операции естественного соединения с использованием подобной структуры вполне очевиден. Для этого достаточно однократного просмотра всех страниц мульти-индекса, т.е. структуры нижнего уровня. В процессе просмотра формируются результирующие записи. Заметим, что рассмотренная структура обобщается очевидным образом на случай более двух отношений. Возможной оптимизацией с точки зрения утилизации кэш-памяти является размещение идентификаторов записей отношений, которые, предположительно, часто участвуют в операции естественного соединения в запросах, рядом друг с другом в индексной записи [51].
