Обзор статей журнала DataBase Programming & Design
vol.10, N 2, February 1997

Support for Data Warehouses

Patrick O'Neil
Professor of Computer ScienceScience ("Наука")— академический журнал Американской ассоциации содействия развитию науки (AAAS). Считается одним из самых авторитетных научных журналов. Журнал рецензируемый, выходит еженедельно, и имеет примерно 130,000 подписчиков бумажного издания. Так как подписка организаций и доступ через интернет образуют гораздо большую аудиторию, число его читателей оценивается в один миллион человек. at the University of Massachusetts at BostonBoston — американская рок-группа, которая за тридцать лет своего существования выпустила всего пять студийных альбомов.

www.cs.umb.edu/~poneil

Конечно, использование больших складов данных невозможно без использования параллелизма. Чтобы просто прочитать терабайт данных с использованием одного дискового устройства, потребуется не меньше недели. РаспараллеливаниеРаспараллеливание программ — процесс адаптации алгоритмов, записанных в виде программ, для их эффективного исполнения на вычислительной системе параллельной архитектуры (в последнее время, как правило, на многопроцессорной вычислительной системе). Заключается либо в переписывании программ на специальный язык, описывающий параллелизм и понятный трансляторам целевой вычислительной системы, либо к вставке специальной разметки (например, инструкций MPI или OpenMP). запросов позволяет выполнять один запрос на большом числе недорогих процессоров. Оптимизатор запросов получает возможность эффективного использования всех аппаратных ресурсов, обеспечивая гарантированное выполнение запроса при выходе из строя некоторых процессоров и максимально эффективное выполнение высокоприоритетных запросов.

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

В статье приводится введение в основные понятия эффективных методов индексации для поддержки приложений класса DSS (Decision Support System): битовые (bitmap) индексы и индексы соединений. Затем рассматриваются новые возможности индексации, внедренные в Informix Extended Parallel Server (XPS)

Битовые индексы похожи на традиционные индексы, основанные на списках идентификаторов строк (RID - Row Identifier). Но битовые индексы в некоторых случаях позволяют получить существенный выигрыш в производительности.

Начнем с определения списка RID. Каждой строке в таблице приписывается RID, который можно рассматривать как указатель на строку на диске. Обычно RID состоит из номера страницы на диске и номера позиции записи на этой странице. Набор строк с данным свойством может быть представлен как список RID этих строк. В большинстве СУБД используются 4-байтовые RID (хотя в Oracle RID имеет длину по крайней мере 6 байт). Традиционно списки RID использовались в индексах для определения набора строк, ассоциированных с каждым значением некоторого индексируемого столбца. Если предположить потребностьПотребность, нужда— внутреннее состояние психологического или функционального ощущения недостаточности чего-либо и проявляются в зависимости от ситуационных факторов. в индексе на таблице SALES, содержащей 100 миллионов строк и включающей столбец department c 40 разными значениями, то для каждого значения этого столбца мы получим список RID, который в среднем будет соответствовать 2.5 миллионам строк.

При наличии громадного числа RID, ассоциированных с каждым значением department, трудно рассчитывать, что удастся целиком переместить список RID в основную память. Список разбивается на фрагменты по несколько сотен RID, которые могут быть помещены в последовательные листовые узлы B-дерева. Для каждого фрагмента можно хранить в B-дереве только одно значение department, так что критически остается лишь потребность в хранении 100 миллионов 4-байтовых RID.

Теперь мы готовы ввести идею битовой индексации. В таблице, для которой используется эта техникаТехника (др.-греч. от — искусство, мастерство, умение)— это общее название различных приспособлений, механизмов и устройств, не существующих в природе и изготовляемых человеком., все строки должны быть перенумерованы: 0, 1, 2, ..., N-1. Нумерация строк должна производиться в соответствии с порядком их RID (физически последовательно относительно расположения строк на диске). Требуется метод преобразования номера строки в RID и наоборот. Теперь, если имеется последовательность из N бит, установим k-тый бит в 1, если строка с номером k входит в набор строк, а в противном случае - в 0. Битовый индекс на SALES по столбцу department аналогичен тому, который основан на RID, но вместо фрагментов RID в нем используются соответствующие битовые фрагменты. Каждый битовый фрагмент будет занимать 12.5 Мб, так что вполне вероятно разместить его на последовательных страницах диска. Отношение числа битов, установленных в 1, к общей длине набора бит, называется плотностью этого набора и аналогична селективности условия выборки. Фрагменты с низкой плотностью можно компрессировать. Пока же будем считать, что все фрагменты обладают высокой плотностью.

