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

www.dbpd.com

Support for Data Warehouses

Patrick O'Neil
Professor of Computer Science at the University of Massachusetts at Boston

www.cs.umb.edu/~poneil

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

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

В статье приводится введение в основные понятия эффективных методов индексации для поддержки приложений класса 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 окажется более эффективным, чем цикл, в котором выполняется логическое умножение битовых шкал, длина каждой из которых равна общему числу строк в таблице. Но при плотности битовой шкалы большей, чем 1/100, алгоритм на основе битовых шкал работает быстрее. Аналогично обстоят дела с алгоритмами для выполнения операций 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, где отсутствуют параллельные изменения, индексы соединения позволяют повысить эффективность выполнения запросов лишь за счет расходов на дополнительное дисковое пространство.

Как сделаны битовые индексы в продуктах компании Informix, предназначенных для поддержки 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 старается добиться еще более высоких показателей эффективности в будущем.