PostrgreSQL: ускоряемся через intarray

Лет так 6 назад, когда слоник был только в 8.0, а я плотно сидел на MySql, часто слышал призывы сменить DB. Я помню как это было болезненно начать. Но после того, как решился, ни разу не жалел и на мускул уже вряд ли вернусь. Уж очень много тут плюсов, но пост не об этом.

Пришла задача: написать магазин, большой в перспективе. А-ля Фотос, Хотлайн. Ну и стандартная задача для таких площадок — это фильтр.

Как это делаются в обычных «движках»? Верно: параметры = фильтры. Ну все понятно, что это просто, но не всегда красиво, особенно когда нужны фильтры с диапазонами (например: диагональ 10"-11"). Да и тогда приходится думать о том, что фильтры — это независимая от параметров сущность. В моей версии фильтры «вяжутся» к параметрам. Не знаю, как это сделано на том же хотлайне (есть подозрение, что там фильтры вяжутся непосредственно на товары), но такой вариант требует много человеческого внимания. Не буду вдаваться в детали архитектуры, это тема другого поста. Но рассматривать будем именно упрощенный вариант, дабы не потеряться.

Проблема в таких фильтрах — это их построение. Просчитать количество товаров при выбранных (или не выбранных ещё) фильтрах.

Итак…

Создаем таблицу для товаров:

CREATE TABLE public.products (
  id SERIAL,
  title VARCHAR NOT NULL,
  CONSTRAINT products_pkey PRIMARY KEY(id)
);

Таблицу фильтров:

CREATE TABLE public.filters (
  id SERIAL,
  title VARCHAR NOT NULL,
  CONSTRAINT filters_pkey PRIMARY KEY(id)
);

Таблицу для связей между filters и products:

CREATE TABLE public.products_ref_filters (
  id_product INTEGER NOT NULL,
  id_filter INTEGER NOT NULL,
  CONSTRAINT products_ref_filters_pkey PRIMARY KEY(id_product, id_filter),
  CONSTRAINT products_ref_filters_fk FOREIGN KEY (id_product)
    REFERENCES public.products(id)
    ON DELETE CASCADE
    ON UPDATE CASCADE,
  CONSTRAINT products_ref_filters_fk1 FOREIGN KEY (id_filter)
    REFERENCES public.filters(id)
    ON DELETE CASCADE
    ON UPDATE CASCADE
);

И получается стандартный вариант. Тривиально.

Дальше…

В таблицу товаров добавляем поле filters:

ALTER TABLE public.products
  ADD COLUMN filters INTEGER[] DEFAULT ARRAY[]::integer[] NOT NULL;

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

CREATE OR REPLACE FUNCTION public.products_ref_filters__insert_tr ()
RETURNS trigger AS'
BEGIN
  UPDATE products 
  SET filters = filters + NEW.id_filter --push element onto array
  WHERE id = NEW.id_product;

  RETURN NEW;
END;
'LANGUAGE 'plpgsql';

CREATE TRIGGER products_ref_filters__insert_tr
  AFTER INSERT 
  ON public.products_ref_filters FOR EACH ROW 
  EXECUTE PROCEDURE public.products_ref_filters__insert_tr();

Удаление:

CREATE OR REPLACE FUNCTION public.products_ref_filters__delete_tr ()
RETURNS trigger AS'
BEGIN
  UPDATE products 
  SET filters = filters - OLD.id_filter --remove entries matching right argument from array
  WHERE id = OLD.id_product;

  RETURN OLD;
END;
'LANGUAGE 'plpgsql';

Обновление:

CREATE OR REPLACE FUNCTION public.products_ref_filters__update_tr ()
RETURNS trigger AS'
BEGIN
  UPDATE products 
  SET filters = filters - OLD.id_filter
  WHERE id = OLD.id_product;
  
  UPDATE products 
  SET filters = filters + NEW.id_filter
  WHERE id = NEW.id_product;
  
  RETURN NEW;
END;
'LANGUAGE 'plpgsql';

CREATE TRIGGER products_ref_filters__update_tr
  AFTER UPDATE 
  ON public.products_ref_filters FOR EACH ROW 
  EXECUTE PROCEDURE public.products_ref_filters__update_tr();

Очистка:

