Введение
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. Заключение
