автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Эффективные методы индексирования данных и выполнения запросов в системах управления базами данных в основной памяти

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Шапоренков Дмитрий Александрович

ЭФФЕКТИВНЫЕ МЕТОДЫ ИНДЕКСИРОВАНИЯ ДАННЫХ И ВЫПОЛНЕНИЯ ЗАПРОСОВ В СИСТЕМАХ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ В ОСНОВНОЙ ПАМЯТИ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2006

Работа выполнена на кафедре системного программирования математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук,

профессор Новиков Борис Асенович

Официальные оппоненты: доктор технических наук,

Кузнецов Сергей Дмитриевич кандидат физико-математических наук, Округин Михаил Борисович

Ведущая организация: Южно-Уральский государственный

университет

Защита диссертации состоится "_"_2006 года в_часов

на заседании диссертационного совета Д212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28, математико-механический факультет Санкт-Петербургского государственного университета.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

'У "

Автореферат разослан " 2006 года.

Ученый секретарь диссертационного совета доктор физико-математических наук,

профессор Б.К.Мартыненко

^ ^Ьбщая характеристика работы

Актуальность темы

Системы управления базами данных (СУБД) уже на протяжении нескольких десятилетий являются неотъемлемой частью человеческой деятельности. Эффективность работы практически всех крупных предприятий, организаций, банковских учреждений зависит от эффективности организации процесса обработки больших объемов информации, и СУБД являются важнейшей частью этого процесса. Обеспечивая надежное хранение информации и быстрое получение ответов на интересующие пользователей запросы, СУБД играют роль "ядра" , на основе которого строятся информационные системы, предоставляющие удобный для человека пользовательский интерфейс или позволяющие обмениваться данными с другими системами.

СУБД в ее классическом понимании хранит данные на постоянном носителе информации — жестком диске. Жесткий диск является в определенном смысле "компромиссным" устройством хранения информации, поскольку, с одной стороны, имеет достаточно высокую (по сравнению с такими носителями информации как компакт-диски и магнитная лента) скорость доступа к информации, а с другой стороны не теряет записанную информацию при выключении питания [1]. Эти свойства сделали диск самым популярным устройством хранения информации, к тому же объем жестких дисков постоянно растет и к настоящему времени (2006 год) измеряется уже терабайтами, а стоимость единицы объема уменьшается. Все это приводит к тому, что хранение информации на жестких дисках является дешевым решением, доступным любым организациям. Кроме того, существует специальное аппаратное обеспечение, такое как ИАГО-диски, также основанное на жестких дисках, но обеспечивающее повышенную отказоустойчивость за счет хранения избыточной информации [1, 2].

Однако, в отличие от объема жестких дисков, который за последние десятилетия увеличился в тысячи раз, скорость доступа к данным на жестких дисках не прогрессировала столь стремительно и увеличилась лишь в десятки раз [1, 7]. Это приводит к тому, что жесткий диск становится "уз-

ким местом" современных вычислительных систем [7], поскольку за тот же период времени скорость работы процессора (CPU) претерпела еще более впечатляющие улучшения, чем объем жестких дисков [7]. Поэтому выполнение операции ввода-вывода приводит к тому, что процессор вынужден ожидать необходимых для работы данных от жесткого диска (так называемый "простой" процессора). СУБД и другие программы используют буферизацию данных в основной (оперативной) памяти для минимизации негативного эффекта этих "простоев" [2, 1].

Подобно объему жестких дисков и скорости работы процессора, объем оперативной памяти также увеличился в тысячи раз за последние десятилетия. Это позволяет поместить базу данных среднего размера целиком в основную память и приводит к идее СУБД в оперативной (основной) памяти, (СУБД-ОП), являющихся предметом исследования в данной работе. В СУБД-ОП все данные и вспомогательные структуры, такие как индексы, находятся в основной памяти, поэтому жесткий диск для доступа к ним не используется. С учетом того, что скорость доступа к основной памяти на несколько порядков выше, чем скорость доступа к данным на жестком диске [7, 1], это позволяет надеяться на значительное ускорение обработки данных.

Однако традиционные СУБД имеют сложившуюся архитектуру, рассчитанную на хранение данных на медленном носителе — жестком диске [2 1. 3] и направленную на минимизацию числа обращений к нему. Оказывается, что такая архитектура не является оптимальной для СУБД-ОП [5, 9, 4, 8] и требует пересмотра. Например, традиционные индексные структуры — В+-деревья, параметризованные размером дисковых страниц, являются недостаточно эффективными для СУБД-ОП [9]. Скорость доступа к данным в основной памяти намного выше, чем на диске, но все еще на много порядков ниже, чем скорость работы процессора [7. 5], и, подобно технике буферизации дисковых страниц, в современных компьютерах используется быстрая кэш-память [11], работающая со скоростью, почти эквивалентной скорости самого процессора, но имеющая очень ограниченный объем (порядка нескольких мегабайт). Для уменьшения "простоев" процессора программа (в частности, СУБД-ОП) должна стремиться как можно

