Базы данных Oracle - статьи

         

Столбцы с небольшим количеством значений


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

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

Классическим примером применимости индекса на основе битовых карт является экстремальный случай столбца, представляющего пол. В этом столбце может быть всего два значения (или три, если включить требуемое стандартом ISO значение "n/a" - неизвестен). Мы будем чуть менее экстремальны и рассмотрим пример, основанный на странах, образующих Соединенное Королевство: Англия, Ирландия, Шотландия и Уэльс.

Пусть используются блоки размером 8 Кбайт и строки (весьма типичным) размером 200 байтов, что дает 40 строк в блоке. Вставим в таблицу несколько миллионов строк, обеспечив равномерно случайное распределение по странам. Таким образом, в среднем в каждом блоке будет по 10 строк для каждой страны.

Если использовать индекс на основе битовых карт для доступа ко всем строкам по Англии, придется (10 раз) последовательно прочитать каждый блок таблицы. Вне всякого сомнения, эффективнее будет выполнить полный просмотр таблицы, а не использовать такой индекс.

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


Конечно, описательные выражения типа "небольшой", "маленький", "близкий к нулю" требуют определенного уточнения. Например, близко ли значение 10000 к нулю? Если сравнивать с десятью миллиардами, то да!

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

Рассмотрим следующий пример, основанный на данных по примерно 64-миллионному населению Великобритании.

  • 50 миллионов имеет карие глаза


  • 35 миллионов - женщины


  • 17 миллионов - темноволосые


  • 1,8 миллиона живет в районе Бирмингема


  • 1,2 миллиона имеет возраст 25 лет


  • 750000 работает в Лондоне






  • Каждому критерию отдельно соответствует очень много людей, но сколько кареглазых темноволосых женщин в возрасте 25 лет живет в Бирмингеме и работает в Лондоне? Где-то пару десятков.

    create table junk as select rownum id from all_objects where rownum

    Рисунок 4. Моделируем население Великобритании.

    Отдельный индекс (будь-то на основе B*-дерева или битовых карт) по любому из этих столбцов будет абсолютно бесполезен для выполнения такого запроса к таким данным в СУБД Oracle.

    Многостолбцовый индекс на основе B*-дерева по соответствующим шести столбцам может существенно помочь, пока нас не заинтересуют мужчины ростом 180 см. с бородой вместо темноволосых и кареглазых женщин.

    Можете поэкспериментировать (см. рис. 4), но понадобиться около 2,0 Гбайт места на диске и пару часов работы процессора с тактовой частотой порядка 500 МГц.

    Из-за нехватки места я построил модель поменьше, эмулирующую население порядка 36 миллионов. Время построения и размеры объектов для компьютера с тактовой частотой процессора 600 МГц, ОС Win2000 и сервером Oracle версии 9.2.0.1 представлены в следующей таблице.



    Объект


    Размер (Мбайт)


    Время построения (мин:сек)
    T1 845 16:12
    I1 (sex) 11 1:39
    I2 (eyes) 16 1:43
    I2 (hair) 37 2:17
    I4 (town) 40 2:25
    I5 (age)

    42 2:28
    I6 (work)

    45 2:42
    <


    Обратите, в частности, внимание на суммарный объем индексов, - 191 Мбайт. Всего лишь один многостолбцовый индекс по тем же шести столбцам (даже с максимальным сжатием) займет минимум 430 Мбайт, а сколько процессорного времени потребуется на его построение, - я вообще не знаю, да и немногие системы позволят построить этот индекс в памяти, поскольку для этого требуется установить параметру sort_area_size значение около 900 Мбайт.

    Итак, что же могут дать все эти битовые индексы? Рассмотрим запрос:

    select count(facts) from t1 where eyes = 1 and sex = 1 and hair = 1 and town = 15 and age = 25 and work = 40;

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

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

    При наличии заданных ранее битовых индексов запрос выполнялся пять секунд. Большая часть этого времени ушла на сканирования диапазонов индексов, требующие физического считывания блоков индекса в память. Фактический план выполнения представлен на рис. 5.

    SORT (AGGREGATE) TABLE ACCESS (BY INDEX ROWID) OF T1 BITMAP CONVERSION (TO ROWIDS) BITMAP AND BITMAP INDEX (SINGLE VALUE) OF I6 BITMAP INDEX (SINGLE VALUE) OF I5 BITMAP INDEX (SINGLE VALUE) OF I4

    Рисунок 5. План выполнения.

    В этом плане выполнения запроса следует отметить два интересных момента. Во-первых, сервер Oracle проигнорировал три "худших" (т.е., наименее избирательных) индекса. Во-вторых, хотя время выполнения - заметное, но размеры индексов настолько малы, что имеет смысл подумать об их размещении в достаточно большом KEEP-пуле, buffer_pool_keep (в Oracle 9 его размер задается параметром db_keep_cache_size), чтобы избежать физических чтений. Этот вариант вряд ли подходит для нескольких многостолбцовых индексов на основе B*-дерева, поддерживающих такие же запросы.

    Давайте подумаем о проигнорированных индексах, - в плане может использоваться практически любое количество индексов на основе битовых карт. Я видел случаи, когда сервер Oracle использовал более пяти таких индексов (это предел для способа доступа and_equal при использовании одностолбцовых индексов на основе B*-дерева).

    Три оставшихся индекса были проигнорированы не из-за какого-то искусственного ограничения. Стоимостной оптимизатор сравнил стоимость чтения каждого дополнительного индекса с достигаемой дополнительной точностью, и не выбрал их. Так что, индексы на основе битовых карт по классическому столбцу (пол) обычно игнорируются, несмотря на противоположные утверждения. (Удалите конструкцию work = 40 из запроса и убедитесь, что индекс по столбцу sex в этом случае используется).

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


    Содержание раздела