GoSuda

Яркий битмап

By snowmerak
views ...

Что такое Bitmap?

Здесь Bitmap является одним из видов индекса. Если вы пришли сюда, думая о графике, вы можете нажать кнопку "Назад".

Основные понятия

Bitmap является формой технологии индексирования базы данных. Он представляет значения определённой колонки в виде битового массива или элемента/формы вектора, где каждый бит указывает на наличие или отсутствие определённого значения в соответствующей колонке. Таким образом, в самой базовой форме каждому row присваивается битовый индекс, и наличие или отсутствие представляется как 0 или 1.

Например, предположим, что у нас есть таблица с колонкой "пол". Допустим, в этой таблице 5 row, и значения колонки "пол" следующие:

  1. Мужской
  2. Женский
  3. Мужской
  4. Женский
  5. Другой

В этом случае Bitmap индекс для колонки "пол" может быть представлен следующим образом:

  • Мужской: 10100
  • Женский: 01010
  • Другой: 00001

Для чего это на самом деле используется?

Таким образом, все, вероятно, подумают, что это не просто для представления чего-либо. Чтобы правильно использовать Bitmap индекс, рассмотрим следующий случай.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Предположим, что в этой таблице 1 000 000 row. И предположим, что выполняется следующий запрос.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Этот запрос находит row, где колонки active и sex обе равны TRUE. Тогда для быстрого поиска row, удовлетворяющих условию, что обе колонки равны TRUE, можно использовать операцию битового И.

  • Предположим, что Bitmap индекс для колонки active предварительно проиндексирован как 1100110011... (битовый массив из 1 000 000 бит), и
  • Предположим, что Bitmap индекс для колонки sex предварительно проиндексирован как 1010101010... (битовый массив из 1 000 000 бит).

Тогда, выполнив операцию битового И над двумя Bitmap индексами, можно быстро найти row, где обе колонки равны TRUE. Поскольку это простая битовая операция, результаты могут быть получены намного быстрее, чем при сканировании других индексов.

Компромиссы

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

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

Если использовать Bitmap индекс для колонки с высокой кардинальностью, необходимо создать отдельный Bitmap для каждого уникального значения, что может потребовать большого объёма памяти для хранения. Например, если в колонке 1 000 000 уникальных значений, то потребуется создать 1 000 000 Bitmap, что может быть крайне неэффективно.

Поэтому мы

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

Основные понятия Roaring Bitmap

Двухэтапное индексирование

Для хранения одного целого числа Roaring Bitmap сначала проходит следующие 2 этапа. Это называется двухэтапным индексированием, но вы можете просто представить это как двумерный массив.

  • Извлечение старших 16 бит: Извлекаются старшие 16 бит целого числа и используются в качестве индекса. Это становится индексом внешнего массива в двумерном массиве общей длиной 65536. Этот массив хранит адреса контейнеров, о которых будет сказано далее.
  • Извлечение младших 16 бит: Извлекаются младшие 16 бит целого числа и используются в качестве позиции внутри контейнера.

Контейнер

Этот контейнер, как было упомянуто ранее, соответствует внутреннему массиву в двумерном массиве. Однако, в отличие от старших 16 бит, внутренняя структура этого контейнера изменяется в зависимости от объёма внутренних данных. Roaring Bitmap поддерживает следующие 3 типа контейнеров.

  • Array Container: Этот контейнер используется, когда внутри хранится мало данных. В частности, он используется для хранения до 4096 элементов. Этот контейнер реализован как просто отсортированный массив целых чисел. Элементы можно найти с помощью бинарного поиска.
  • Bitmap Container: Этот контейнер используется, когда внутри хранится много данных. В частности, он используется для хранения более 4096 элементов. Этот контейнер реализован как Bitmap из 65536 бит (8192 байта). Каждый бит указывает на наличие или отсутствие целого числа в соответствующей позиции.
  • Run Container: Этот контейнер используется для хранения последовательных диапазонов целых чисел. Например, он эффективен при хранении последовательных целых чисел, таких как 1, 2, 3, 4, 5. Этот контейнер реализован как список пар (начальное значение, длина). Если есть все значения? Это означает, что есть все от начала до конца, поэтому можно просто сохранить одну пару (0, 65536).