больше активно используемых данных умещать в кэттт-памяти [7. 5, 9]

Цели работы

Данная работа исследует некоторые алгоритмы выполнения реляционных операций и индексных структур в контексте СУБД-ОП. Цели, преследуемые работой, включают:

• В предположении хранения всех данных в основной памяти, определение источников "простоев" процессора в программе, оказывающих негативное влияние на производительность СУБД-ОП.

• Построение простой модели "локальности" обращений к памяти в программе, показывающей, насколько хорошо для данной программы будет работать кэширование часто используемых данных (или, другими словами, насколько эффективно программа может использовать кэш-память процессора).

• Исследование возможностей предвычисления результатов операции естественного соединения (как одной из наиболее распространенных в СУБД) и хранения их в виде специальной структуры.

• Поиск эффективных алгоритмов выполнения операций соединения по предикату над множественнозначными атрибутами.

Основные результаты

В работе получены следующие основные результаты:

• На основе простых экспериментов продемонстрировано, что эффективное использование кэш-памяти процессора играет решающую роль в программах, включающих интенсивный обмен данными между процессором и основной памятью.

• Предложены критерии оценки эффективности структур данных и алгоритмов для СУБД-ОП. учитывающие неоднородность доступа к основной памяти в современных вычислительных системах,

• Построена классификация, обобщающая большинство известных методов оптимизации структур данных и алгоритмов для эффективного использования кэш-памяти процессора Эта классификация обобщает предшествующие работы и сводит методы оптимизации использования кэш-памяти к нескольким простым идеям.

• Предложен и экспериментально проверен метод оптимизации операции соединения на основе мульти-индексов в СУБД-ОП, показана его сравнительная эффективность по сравнению с методом хэш-соединения в зависимости от параметров входных отношений.

• Исследованы различные алгоритмы для выполнения операции соединения по предикату над множественнозначными атрибутами в СУБД-ОП, предложена модификация алгоритма, основанного на использовании инвертированных файлов, для лучшего использования кэш-памяти и экспериментально продемонстрировано, что эта модификация приводит к уменьшению времени выполнения соединения

Научная новизна

В данной работе впервые детально исследованы операции соединения по предикатам над множественнозначными атрибутами в контексте СУБД-ОП. с учетом такого фактора как неоднородность доступа к памяти. Остальные полученные результаты также являются новыми и дополняют результаты предшествующих работ.

Практическая и теоретическая ценность

С теоретической точки зрения, в работе предложена простая модель локальности ссылок на данные в программе, позволяющая быстро оценить, насколько эффективно для ссылки будет работать кэширование. Кроме того, в работе получены аналитические оценки эффективности нескольких алгоритмов на основе инвертированных списков для выполнения операции соединения по предикатам над множественнозначными атрибутами.

Практическая ценность работы состоит в том. что предложенные алгоритмы могут быть использованы при построении эффективной реализации СУБД-ОП Экспериментальные результаты, содержащиеся в работе, могут послужить основой для выбора наиболее подходящего алгоритма для выполнения соединения по предикату над множественнозначными атрибутами в зависимости от параметров отношений, что важно, в частности, для создания оптимизатора запросов для СУБД-ОП.

Апробация работы

Результаты работы докладывались

• на Девятой Восточно-Европейской конференции "Advances in Databases and Information Systems"(TajuraH, Эстония, сентябрь 2005)

• на Шестой конференции "Baltic Conference on Databases and Information Systems"(Рига, Латвия, июнь 2004)

• на Первом и Втором коллоквиумах "Spring Colloquium for Young Researchers in Databases and Information Sytems (SYRCoDIS)" (Санкт-Петербург. май 2004 и июнь 2005)

• на семинарах группы теории баз данных при лаборатории исследования операций НИИММ

Публикации

Основные результаты представлены в работах [1]-[4]. Структура и объем диссертации

Диссертация состоит из введения. 3 глав, заключения и списка литературы. Основной текст диссертации занимает 120 страниц машинописного текста Библиография содержит 67 наименований. Общий объем диссертации 128 страниц. Рисунки и таблицы нумеруются по главам.

Содержание работы

Введение является первой главой и содержит предварительную информацию о предмете исследования.

Вторая глава демонстрирует актуальность СУБД-ОП. В ней содержится краткое изложение особенностей архитектуры современных компьютеров, оказывающих существенное влияние на эффективность программ. Большая разница в скорости работы процессора и оперативной памяти компенсируется за счет нескольких уровней кэш-памяти, устанавливаемой внутри процессора. Однако, эффективное использование кэш-памяти, как и буфера трансляции адресов, ускоряющего преобразование виртуальных адресов в физические, является обязанностью программы. Это иллюстрируется примером простой программы, выполняющей доступ к элементам большого массива с определенным шагом. От величины шага зависит количество кэш- и ТЬВ-промахов и, тем самым, время выполнения программы.