CREATE OR REPLACE FUNCTION public.products_ref_filters__truncate_tr ()
RETURNS trigger AS'
BEGIN
  UPDATE products SET filters = ARRAY[]::INTEGER[];

  RETURN NULL;
END;
'LANGUAGE 'plpgsql';


CREATE TRIGGER products_ref_filters__truncate_tr
  AFTER TRUNCATE 
  ON public.products_ref_filters FOR EACH STATEMENT 
  EXECUTE PROCEDURE public.products_ref_filters__truncate_tr();

Теперь, при вставке, обновлении, удалении, данных из таблицы связей будет записываться массив фильтров в таблицу товаров. И мы избавились от JOIN. Теперь не нужно клеить таблицы в запросе. Это дает много плюсов, легче строить запросы, они быстрее, меньше памяти и т.д. Но статья ведь о intarray? Да.

Устанавливаем расширение:

CREATE EXTENSION intarray;

После исполнения этой команды в базе появятся функции, индексы, операторы для работы с массивами типа INTEGER. Теперь работать будет намного быстрее и удобнее.

Наполняем нашу БД. Фильтров 10 000. Товаров 100 000. Каждому товару по 10 фильтров. Итого: промежуточная таблица 1 000 000 строк. Этот блок запросов у меня исполнялся 8 мин. Так что дождитесь.

INSERT INTO filters (title) SELECT 'filter_' || num FROM generate_series(1, 10000) as num;

INSERT INTO products (title) SELECT 'product_' || num FROM generate_series(1, 100000) as num;

DO $$
DECLARE
    idp INTEGER;
BEGIN
   FOR idp IN SELECT id FROM products
   LOOP
	INSERT INTO products_ref_filters 
        SELECT idp, f.id FROM filters f ORDER BY random() LIMIT 10;
   END LOOP;
END$$;

Создаем индекс на массив чисел:

CREATE INDEX products_idx ON public.products
  USING gin (filters public.gin__int_ops);

Итого, наша БД заполнена. Давайте посмотрим, что теперь с этим делать. Давайте найдем самые популярные фильтры и запомним их.

SELECT id_filter
FROM products_ref_filters 
GROUP BY id_filter 
ORDER BY count(*) DESC
LIMIT 10

Мой результат такой: 7267, 4889, 6364, 5376, 3556, 7292, 11188, 2643, 9005, 10235.

Найдем товары с определенным фильтром, пусть будет 7267:

-- обычный JOIN
SELECT t1.* FROM products t1, products_ref_filters t2
WHERE t1.id = t2.id_product
  AND t2.id_filter = 7267
-- 140 rows returned (execution time: 125 ms; total time: 141 ms)

-- SUB SELECT
SELECT * FROM products 
WHERE id IN ( SELECT id_product FROM products_ref_filters WHERE id_filter = 7267 ) 
-- 140 rows returned (execution time: 125 ms; total time: 141 ms)

-- поиск по массиву 
SELECT * FROM products WHERE filters @> ARRAY[7267]
-- 140 rows returned (execution time: 0 ms; total time: 0 ms)

Один из фильтров

-- JOIN
SELECT DISTINCT t1.* FROM products t1, products_ref_filters t2
WHERE t1.id = t2.id_product
  AND t2.id_filter IN (7267,4889,6364,5376,3556,7292,11188,2643,9005,10235)
-- 1347 rows returned (execution time: 297 ms; total time: 297 ms)

-- SUB SELECT
SELECT * FROM products 
WHERE id IN ( SELECT id_product FROM products_ref_filters WHERE id_filter IN (7267,4889,6364,5376,3556,7292,11188,2643,9005,10235) ) 
-- 1347 rows returned (execution time: 234 ms; total time: 250 ms)

-- INTARRAY
SELECT * FROM products WHERE filters && ARRAY[7267,4889,6364,5376,3556,7292,11188,2643,9005,10235]
-- 1347 rows returned (execution time: 16 ms; total time: 16 ms)

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

-- JOIN
-- ЛЕНЬ, но тут отрыв ещё больше будет ;)

-- Товары содержащие оба фильтра
SELECT * FROM products WHERE filters @> ARRAY[9844,9957];
-- 1 rows returned (execution time: 0 ms; total time: 16 ms)

Оф. дока тут.