В этом случае полный битовый индекс требует на листовом уровне чуть больше 500 Мб внешней памяти, т.е. больше, чем индекс, основанный на RID. Однако ситуация меняется, если индексируемый столбец содержит мало различных значений. Если, например, таблица SALES содержит столбец gender (пол) со всего двумя значениями M и F, то для листового уровня битового индекса потребуется всего 25 Мб, в то время как для RID-индекса по-прежнему было бы нужно иметь 400 Мб. Для индексов с менее чем 32 значениями битовые индексы позволяют экономить память.

Однако наиболее важным свойством неупакованных битовых индексов является не экономия памяти, а возможностьВозможность — направление развития, присутствующее в каждом явлении жизни; выступает и в качестве предстоящего, и вполне объяснимо рациональным путем: в каждой возможности присутствует вероятная невозможность, «возможность невозможного». Возможность не определяется познанием того, что может быть. Познание вероятностей, возможностей не всегда влияет на нашу возможность. На изучении возможности основывается, главным образом, исследование бытия и события. существенно повысить скорость выполнения операций AND, OR, NOT и COUNT. Предположим, что имеются два битовых фрагмента B1 и B2, где B1 представляет свойство gender = 'M', а B2 - department = 'sports'. Тогда для получения битового фрагмента, соответствующего свойству B1 & B2, требуется всего лишь выполнить поразрядное логическое умножение B1 и B2.

Для выполнения операции AND над двумя списками RID требуется более сложная техника: слияние с пересечением. Нужно использовать два курсора, каждый из которых продвигается по одному из списков, и в результирующем списке остаются те RID, которые встречаются в каждом из исходных списков.

Конечно, если списки-операнды включают только по несколько десятков RID, то цикл со списками RID окажется более эффективным, чем цикл, в котором выполняется логическое умножение битовых шкал, длина каждой из которых равна общему числу строк в таблицБогуслав Таблиц (словацк. Bohuslav Tablic (Tablicz); 6 сентября 1769, Ческе Брезово, Словакия — 21 января 1832, Костолне Моравце, Словакия) — чешско-словацкий писатель, священник, деятель возрождения словаков-лютеран, подобно тому как Бернолак является деятелем возрождения словаков-католиков. Таблиц учредил в Пресбурге «Общество чешско-словацкой литературы и языка» с целью издавать на понятном народу чешском языке простонародные и школьные книги. Учреждение этого общества было причиной если не процветания словацкой литературы, то появления в пресбургском лицее кафедры словацкого языка, для чего общество собрало большой капитал. Занять кафедру приглашен был Юрай Палкович. Общество скоро распалось, но кафедра продолжала существовать. Молодёжь имела возможность слушать историю своего народа на родном языке. В 1812 г. Таблиц был одним из основателей нового «Литературного общества Горных Городов» (Bergstdte), задававшегося прежней целью; результатом было открытие кафедры словацкого языка и в Банской Штьявнице. Это общество также скоро распалось. Таблиц писал очень много и по различным специальностям. Первое место занимают его «Poesie» (Вацов, 1806-1812). К ним приложены биографии известных словацких деятелей. Его «Sloventi verovci» (Вацов, 1805-1809) — отрывки из произведений древних словацких писателей, в то время почти уже позабытых. Перу Таблица принадлежит также много книг для народа, изданных двумя упомянутыми обществами.е. Но при плотности битовой шкалы большей, чем 1/100, алгоритм на основе битовых шкал работает быстрее«Быстрее пули» (англ.Faster) — фильм-боевик режиссера Джорджа Тиллмана мл. Мировая премьера назначена на 4 ноября 2010 года (в России — 2 декабря).. Аналогично обстоят дела с алгоритмами для выполнения операций OR, NOT и COUNT.

