Как полезны растровые индексы?

Wikipedia дает этот пример

Identifier    Gender         Bitmaps
                              F    M
1           Female            1    0
2           Male              0    1
3           Male              0    1
4           Unspecified       0    0
5           Female            1    0

Но я этого не понимаю.

  • Как это индекс в первую очередь? Разве индекс не должен указывать на строки (используя rowid) с учетом ключа?
  • Какими будут типичные запросы, когда такие индексы будут полезны? Как они лучше, чем индексы B-дерева? Я знаю, что если мы будем использовать индекс B-tree на Gender здесь, мы получим много результатов, если, например, мы будем искать Gender = Male, которые необходимо отфильтровать дальше (что не очень полезно). Как Bitmap улучшает ситуацию?

Ответы

Ответ 1

Лучшее представление индекса растрового изображения, если задан образец выше:

Identifier    Gender          RowID
1             Female          R1
2             Male            R2
3             Male            R3
4             Unspecified     R4
5             Female          R5

индекс растрового изображения в столбце gender (концептуально) выглядит следующим образом:

Gender       R1    R2   R3   R4   R5
Female       1     0    0    0    1
Male         0     1    1    0    0
Unspecified  0     0    0    1    0

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

Итак, с этим индексом на месте запрос типа

SELECT * FROM table1 WHERE gender = 'Male'

база данных ищет совпадение в значениях пола в индексе, находит все rowids, где бит был установлен в 1, а затем идет и получает результаты таблицы.

Запрос типа:

SELECT * FROM table1 WHERE gender IN ('Male', 'Unspecified')

получит 1 бит для Male, 1 бит для Unspecified, выполняет поразрядное ИЛИ, а затем забирает строки, где результирующие биты равны 1.

Таким образом, преимущества использования индекса bitmap над индексом ab * tree - это хранение (с низкой мощностью, растровые индексы довольно компактные) и возможность выполнять побитовые операции до разрешения реальных строк, которые могут быть довольно быстрыми.

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

Ответ 2

Преимущество возникает при фильтрации по нескольким столбцам, тогда соответствующие индексы могут быть объединены с побитовыми операциями до фактического выбора данных. Если у вас есть пол, eye_colour, hair_colour то запрос

select * from persons where
                      gender = 'male' and 
                      (eye_colour = 'blue' or hair_colour = 'blonde')

сначала будет побито или между указателем eye_colour ['blue'] и индексом hair_colour ['blonde'] и, наконец, побитовым и между результатом и индексом gender ['male']. Эта операция выполняется очень быстро и вычислительно, и I/O.
Полученный бит-поток будет использоваться для выбора фактических строк.

Индексы растровых изображений обычно используются в "звездообразных соединениях" в приложениях хранилища данных.

Ответ 3

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

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

Просто подумайте о том, как это работает под капотом, чтобы сделать это быстрее. Бит логически является истинным или ложным. Если вы хотите сделать запрос, используя предложение WHERE, это в конечном итоге будет оценивать либо true, либо false для записей, чтобы определить, включать ли их в свои результаты.

Предисловие - остальная часть этого предназначается для неспециалистов и нетехнических

Итак, следующий вопрос - это то, что нужно для оценки истины? Даже сравнение числовых значений означает, что компьютер должен...

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

повторите, если вы используете предложение с несколькими частями, где: "this = this AND that that that"

  1. выполнять побитовые операции с результатами, сгенерированными на шаге 5
  2. Придумайте окончательное значение
  3. освободить память, выделенную в шагах 1-3.

Но с использованием побитовой логики вы просто смотрите на значения 0 (false) и 1 (true). 90% накладных расходов для сравнительной работы устраняется.