Обратите внимание на операторы, это просто сказка! Где-то читал, что даже есть патч, установив который, можно внешние ключи строить на массив, и база сама будет следить за целостностью. Еще где-то читал, что разработчики даже планируют это сделать без всяких патчей. Да, здорово. В свое время, когда я нашел (для себя) это решение, радости было…

Посмотрев, что есть небольшой интерес к теме.
Решил немного добавить немного тестов на объемах.
Попробуем на 10 000 000 товарах.
Немного изменим запрос, по заполнению псевдотоваров.

-- фильтров как и было 1000
INSERT INTO filters (title) SELECT 'filter_' || num FROM generate_series(1, 10000) as num;
--Товаров 10 000 000
INSERT INTO products (title) SELECT 'product_' || num FROM generate_series(1, 10000000) as num;

-- т.к. целостность нас в тестах не интересует, заполним только ID-шки
DO $$
DECLARE
    idp INTEGER;
BEGIN
   FOR idp IN SELECT id FROM products
   LOOP
        UPDATE products 
        SET filters = (SELECT array_agg(id) FROM (SELECT id FROM filters OFFSET random()*1000 LIMIT 10) as foo)
        WHERE id = idp;
   END LOOP;
END$$;
-- этот запрос отрабатывает ~20мин

Размер БД ~2.9Гб

Индекс BTREE:

CREATE INDEX products_idx ON public.products USING btree (filters);
-- execution time: 00:02:36
-- DB size ~ 3.8Gb

SELECT * FROM products WHERE filters @> '{842}'::INTEGER[];
-- Seq Scan on public.products  (cost=0.00..357908.00 rows=10000 width=80) ...
-- 99798 rows returned (execution time: 5,594 sec; total time: 5,594 sec)

SELECT * FROM products WHERE filters = '{842,843,844,845,846,847,848,849,850,851}'::INTEGER[];
-- Bitmap Heap Scan on public.products  (cost=487.94..32940.13 rows=9726 width=80)
-- 9940 rows returned (execution time: 46 ms; total time: 62 ms)

SELECT * FROM products WHERE filters && '{842,843,844,845,846,847,848,849,850,851}'::INTEGER[]
-- Seq Scan on public.products  (cost=0.00..357908.00 rows=10000 width=80)
-- 189853 rows returned (execution time: 6,281 sec; total time: 6,296 sec)

Индекс GIST:

CREATE INDEX products_idx ON public.products USING gist (filters public.gist__int_ops);
-- execution time: 00:26:55;
-- DB size ~ 4.5Gb

SELECT * FROM products WHERE filters @> '{842}'::INTEGER[];
-- Bitmap Heap Scan on public.products  (cost=833.92..34097.44 rows=10000 width=80)
-- 99798 rows returned (execution time: 2,234 sec; total time: 2,234 sec)

SELECT * FROM products WHERE filters = '{842,843,844,845,846,847,848,849,850,851}'::INTEGER[];
-- Bitmap Heap Scan on public.products  (cost=811.79..33263.99 rows=9726 width=80)
-- 9940 rows returned (execution time: 234 ms; total time: 234 ms)

SELECT * FROM products WHERE filters && '{842,843,844,845,846,847,848,849,850,851}'::INTEGER[];
-- Bitmap Heap Scan on public.products  (cost=833.92..34097.44 rows=10000 width=80)
-- 189853 rows returned (execution time: 5,234 sec; total time: 5,234 sec)

Индекс GIN:

CREATE INDEX products_idx ON public.products USING gin (filters public.gin__int_ops);
-- execution time: 56,344 sec;

SELECT * FROM products WHERE filters @> '{842}'::INTEGER[];
-- Bitmap Heap Scan on public.products  (cost=97.50..33361.02 rows=10000 width=80)
-- 99798 rows returned (execution time: 2,204 sec; total time: 2,219 sec)

SELECT * FROM products WHERE filters = '{842,843,844,845,846,847,848,849,850,851}'::INTEGER[];
-- Bitmap Heap Scan on public.products  (cost=211.37..32663.57 rows=9726 width=80)
-- 9940 rows returned (execution time: 297 ms; total time: 312 ms)

SELECT * FROM products WHERE filters && '{842,843,844,845,846,847,848,849,850,851}'::INTEGER[];
-- Bitmap Heap Scan on public.products  (cost=213.50..33477.02 rows=10000 width=80)
-- 189853 rows returned (execution time: 4,500 sec; total time: 4,515 sec)

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