Если битовая шкала становится очень разреженной, то битовые индексы работают плохо по сравнению с RID-индексами не только в связи с нагрузкой на процессор, но и по причине большого числа обменов с внешней памятью. Для решения обеих проблем требуется какой-либо метод сжатия, который позволил бы сократить расходы внешней памяти, но в то же время позволил бы по-прежнему быстро выполнять операции AND, OR, NOT и COUNT. Один из подходов состоит в совместном использовании битовой и RID индексации: когда битовый фрагмент становится слишком разреженным, он заменяется на RID-фрагмент. В других подходах используется техника кодирования битовых шкал. В этом случае становится сложно эффективно выполнять перечисленные выше операции между сжатой и несжатой шкалами. Потребность нахождения техники сжатия, которая бы не тормозила выполнение этих операций является наиболее важной проблемой битовой индексации.

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

Индекс соединения обеспечивает средства, с помощью которых СУБД может эффективно транслировать ограничения на столбец одной таблицы в ограничения на другую таблицу путем стандартного соединения. Предположим, что мы имеем таблицу SALES, каждая строка которой является агрегацией данных о продажах конкретного продукта для конкретного заказчика в конкретный день (это называется грануляцией агрегации). SALES является таблицей фактов и соединяется с таблицами, представляющими три измерения,- CUSTOMER, PRODUCT и TIME через внешние ключи cid, pid и day. Предположим, что следующий запрос является распространенным:

(SEL1)



SELECT SUM(dollar_sales), SUM(unit_sales)

 FROM SALES s, CUSTOMERS c, PRODUCTS p, TIME t

 WHERE s.cid = c.cid AND s.pid = p.pid AND s.day = t.day

 AND t.month = 'May95' AND p.package_type = 'box'

  AND c.gender = 'M'

Желательно заранее иметь индексы для эффективного выполнения этого запроса. В этом запросе столбец gender принадлежит таблице CUSTOMER, но только столбцы таблицы SALES агрегированы; ограничение на gender кажется естественным выполнять после соединения. Но предположим, что производится некоторая предварительная подготовка, заключающаяся в соединении всех строк SALES со всеми соответствующими строками CUSTOMER (для каждой продажи имеется только один заказчик) и ограничим строки SALES условием, что заказчики - мужчиныМужчина— человек мужского пола, одного из двух полов внутри рода людей (человек другого поланазывается женщиной).. В результате будет выбрано около половины строк SALES, что лучше всего представляется битовой шкалой. Аналогично, можно ограничить строки SALES условием, что заказчики - женщиныЖенщина — человек женского пола, один из двух полов, образующих род людей (другой биологический пол— мужчина)., и создать соответствующую битовую шкалу. Теперь создадим индекс на SALES с двумя значениями "M" и "F" и свяжем две ранее полученных шкалы с этими значениями. Реально мы создали индекс по половому признаку для SALES, хотя сама таблица SALES не содержит такого столбца. Этот индекс делает не обязательным реально выполнять соединение между SALES и CUSTOMERS при выполнении запроса. Такой индекс называется индексом соединения внешнего столбца (FCJ - Foreign Column Join). Чтобы еще больше сократить работу по выполнению запроса, можно создать на таблице SALES FCJ-индексы для p.package_type и t.month. Тогда оптимизатор запросов сможет выполнить этот запрос с использованием только индексов на таблице SALES. FCJ-индекс является вариантом битового индекса соединения, предложенного в статье Valduriez P., "Join Indexes", ACM TODS, 12 (2), 218-246, June 1987.

Вместо создания трех FCJ-индексов можно создать многотабличный индекс соединения (MTJ - Multi-Table Index) на таблице SALES, объединяющий столбцы нескольких таблиц - t.month, p.package_type и c.gender. Хотя такие индексы позволяют еще больше повысить эффективность соединения, их наличие может привести к определенной потере гибкости. Кроме того, по соображениям эффективности, возможно, пришлось бы создать MTJ-индекс для каждой комбинации внешних таблиц, которая характерна для данной рабочей загрузки системы. С другой стороны, число FCJ-индексов возрастает только линейно с увеличением числа внешних столбцов. По этой причине MTJ-индексы могут быть полезны только в исключительно специальных ситуациях.

Возникает вопрос: если понадобится создать много индексов соединения, не приведет ли это к деградации системы? Ответ: нет. На платформах DSS, где отсутствуют параллельные изменения, индексы соединения позволяют повысить эффективность выполнения запросов лишь за счет расходов на дополнительное дисковое пространство.