Вторая часть второй главы посвящена обзору архитектуры традиционных СУБД и выяснению того, насколько пригодна эта архитектура для СУБД-ОП, в предположении того, что все данные и вспомогательные структуры находятся в основной памяти. Выясняется, что наиболее существенные изменения должны претерпеть оптимизатор запросов и индексные структуры. Эти изменения связаны с тем, что оптимизатор запросов в традиционных СУБД обычно выбирает план, доставляющий минимум функции стоимости, которая включает в себя вычислительную стоимость операции (в терминах количества каких-либо примитивных операций) и количество операций ввода-вывода. В СУБД-ОП второй компонент функции стоимости заменяется на количество "простоев" процессора из-за кэш-промахов, ошибок предсказания перехода и других причин, поэтому для одного и того же объема входных данных оптимизатор в традиционной СУБД и СУБД-ОП могут считать наилучшими разные планы. Аналогично, индексные структуры в традиционных СУБД-ОП стараются минимизировать количество операций ввода-вывода во время поиска (как, например, В+-дерево), и их устройство и параметры (например, размер узла В+-дерева) выбираются из этих соображений. Но такой выбор зачастую оказывается

неоптимальным в СУБД-ОП, где главной задачей является минимизация числа кэш- и ТЬВ-промахов — в частности, большие узлы "дисковых" В+-деревьев приводят в СУБД-ОП к большому количество кэш-промахов во время поиска внутри узла [9, 6, 10].

В третьей главе рассматриваются общие методы оптимизации использования кэш-памяти в алгоритмах и структурах данных. Предложенная классификация основана на обобщении приемов, встречающихся в более ранних работах. Отдельно рассматривается оптимизация структур данных и алгоритмов. Для структур данных рассматривается простая модель, где все структуры данных состоят из узлов, которые включают поля двух видов — ключевые поля и указатели. В ключевых полях содержится информация, относящаяся к хранимым данным, а указатели необходимы для поддержания связей в самой структуре данных. Методы оптимизации структур данных удаляют неиспользуемые для поиска ключевые поля из узла, группируют поля таким образом, чтобы совместно используемые поля находились рядом в узле, используют сжатие для уменьшения размера ключевых полей и удаляют указатели из узла, заменяя их на вычисление адресов дочерних узлов за счет специального устройства структуры данных. Можно также пытаться улучшать взаимное расположение узлов, располагая на нечетных уровнях дочерние узлы в том же кэш-блоке, что и родительский узел, если количество дочерних узлов у данного узла невелико.

В разделе третьей главы, посвященном оптимизации алгоритмов, используется модель локальности ссылок, которая характеризует темпоральную и пространственную локальность инструкции обращения к памяти (ссылки) в программе. Пространственная локальность выражается с помощью пространственного интервала, который равен среднему расстоянию между адресами двух последовательных исполнений инструкции обращения к памяти. Интервал переиспользования, характеризующий темпоральную локальность, равен среднему интервалу времени между исполнениями ссылки, которые попадают в один и тот же кэш-блок. Мы рассматриваем также зависимость между адресами последовательных исполнений ссылки — в некоторых случаях можно сказать (с точностью до несколь-

ких возможных значений) чему будет равен адрес очередного исполнения ссылки, зная адрес текущего исполнения. Эта зависимость моделирует списки, деревья и другие подобные структуры, где узел содержит указатели на следующие узлы Введенные понятия позволяют более формально определить последовательный, произвольный и псевдо-произволъный характер доступа к памяти, что используется в данной и следующей главах Методы оптимизации алгоритмов, рассматриваемые в третьей главе, подразделяются на методы, уменьшающие пространственный интервал (те. улучшающие пространственную локальность), и методы, уменьшающие интервал переиспользования. Среди методов первого вида введение временных структур данных, которые более компактны, чем исходные, за счет того, что содержат лишь данные, требуемые в конкретном алгоритме, и изменение порядка обхода структуры данных, если порядок обработки узлов не имеет значения (как, например, в случае многих операций над матрицами, которые можно выполнять как "по строкам" , так и "по столбцам" ) Методы, уменьшающие интервал переиспользования, повышают вероятность того, что активно используемые данные все еще находятся в кэш-памяти к моменту их следующего использования. Разбиение структур данных на блоки применимо при последовательном характере доступа и уменьшает размер активного множества данных (и, следовательно, интервал переиспользования элемента этого множества) за счет обработки структуры данных блоками фиксированного размера. Распределение структур данных выполняет предварительный проход структур данных с целью распределения их по разделам в соответствии с некоторой хэш-функцией. Затем исходный алгоритм применяется к каждому разделу, что обеспечивает интервал переиспользования, не превышающий размер раздела. Логическое распределение не генерирует разделы в явном виде, но заменяет их на многократный проход по структуре данных, обрабатывая на каждой итерации лишь элементы, относящиеся к соответствующему разделу. Рассматривается также использование инструкций процессора для явной предвыборки в кэш-память, что возможно при псевдо-произвольном методе доступа, поскольку на очередной итерации известен возможный адрес следующего узла.

