Используйте GIN для индексации строк битов

Я пытаюсь расширить PostgreSQL для индексации строк битов до 1 000 битов. (Эти строки битов создаются квантованием высоко-размерных векторов, таким образом, для каждого размера до 4 битов присвоены). Вставки являются довольно нечастыми, тогда как поиски являются главным образом используемой операцией. В поиске я хотел бы получить все строки, которые точно соответствуют строке битов.

Похоже на идеальное задание для GIN (в сочетании с моим собственным типом данных), или что Вы думаете?

6
08.01.2020, 00:25
1 ответ

В поиске я хотел бы получить все строки, которые точно соответствуют строке битов.

Используйте индекс B-дерева, тип по умолчанию. Я не вижу случай для индекса GIN здесь.

Результат на 1 000 битов максимум в 133 байтах (или немного больше) размер ресурса хранения на диске для a bit varying ввести.

SELECT pg_column_size(repeat('1', 1000)::varbit)  -- 133

Не то, чтобы очень. Простой индекс B-дерева должен сделать. Но возможно столбец является достаточно большим, что следующие приемы улучшают производительность.

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

Пример

Таблица Given:

CREATE TABLE tbl(id serial PRIMARY KEY, b_col varbit);

Если первых 10 битов достаточно для сужения поиска к нескольким хитам, Вы могли бы создать индекс по выражению b_col::bit(10). Кастинг к bin(n) усекает bitstring к n укусил.

CREATE INDEX tbl_b_col10_idx ON tbl (b_col::bit(10))

Затем вместо запроса

SELECT * FROM tbl WHERE b_col = '1111011110111101'::varbit; -- 16 bit

Вы использовали бы:

SELECT *
FROM   tbl
WHERE  b_col::bit(10) = '1111011110111101'::bit(10) -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- filter to exact match

Знайте, что более короткие значения дополнены 0направо (младшие значащие биты), когда брошено к bit(n).

В приложении реального мира это начинает иметь смысл с несколькими 100 с битов. Тест для поворотного момента.

Оптимизируйте далее

Так как большинство установок работает с a MAXALIGN из 8 байтов (ОС на 64 бита) (больше деталей здесь), Ваш индексный размер является тем же для любых данных не чрезмерные 8 байтов. Эффективно, на строку:

 4 bytes item pointer
 8 bytes for the index tuple header (or 23 + 1 byte for heap tuples)
 ? actual space for data
 ? padding to the nearest multiple of 8 bytes

Плюс некоторые незначительные издержки на страницу и индекс / таблица. Детали в руководстве или в этом связанном ответе на ТАК.

Поэтому необходимо смочь далее оптимизировать вышеупомянутый подход. Возьмите первые 64 бита (или в последний раз или независимо от того, что является самым отличительным и работает на Вас), бросьте его к bigint и создайте индекс по этому выражению.

CREATE INDEX tbl_b_col64_idx ON tbl (b_col::bit(64)::bigint)

Я бросил дважды (b_col::bit(64)::bigint) поскольку нет никакого броска, определенного между varbit и bigint. Детали в этом связанном ответе на ТАК:

Эффективно, это - просто очень быстрая и простая хеш-функция, где значение хэш-функции также позволяет искать диапазоны значений. В зависимости от строгих требований Вы могли пойти один шаг вперед и использовать любого IMMUTABLE хеш-функция - как md5(). Детали в ответе, связанном выше.

Запрос для соглашений с этим:

SELECT *
FROM   tbl
WHERE  b_col::bit(64)::bigint = '1111011110111101'::bit(64)::bigint -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- narrow down to exact match

Получающийся индекс должен быть столь же большим как тот в первом примере, но запросы должны быть значительно быстрее по трем причинам:

  • Индекс обычно возвращает намного меньше хитов (64 бита информации по сравнению с 10 битами)

  • Пост-ГРЭС может работать с целочисленной арифметикой, которая должна быть быстрее, даже для плоскости = операция. (Не протестировал для проверки этого.)

  • Тип integer не имеет никаких издержек как varbit - 5 или 8 байтов. (В моей установке 5 байтов максимум для 960 битов, 8 байтов для больше).
    Эффективно, для хранения индекса в его минимальном размере можно только упаковать 24 бита в a varbit индекс - по сравнению с 64 битами информации для a bigint индекс.

CLUSTER

В таком случае CLUSTER должен улучшить производительность:

CLUSTER TABLE tbl USING tbl_b_col10_idx;

Это - одноразовая операция и должно быть повторено с промежутками в Ваш дизайн. Обязательно прочитайте руководство по CLUSTER если Вы хотите использовать это. Или рассмотрите альтернативу pg_repack.Подробнее:

Если первые 64 бита Ваших значений уникальны большую часть времени, CLUSTER едва поможет, так как индексное сканирование возвратит одну строку в большинстве случаев. В противном случае CLUSTER поможет много. Следовательно, эффект будет намного больше для первого примера с менее оптимизированным индексом.

15
22.02.2020, 22:32

Теги

Похожие вопросы