6 мая 2010 в 16:56

Обход ограничений DISTINCT ON в PostgreSQL.

Ожидает приглашения

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

Квалифицированный веб-программист сразу же скажет, что такая страница — отличный кандидат в кэш. Однако могут быть дополнительные условия, которые сделают мысль о кэше совсем не такой привлекательной, например, если на эту выборку должны быть наложены дополнительные условия, индивидуальные для каждого пользователя: списки друзей, подписка на группы или категории, права доступа и т.п. И даже если кэширование возможно, выборка для кэша, длящаяся несколько секунд, крайне неприятна.

Поэтому рассмотрю оптимизацию «честной» выборки на уровне SQL запросов.

Беглое знакомство с возможностями PostgreSQL должно подкинуть мысль об использовании конструкции DISTINCT ON:
SELECT DISTINCT ON (user_id) * FROM images ORDER BY post_date DESC;

К сожалению, текущая реализация DISTINCT ON в PostgreSQL использует сортировку и требует, чтобы первыми в ORDER BY стояли те же поля, что и в DISTINCT ON:
ERROR: SELECT DISTINCT ON expressions must match initial ORDER BY expressions

В результате для получения такой выборки «в лоб» необходим подзапрос:

SELECT * FROM (SELECT DISTINCT ON (user_id) * FROM images ORDER BY user_id, post_date) AS images ORDER BY post_date DESC LIMIT 5;

К сожалению, переместить в этой выборке LIMIT внутрь подзапроса нельзя, поэтому внутренний SELECT сделает full table scan с сортировкой, а потом внешний SELECT сделает свою сортировку с наложением LIMIT. Уже при нескольких десятках тысяч объектов в таблице такой запрос начинает существенно раздражать.

Можно попытаться переписать этот запрос с использованием GROUP BY, но избежать полного перебора строк таблицы средствами SQL мне не удалось.

Что делать?

В идеале — надо копнуть код PostgreSQL, снять ограничение на список DISTINCT ON, а потом научить оптимизатор запросов делать DISTINCT ON выборкой по индексу без сортировки всей таблицы.

А до тех пор, пока энтузиаста не нашлось, можно применить PL/pgSQL. Алгоритм простой: для каждой строки из таблицы, отсортированной по «полю сортировки», выдаём её на выход, если её «категория» ещё не встречалась, а идентификаторы «категорий» собираем в массив.

BEGIN;

CREATE TABLE t (
    id SERIAL PRIMARY KEY,
    cat INTEGER NOT NULL,
    sort INTEGER NOT NULL
    );

-- Здесь умышленно не использован random() для поля "cat", чтобы получить менее удачную для алгоритма выборку.
INSERT INTO t (cat,sort) SELECT (v/100)::INTEGER, v::INTEGER FROM generate_series(100000, 1, -1) AS g(v);
CREATE INDEX t_cat_idx ON t(cat);
CREATE INDEX t_sort_idx ON t(sort);
ANALYZE t;

-- Этот запрос не поддерживается.
-- SELECT DISTINCT ON (cat) * FROM t ORDER BY sort LIMIT 5;
--      ERROR:  SELECT DISTINCT ON expressions must match initial ORDER BY expressions

-- запрос "в лоб"
SELECT * FROM (SELECT DISTINCT ON (cat) * FROM t ORDER BY cat, sort) AS t ORDER BY sort LIMIT 5;
EXPLAIN ANALYZE
    SELECT * FROM (SELECT DISTINCT ON (cat) * FROM t ORDER BY cat, sort) AS t ORDER BY sort LIMIT 5;

-- специализированная функция
CREATE FUNCTION t_distinct_cat_sorted_limited(_limit INTEGER)
    RETURNS SETOF t LANGUAGE 'plpgsql' STABLE STRICT COST 4000 ROWS 10 AS
$$
    DECLARE
        tr t%ROWTYPE;
        i INTEGER;
        cat_got INTEGER[];
    BEGIN
        i := 0;
        cat_got := ARRAY[]::INTEGER[];

        IF _limit < 1
        THEN
            RETURN;
        END IF;

        -- Этот запрос не выбирает всю таблицу, а обращается к ней построчно.
        FOR tr IN SELECT * FROM t ORDER BY sort
        LOOP
            -- Если "cat" уже попадался, пропустить строку.
            -- if the same "cat" was found already, skip
            IF NOT tr.cat = ANY(cat_got)
            THEN
                -- Найдено новое "cat".
                -- found new "cat"
                RETURN NEXT tr;

                i := i + 1;

                IF i >= _limit
                THEN
                    EXIT;
                END IF;

                cat_got[i] := tr.cat;
            END IF;
        END LOOP;

        RETURN;
    END;
$$;

-- Нет гарантий, что результат функции будет выдан в том порядке, в котором вызывались RETURN NEXT, особенно при дальнейшем комбинировании запросов.
SELECT * FROM t_distinct_cat_sorted_limited(5) ORDER BY sort;

EXPLAIN ANALYZE
    SELECT * FROM t_distinct_cat_sorted_limited(5) ORDER BY sort;

-- Для сравнения - обычная выборка всей таблицы.
EXPLAIN ANALYZE
    SELECT * FROM t;
EXPLAIN ANALYZE
    SELECT * FROM t ORDER BY sort;

ROLLBACK;

Что мы имеем на выходе.
Запрос «в лоб»:

   id   | cat | sort
--------+-----+------
 100000 |   0 |    1
  99901 |   1 |  100
  99801 |   2 |  200
  99701 |   3 |  300
  99601 |   4 |  400
                                                             QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=11862.43..11862.44 rows=5 width=12) (actual time=10595.375..10595.453 rows=5 loops=1)
   ->  Sort  (cost=11862.43..11864.93 rows=1000 width=12) (actual time=10595.360..10595.383 rows=5 loops=1)
         Sort Key: public.t.sort
         Sort Method:  top-N heapsort  Memory: 17kB
         ->  Unique  (cost=11335.82..11835.82 rows=1000 width=12) (actual time=5492.463..10565.894 rows=1001 loops=1)
               ->  Sort  (cost=11335.82..11585.82 rows=100000 width=12) (actual time=5492.445..8088.609 rows=100000 loops=1)
                     Sort Key: public.t.cat, public.t.sort
                     Sort Method:  external merge  Disk: 2144kB
                     ->  Seq Scan on t  (cost=0.00..1491.00 rows=100000 width=12) (actual time=0.019..2406.391 rows=100000 loops=1)

Total runtime: 10600.052 ms

Теперь функция:
Total runtime: 1.594 ms
Неплохое ускорение!

И для сравнения, полная выборка таблицы без сортировок:

 Seq Scan on t (cost=0.00..1491.00 rows=100000 width=12) (actual time=0.021..2357.040 rows=100000 loops=1)

Total runtime: 4680.567 ms

Или с сортировкой:

 Index Scan using t_sort_idx on t (cost=0.00..2878.26 rows=100000 width=12) (actual time=0.000..2635.212 rows=100000 loops=1)

Total runtime: 4899.435 ms

Какие недостатки есть у описанного подхода?

К сожалению, на данный момент PostgreSQL не умеет выдавать строки из функции по одной, вместо этого он накапливает их все. Поэтому приходится задавать LIMIT в качестве параметра функции. А это означает, в свою очередь, что любые параметры, которые могут ограничить выборку, в том числе для присоединённых по JOIN таблиц, также надо вносить в функцию. То есть придётся либо дописывать функцию для каждого параметра, либо писать универсальную функцию с параметром «текст запроса».

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

Теги:

Хабы:

Чулан