Четвертая глава посвящена алгоритмам для выполнения операций естественного соединения и соединения по предикатам над множествен-нозначными атрибутами. Для операции естественного соединения рассматриваются мульти-индексы — индексы, которые, в отличие от традиционных индексов, используемых в СУБД, строятся по нескольким, а не по одному отношению. Мульти-индекс позволяет за одну операцию поиска находить записи всех индексируемых отношений, имеющие данное значение индексируемого атрибута. При изменении индексируемых отношений мульти-индекс обновляется, а естественное соединение сводится к однократному просмотру мульти-индекса. Для мульти-индекса предлагается двухуровневая структура, на нижнем уровне которой находится стандартная страничная структура для хранения индексных записей, а на верхнем уровне — индексная структура, отображающая значения индексируемого атрибута в индексные записи. Возможны различные варианты организации верхнего уровня мульти-индекса, выбор между которыми должен выполняться в соответствии с соображениями частоты обновления индексируемых отношений, доступного объема основной памяти и т.д. Приводятся результаты экспериментальной проверки мульти-индекса в среде Memphis, демонстрирующие, что соединение с его использованием выполняется в ряде случаев более эффективно, чем с помощью метода, основанного на хэшировании. Здесь также содержится краткое описание среды Memphis, реализованной в рамках данной работы и использованной при проведении экспериментов в данной главе.

Вторая часть четвертой главы описывает исследование алгоритмов выполнения операции соединения по предикатам над атрибутами, значения которых не атомарны, а являются множеством элементов. Сначала рассматриваются несколько известных алгоритмов, предварительные эксперименты с которыми показывают, что наиболее эффективными являются алгоритмы, основанные на инвертированных списках. Два из этих алгоритмов, IFNL (Inverted File Nested Loops) и IFJ (Inverted File Join), являются предметом улучшения для СУБД-ОП. К этим алгоритмам применяются методы, описанные в третьей главе, в частности, метод логического распределения. Эта оптимизация оказывается эффективной для алгоритма

1Р.1, но не ШМЬ. что подтверждается приведенными экспериментальными результатами и объясняется аналитически. В результате данного исследования получен алгоритм 1РЛ(к), параметризуемый числом разделов — просмотров инвертированного файла. Дальнейшие эксперименты исследуют этот алгоритм: выясняется, как ведет себя алгоритм в зависимости от числа разделов и как выбирать оптимальное число разделов: изучается эффект сжатия инвертированных списков на поведение алгоритма; алгоритм сравнивается с другими известными алгоритмами и демонстрируется его преимущество Данный алгоритм показывает лучшую скорость работы. чем конкурирующие алгоритмы, и лучше масштабируется с ростом размера входных отношений. Дополнительную экономию памяти может обеспечить применение сжатия инвертированных списков.

Заключение содержит список основных результатов, полученных в работе.

Список литературы

[1] Гектор Гарсиа-Молина, Джеффри Д. Ульман, Дженнифер Уидом Системы баз данных. Полный курс. — Вильяме, 2003.

[2] К. Дж. Дейт. Введение в системы баз данных. 8-е издание.— Вильяме, 2005.

[3] М. Р. Когаловский. Энциклопедия технологий баз данных. — Финансы и статистика, 2002.

[4] Dali: A High Performance Main Memory Storage Manager. / H. V. Ja-gadish, D. F. Lieuwen, R. Rastogi et al. // Proc. of the VLDB 1994 Conference. — Morgan Kaufmann, 1994. — P. 48-59.

[5] DBMSs on a Modern Processor: Where Does Time Go? / A. Ailarnaki. D. J. DeWitt, M. D. Hill, D. A. Wood // Proc. of the VLDB 1999 Conference. — Morgan Kaufmann, 1999. — P. 266-277.

[6] Hankins R. A., Patel J. M. Effect of Node Size on The Performance of Cache-Conscious B+-trees. // Proc. of the SIGMETRICS 2003 Conference. - ACM, 2003. - P. 283-294.

[7] Hennessy J. L., Patterson D. A. Computer Architecture: A Quantitative Approach. — 3rd edition. — Morgan Kaufmann, 2002.

[8] Lehman T. J., Carey M. J. A Study of Index Structures for Main Memory Database Management Systems. // Proc. of the VLDB 1986 Conference. — Morgan Kaufmann, 1986.—P. 294-303.

[9] Rao J., Ross K. A. Cache Conscious Indexing for Decision-Support in Main Memory. // Proc. of the VLDB 1999 Conference. — Morgan Kaufmann, 1999. - P. 78-89.

[10] Rao J., Ross K. A. Making B+-Trees Cache Conscious in Main Memory. // Proc. of the SIGMOD 2000 Conference. - ACM, 2000. - P. 475-486.

[11] Smith A. J. Cache Memories. // ACM Comput. Surv.— 1982, — Vol. 14, no. 3. - P. 473-530.

Работы автора по теме диссертации

1. D.Shaporenkov. Multi-Indices — A Tool for Optimizing Join Processing in Main Memory. Proceedings of the Sixth International Baltic Conference on Databases and Information Systems (Doctoral Consortium), Vol. 2. - Riga, Latvia, 2004. - P. 105-114.