Такой подход позволяет Roaring Bitmap очень эффективно использовать память и обеспечивать оптимальную производительность для различных плотностей данных.

Функциональность Roaring Bitmap

Базовая функциональность

Roaring Bitmap предоставляет следующие основные функции:

  • Вставка: Добавляет новое целое число в Bitmap. В процессе этого может быть выбран подходящий контейнер или, при необходимости, контейнер может быть преобразован.
  • Удаление: Удаляет существующее целое число из Bitmap. В процессе этого также выполняется соответствующая обработка в зависимости от состояния контейнера.
  • Поиск: Проверяет наличие определённого целого числа в Bitmap. Эта операция выполняется очень быстро.

Операции с множествами

Roaring Bitmap также поддерживает следующие операции с множествами:

  • Объединение (Union): Создает новый Bitmap, содержащий все элементы из двух Bitmap.
  • Пересечение (Intersection): Создает новый Bitmap, содержащий только элементы, присутствующие в обоих Bitmap.
  • Симметрическая разность (Symmetric Difference): Создает новый Bitmap, содержащий элементы, присутствующие только в одном из двух Bitmap.

Эти операции оптимизированы в зависимости от типа контейнера Bitmap и выполняются очень быстро.

В языке Go

В языке Go вы можете легко использовать Roaring Bitmap, используя пакет github.com/RoaringBitmap/roaring. Этот пакет предоставляет все функции Roaring Bitmap и оптимизирован для характеристик языка Go.

Установка

1go get github.com/RoaringBitmap/roaring/v2

Пример использования

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Инициализация значениями 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Инициализация значениями 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Добавление 5
14	b2.Add(10) // Добавление 10
15
16	b2.Remove(12) // Удаление 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Поскольку операции над bitmap изменяют оригинал, используйте клон
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

Основные функции, не показанные в приведенном примере кода:

  • Contains(x uint32) bool: Проверяет, содержит ли Bitmap определённое значение.
  • GetCardinality() uint64: Возвращает количество элементов в Bitmap.
  • Rank(x uint32) uint64: Возвращает количество элементов, меньших или равных определённому значению.
  • ToBytes() ([]byte, error): Сериализует Bitmap в срез байтов.
  • FromBytes(data []byte) error: Восстанавливает Bitmap из среза байтов.
  • Clone() *Bitmap: Создает клон Bitmap.
  • Clear(): Инициализирует Bitmap.
  • NextValue(x uint32) int64: Возвращает следующий элемент, больший или равный x.
  • PreviousValue(x uint32) int64: Возвращает следующий элемент, меньший или равный x.
  • Maximum() uint32: Возвращает наибольший элемент в Bitmap.
  • Minimum() uint32: Возвращает наименьший элемент в Bitmap.

Эти функции доступны. Более подробную информацию см. в официальной документации.

Кстати, пакет roaring содержит пакеты, поддерживающие не только uint32, но и uint64. Поскольку они предоставляют почти идентичный интерфейс, их можно использовать взаимозаменяемо.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Инициализация значениями 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Инициализация значениями 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Добавление 5
14	b2.Add(10) // Добавление 10
15
16	b2.Remove(12) // Удаление 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Поскольку операции над bitmap изменяют оригинал, используйте клон
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Заключение

Roaring Bitmap — это мощный инструмент, позволяющий эффективно хранить и манипулировать наборами целых чисел высокой кардинальности. В языке Go, используя пакет github.com/RoaringBitmap/roaring, вы можете легко использовать все возможности Roaring Bitmap. Этот пакет максимально увеличивает использование памяти и производительность благодаря различным типам контейнеров и оптимизированным операциям. Roaring Bitmap может быть использован для реализации эффективной обработки данных в различных областях, таких как индексирование баз данных, анализ логов и статистические вычисления.

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

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