Как сделаны битовые индексы в продуктах компанииЮридическое лицо— созданная и зарегистрированная в установленном законом порядке организация, которая имеет в собственности, хозяйственном ведении или оперативном управлении обособленное имущество и отвечает по своим обязательствам этим имуществом, может от своего имени приобретать и осуществлять имущественные и личные неимущественные права, нести обязанности, быть истцом и ответчиком в суде. Юридические лица должны иметь самостоятельный баланс или смету. InformixInformix— семейство систем управления реляционными базами данных (СУБД), выпускаемых компанией IBM. Informix позиционируется как флагман среди СУБД IBM, предназначенный для онлайновой обработки транзакций (OLTP), а также как СУБД для интегрированных решений., предназначенных для поддержки DSS? Новая форма индекса, называемая GK-индекс (Generalized Key) представляет гибкую комбинацию традиционных и битовых индексных структур. Вот синтаксис оператора CREATE GK INDEX:

CREATE GK INDEX INDEXNAME

ON T

 (SELECT AS KEY X.c1 {, Y.c2, ...}

   FROM T, X, Y, ...

   WHERE }

 );

В результате будет создан именованный индекс на таблице T. Раздел SELECT AS KEY явно определяет значение ключа индекса, который может быть вычислен для каждой строки T, и индекс позволяет выбрать строку T с этим ключом. Ключ индекса может состоять из набора конкатенированных значений столбцов таблиц X, Y, ..., а раздел WHERE будет специфицировать (среди прочего), каким образом строки со столбцами, значения которых входят в значение ключа индекса, соединяются в результирующую строку. Список SELECT не порождает какого-либо порядка таблиц. Он означает только то, что столбцы перечисленных таблиц могут выбираться в любом порядке, но из таблицы T будет выбираться только один столбец; в разделе FROM не требуется указывать несколько таблиц.

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

CREATE GK INDEX ORDERGENDER

ON SALES

 (SELECT AS KEY c.gender

   FROM SALES s, CUSTOMER c

   WHERE s.cid = c.cid);

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

SELECT SUM(s.dollar_sales) FROM CUSTOMER c, SALES s

 WHERE s.cid = c.cid AND c.gender = 'M';



SELECT SUM(dollar_sales) FROM SALES

 WHERE CID IN (SELECT CID FROM CUSTOMERS WHERE

  c.gender = 'M');

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

CREATE GK INDEX ORDERSMPG

ON SALES

 (SELECT AS KEY t.month, p.package_type, c.gender

  FROM SALES s, TIME t, PRODUCT p, CUSTOMER c

  WHERE s.day = t.day AND s.pid = p.pid

   AND s.cid = c.cid);

Формат GK-индекса настолько гибок, что поддерживает совершенно новые возможности индексации, такие как индекс на виртуальном столбце, представленном выражением над базовыми столбцами. Предположим, что в таблице SALES определяется новый виртуальный столбец по формуле:

profit_per_unit = (dollar_sales - dollar_cost) / unit_sales

Все три составляющих являются реальными столбцами таблицы SALES, так что вычисление производится легко для каждой строки SALES. Такой виртуальный столбец может быть определен с помощью операторов CREATE TABLE или ALTER TABLE диалекта языка SQL компании Informix. После этого виртуальный столбец можно использовать в запросах точно так же, как и реальные столбцы. Для этого столбца можно создать GK-индекс с помощью простого оператора

CREATE GK INDEX PROFITX

ON SALES

 (SELECT AS KEY profit_per_unit

  FROM SALES);

Селективный индекс напоминает набор строк, выбираемых из таблицы при задании в разделе WHERE некоторого набора ограничений. Этот набор строк, представленный битовой строкой, называется foundset ("найденным набором"). Если имеется желание ограничить вниманиеВнимание— избирательная направленность восприятия на тот или иной объект. в таблице EMPLOYEES "технарями", можно определить следующий селективный GK-индекс:

CREATE GK INDEX TECHIES

ON EMPLOYEES

 (SELECT AS KEY 'constant'

   FROM EMPLOYEES

   WHERE hobby = 'math' AND reading = 'Dibert');

Informix старается добиться еще более высоких показателей эффективности в будущем.