2. Шапоренков Д.А. Сравнение производительности алгоритмов для выполнения соединения по предикату включения множеств в основной памяти. Труды Первого весеннего коллоквиума молодых исследователей в области баз данных и информационных систем (SYRCoDIS). - Санкт-Петербург, 2004. — с. 17-21.

3. Шапоренков Д.А. Распределение инвертированных списков для эффективного выполнения соединения по предикату включения множеств в основной памяти. Труды Второго весеннего коллоквиума молодых исследователей в области баз данных и информационных систем (SYRCoDIS). - Санкт-Петербург, 2005. — с. 40-46.

4. D.Shaporenkov. Efficient Main-Memory Algorithms for Set Containment Join Using Inverted Lists. Proceedings of the Ninth East-European Conference on Advances in Databases and Information Systems — Tallinn, Estonia, 2005. - P. 139-152.

Подписано в печать 03.03.2006г., Заказ №54277 Формат бумаги 60x84/16 Тираж 100 экз. Отпечатано в типографии «иМРЫЫТ» 19119, Санкт-Петербург, ул.Достоевского, 44. Тел./факс:: (812) 712-5814

OjOO G± OA

- 5 4 04

1. Введение

2. Предпосылки СУБД-ОП

2.1. Особенности архитектур современных компьютеров.

2.1.1. Процессоры.

2.1.1.1. Внутренний параллелизм.

2.1.1.2. Предсказание переходов.

2.1.2. Система памяти

2.1.2.1. Кэш-память.

2.1.2.2. Характеристики кэш-памяти.

2.1.2.3. Виды кэш-промахов.

2.1.2.4. Явное управление кэш-памятью.

2.1.2.5. Устройство трансляции адресов

2.1.2.6. Стоимость доступа к памяти.

2.1.2.7. Методы измерения эффективности доступа к памяти.

2.1.2.8. Пример.

2.1.3. Особенности многопроцессорных систем.

2.2. Архитектура традиционных СУБД и СУБД-ОП.

2.2.1. Компоненты архитектуры традиционной СУБД

В течение нескольких последних десятилетий системы управления базами данных (СУБД) стали одним из основных приложений вычислительной техники. Сегодня успешная деятельность многих организаций, таких как государственные учреждения, предприятия, банки, магазины напрямую зависит от СУБД. Объемы данных, хранимые в таких системах, огромны и часто достигают многих терабайт [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, может иметь вид:

CREATE TABLE Citizens (ID int NOT NULL,

FirstName char (10) NOT NULL, LastName char (25) NOT NULL, Address char (30) NOT NULL, Phone char (7))

Размер записи этого отношения составит примерно 80 байт, и для хранения информации о всех жителях города потребуется, таким образом, около 400 мегабайт. С учетом того, что в 2005 году объем ОП в 2 гигабайта не является редкостью для серверной системы, вся БД (состоящая из нескольких отношений) может быть целиком размещена в памяти сервера СУБД.

Проблемы оптимизация выполнения запросов в традиционных реляционных СУБД хорошо формализованы и исследованы [1]. На протяжении последних десятилетий были разработаны критерии эффективности методов выполнения запросов, и современные реляционные СУБД, как правило, способны выбирать наиболее эффективные пути выполнения запросов без помощи пользователя или администратора [1, б]. Однако с переносом данных в ОП традиционные критерии эффективности перестают иметь смысл [11, 21]: в традиционных СУБД оптимизация запросов обычно направлена на минимизацию числа обращений к медленной вторичной памяти, а в СУБД-ОП такие обращения не происходят вообще. Таким образом, необходимы новые критерии эффективности и, возможно, иные методы выполнения запросов.

Эффективное выполнение запросов в СУБД-ОП и является основным предметом данной работы. Наши исследования касаются эффективных индексных структур и методов выполнения запросов, которые позволяют полностью использовать возможности современных компьютеров. Мы систематизируем методы оптимизации работы с данными в ОП, а также предлагаем ряд новых индексных структур и алгоритмов выполнения операций и оцениваем их эффективность [51, 52, 54, 53].

Данная работа имеет следующую структуру. В главе 2 рассматриваются особенности современных компьютерных архитектур и обосновывается, почему традиционные СУБД, рассчитанные на хранение данных на диске, не позволяют получить максимальную производительность при использовании их в качестве СУБД-ОП. Там же показано, какие компоненты СУБД требуют пересмотра для СУБД-ОП. Глава 3 описывает общие идеи, которые применяются для повышения эффективности алгоритмов и структур данных в предположении, что данные располагаются в основной памяти. Эти идеи проиллюстрированы небольшими примерами, поясняющими их применение для простых задач, которые являются частями более сложных проблем, возникающих при реализации СУБД. В главе 4 мы применяем эти общие идеи к задачам оптимизации операции естественного соединения и соединения по предикату над множественнозначными атрибутами. Мы предлагаем мульти-индексы — структуру, которая в компактном виде хранит результат естественного соединения и допускает быстрое обновление при изменении индексируемых отношений. Мы также исследуем производительность нескольких алгоритмов для выполнения операции соединения по предикату над множественнозначными атрибутами в СУБД-ОП и выясняем, что наиболее эффективными являются методы, основанные на использовании инвертированных списков. Мы предлагаем модификацию этих методов, учитывающую специфические для СУБД-ОП критерии эффективности, и экспериментально демонстрируем, что эта модификация сокращает время выполнения соединения.

Глава 2.

Предпосылки СУБД-ОП

4.3.5. Выводы

В данном разделе мы исследовали производительность различных алгоритмов для выполнения операции соединения по предикату над множе-ственнозначными атрибутами в предположении, что данные находятся в основной памяти. Наши исследования показывают, что алгоритмы, основанные на использовании инвертированных файлов - IFNL, IFJ и IX, оказываются значительно эффективнее, чем алгоритмы, применяющие для ускорения соединения сигнатуры и метод распределения. Мы также предложили специализированную индексную структуру - индекс пересечения, которая позволяет свести вычисление результата соединения к простому обходу этой структуры.

Мы рассмотрели модифицированные варианты алгоритмов IFNL и IFJ, которые используют технику логического распределения для сокращения активного набора данных и увеличения шансов их переиспользования в кэш-памяти. Этот прием оказался эффективным для алгоритмаIFJ, но не для алгоритма IFNL, поскольку для IFNL дополнительные накладные расходы, связанные с необходимостью выбора значения для обработки на очередном этапе, перевешивают преимущества уменьшающегося количества кэш-промахов. Это означает, что алгоритм IFNL больше подходит для отношений небольших размеров, в то время как алгоритм IFJ более пригоден для больших отношений, поскольку он лучше масштабируется с ростом \S\. Мы также изучили эффект сжатия инвертированных файлов и промежуточных результатов и сделали вывод, что основным положительным эффектом сжатия является сокращение требуемого объема памяти, но это достигается только в случае, когда длины инвертированных списков и размер результата достаточно велики. Как средство уменьшения размера списков и сокращения количества кэш-промахов первого обращения сжатие себя не оправдывает, поскольку вызывает значительные накладные расходы на распаковку сжатых данных.

Глава 5.

Заключение

В данной работе исследованы аспекты СУБД-ОП, относящиеся к индексированию данных и эффективному выполнению запросов. В работе получены следующие основные результаты:

1. Предложены критерии оценки эффективности структур данных и алгоритмов для СУБД-ОП, учитывающие неоднородность доступа к основной памяти в современных вычислительных системах.

2. Построена классификация, обобщающая большинство известных методов оптимизации структур данных и алгоритмов для эффективного использования кэш-памяти процессора.

3. Реализована среда для проведения экспериментов с индексными структурами и алгоритмами выполнения реляционных операций в основной памяти Memphis, которая использована при проведении многих экспериментальных проверок.

4. Предложен и экспериментально проверен метод оптимизации операции соединения на основе мульти-индексов в СУБД-ОП, показана его сравнительная эффективность по сравнению с методом хэш-соединения в зависимости от параметров входных отношений.

5. Исследованы различные алгоритмы для выполнения операции соединения по предикату над множественнозначными атрибутами в

СУБД-ОП, предложена модификация алгоритма IFJ (Inverted File Join), основанного на использовании инвертированных файлов, для лучшего использования кэш-памяти и экспериментально продемонстрировано, что эта модификация приводит к уменьшению времени выполнения соединения.

Данная работа демонстрирует необходимость применения специальных методов для реализации полноценных СУБД-ОП, которые эффективно используют кэш-память процессора, устройство предсказания переходов и другие особенности архитектуры современных компьютеров. Предложенные в работе алгоритмы могут применяться в СУБД-ОП для поддержки расширенного набора реляционных операций, включающего операции над множественнозначными атрибутами, во многих случаях предоставляющими естественный способ выражения понятий предметной области. Рассмотренные методы имеют также важное значение при исследовании следующего шага в развитии СУБД с точки зрения использования архитектурных особенностей компьютерных систем — СУБД, которые могут эффективно работать с данными на нескольких уровнях иерархии памяти, обеспечивая оптимальное быстродействие как для данных, находящихся на диске, так и для данных в основной памяти.

1. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. / Пер. с англ. — М.:Вильямс, 2003.

2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. / Пер. с англ. — М.:Мир, 1998.

3. К.Дою.Дейт. Введение в системы баз данных. 8-е издание. / Пер. с англ. — М.:Вильямс, 2005.

4. М.Р.Когаловский. Энциклопедия технологий баз данных.— М.:Финансы и статистика, 2002.

5. Руссинович М., Соломон Д. Внутреннее устройство Microsoft Windows 2000. / Пер. с англ. — СПб.:Русская редакция : Питер, 2001.

6. Access Path Selection in a Relational Database Management System. / P. G. Selinger, M. M. Astrahan, D. D. Chamberlin et al. // Proc. of the SIGMOD 1979 Conference. ACM, 1979.- P. 23-34.

7. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. / C. Mohan, D. J. Haderle, B. G. Lindsay et al. // ACM Trans. Database Syst.— 1992. Vol. 17, no. 1. - P. 94-162.

8. Bayer R., McCreight E. M. Organization and Maintenance of Large Ordered Indexes. // Record of the SIGFIDET 1970 Workshop. ACM, 1970. - P. 107-141.

9. Bohannon P., Mcllroy P., Rastogi R. Main-Memory Index Structures with Fixed-Size Partial Keys. // Proc. of the SIGMOD 2001 Conference.-2001.

10. Boncz P. A., Manegold S., Kersten M. L. Database Architecture Optimized for the New Bottleneck: Memory Access. // Proc. of the VLDB 1999 Conference. — Morgan Kaufmann, 1999. — P. 54-65.

11. Boncz P., Kersten M. Monet: an Impressionist Sketch of an Advanced Database System. — 1995.

12. Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems. / S. K. Cha, S. Hwang, K. Kim, K. Kwon // Proc. of the VLDB 2001 Conference. — Morgan Kaufmann, 2001.-P. 181-190.

13. Cai J.-Y. et al. On the Complexity of Join Predicates // Proc. of the PODS 2001 Conference. 2001. - P. 207-214.

14. Chatterjee S., Sen S. Cache-Efficient Matrix Transposition. // Proc. of the HPCA 2000 Conference. 2000. - P. 195-205.

15. Chilimbi Т. M., Hill M. D., Larus J. R. Cache-Conscious Structure Layout, // Proc. of the PLDI 1999 Conference. 1999. - P. 1-12.

16. Chilimbi Т. M., Larus J. R. Using Generational Garbage Collection To Implement Cache-Conscious Data Placement. // Proc. of the ISMM 1998 Conference. 1998. - P. 37-48.

17. Copeland G. P., Khoshafian S. A Decomposition Storage Model. // Proc. of the SIGMOD 1985 Conference. ACM Press, 1985. - P. 268-279.

18. Dali: A High Performance Main Memory Storage Manager. / H. V. Jagadish, D. F. Lieuwen, R. Rastogi et al. // Proc. of the VLDB 1994 Conference. — Morgan Kaufmann, 1994. — P. 48-59.

19. Data Compression in Full-Text Retrieval Systems. / Т. C. Bell, A. Moffat,

20. C. G. Nevill-Manning et al. // JASIS. 1993. - Vol. 44, no. 9. - P. 508531.

21. DBMSs on a Modern Processor: Where Does Time Go? / A. Ailamaki,

22. D. J. DeWitt, M. D. Hill, D. A. Wood // Proc. of the VLDB 1999 Conference. Morgan Kaufmann, 1999. - P. 266-277.

23. Denning P. Locality (unpublished manuscript). — 2005.

24. Graefe G. Query Evaluation Techniques for Large Databases. // ACM Comput. Surv.- 1993. Vol. 25, no. 2. - P. 73-170.

25. Hankins R. A., Patel J. M. Data Morphing: An Adaptive, Cache-Conscious Storage Technique. // Proc. of the VLDB 2003 Conference. — 2003.-P. 417-428.

26. Helmer S., Moerkotte G. Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. // Proc. of the VLDB 1997 Conference. — Morgan Kaufmann, 1997. — P. 386-395.

27. Hennessy J. L., Patterson D. A. Computer Architecture: A Quantitative Approach. — 3rd edition. — Morgan Kaufmann, 2002.

28. Improving Hash Join Performance through Prefetching. / S. Chen, A. Ailamaki, P. B. Gibbons, Т. C. Mowry // Proc. of the HDMS 2004 Conference. — 2004.

29. Intel Corporation. IA-32 Intel Architecture Optimization Reference Manual. 2005.

30. Intel Corporation. IA-32 Intel Architecture Software Developer's Manuals. 2005.

31. Intel Corporation. Intel С++ Compiler Documentation. — 2005.

32. Intel VTune Performance Analyzer // http://www.mtel. com/software/products/vtune/.

33. Kim K., Cha S. K., Kwon K. Optimizing Multidimensional Index Trees for Main Memory Access. // Proc. of the SIGMOD 2001 Conference.— 2001.

34. Lehman T. JCarey M. J. A Study of Index Structures for Main Memory Database Management Systems. // Proc. of the VLDB 1986 Conference. — Morgan Kaufmann, 1986. P. 294-303.

35. Litwin W. Linear Hashing: A New Tool for File and Table Addressing. // Proc. of the VLDB 1980 Conference. IEEE Computer Society, 1980. -P. 212-223.

36. Li Z., Ross K. A. Fast Joins Using Join Indices. // VLDB Journal — 1999.-Vol. 8, no. l.-P. 1-24.

37. Mamoulis N. Efficient Processing of Joins on Set-Valued Attributes // Proc. of the SIGMOD 2003 Conference. 2003. - P. 157-168.

38. Manegold S., Boncz P. A., Kersten M. L. What Happens During a Join? Dissecting CPU and Memory Optimization Effects. // Proc. of the VLDB 2000 Conference. Morgan Kaufmann, 2000. - P. 339-350.

39. Manegold S., Boncz P. A., Kersten M. L. Generic Database Cost Models for Hierarchical Memory Systems. // VLDB. 2002. - P. 191-202.

40. Manegold S., Boncz P. A., Kersten M. L. Optimizing Main-Memory Join on Modern Hardware. // IEEE Trans. Knowl. Data Eng. — 2002. — Vol. 14, no. 4.-P. 709-730.

41. Manegold S., Boncz P. A., Nes N. Cache-Conscious Radix-Decluster Projections. // Proc. of the VLDB 2004 Conference. — Morgan Kaufmann, 2004. P. 684-695.

42. Manegold S., Boncz P. Cache-Memory and TLB Calibration Tool // http://monetdb. cwi. nl/ Calibrator/doc/calibrator.pdf.

43. Nonlinear Array Layouts for Hierarchical Memory Systems. / S. Chatterjee, V. V. Jain, A. R. Lebeck et al. // Proc. of the ICS 1999 Conference. 1999.- P. 444-453.

44. Oracle Corporation. SQL 2003 Standard Support in Oracle Database lOg. An Oracle White Paper. 2003.

45. PennerM., Prasanna V. K. Cache-Friendly Implementations of Transitive Closure. // Proc. of the PACT 2001 Conference.- IEEE Computer Society, 2001. P. 185-.

46. Rao J., Ross K. A. Cache Conscious Indexing for Decision-Support in Main Memory. // Proc. of the VLDB 1999 Conference. — Morgan Kaufmann, 1999. P. 78-89.

47. Rao J., Ross K. A. Making B+-Trees Cache Conscious in Main Memory. // Proc. of the SIGMOD 2000 Conference. ACM, 2000. - P. 475-486.

48. Ross K. A. Selection Conditions in Main Memory. // ACM Trans. Database Syst.- 2004.- Vol. 29.- P. 132-161.

49. Set Containment Joins: The Good, The Bad and The Ugly. / K. Ramasamy, J. M. Patel, J. F. Naughton, R. Kaushik // Proc. of the VLDB 2000 Conference. Morgan Kaufmann, 2000. - P. 351-362.

50. Shaporenkov D. Multi-Indices A Tool for Optimizing Join Processing in Main Memory // Proc. of the Baltic DBIS 2004 Conference.- 2004.-P. 105-114.

51. Shaporenkov D. Performance Comparison of Main-Memory Algorithms for Set Containment Joins // Proc. of the SYRCoDIS 2004 Symposium.— 2004.-P. 17-21.

52. Shaporenkov D. Efficient Main-Memory Algorithms for Set Containment Join Using Inverted Lists // Proc. of the ADBIS 2005 Conference. — 2005.-P. 139-152.

53. Shaporenkov D. Partitioning Inverted Lists for Efficient Evaluation of Set-Containment Joins in Main Memory // Proc. of the SYRCoDIS 2005 Symposium. 2005. - P. 40-46.

54. Shatdal A., Kant C., Naughton J. F. Cache Conscious Algorithms for Relational Query Processing. // Proc. of the VLDB 2004 Conference. — Morgan Kaufmann, 1994. P. 510-521.

55. Smith A. J. Cache Memories. // ACM Comput. Surv.- 1982.- Vol. 14, no. 3. P. 473-530.

56. Sokolinsky L. B. Lfu-k: An effective buffer management replacement algorithm. // Proc. of the DAS FA A 2004 Conference. 2004,- P. 670681.

57. Stallings W. Computer Organization and Architecture: Designing for Performance. — 6th edition. — Prentice Hall, 2003.

58. Stallings W. Operating Systems: Internals and Design Principles. — 5th edition. — Prentice Hall, 2003.

59. Sun Microsystems Inc. UltraSPARC IV Processor Specifications. — 2005.

60. Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software // Dr.Dobb's Journal — 2005. — Vol. 30, no. 3.

61. The Architecture of the Dali Main-Memory Storage Manager. / P. Bohannon, D. F. Lieuwen, R. Rastogi et al. // Multimedia Tools Appl — 1997. Vol. 4, no. 2. - P. 115-151.

62. Valduriez P. Join Indices. Ц ACM Trans. Database Syst1987.-Vol. 12, no. 2.-P. 218-246.

63. Weaving Relations for Cache Performance. / A. Ailamaki, D. J. DeWitt, M. D. Hill, M. Skounakis // Proc. of the VLDB 2001 Conference. Morgan Kaufmann, 2001.- P. 169-180.

64. Whaley R. C., Dongarra J. Automatically Tuned Linear Algebra Software. // Proc. of the PPSC 1999 Conference. 1999.

65. Witten I., Moffat A., Bell T. Managing Gigabytes : Compressing and Indexing Documents and Images.— 2nd edition.— Morgan Kaufmann, 1999.

66. Zhou J., Ross K. A. Implementing Database Operations Using SIMD Instructions. // Proc. of the SIGMOD 2002 Conference. ACM, 2002.-P. 145-156.