sql

Вчера под ночь боролся с «Постгресом» (это такая СУБД), в итоге поборол, но не так, как хотелось бы. Бизнес-задачу мне не хотелось бы сейчас рассматривать, поэтому для иллюстрации проблемы создам тестовую таблицу безо всякой смысловой нагрузки:

SELECT id, CASE WHEN RANDOM()>.5 THEN value END AS value
INTO test
FROM generate_series(1, 1000000) WITH ORDINALITY AS test(id, value)

В тестовой таблице два поля — идентификатор (id) и значение (value), примерно половина значений в поле value — NULL. И теперь нам надо создать индекс для запросов, которые выглядит примерно так:

SELECT id FROM test WHERE value IS NULL ORDER BY id;
SELECT id FROM test WHERE value IS NOT NULL ORDER BY id;

План для них выглядит одинаково печально, что логично — на таблице ни одного индекса:

Sort  (cost=61739.93..62977.68 rows=495100 width=4) (actual time=47289.775..47761.235 rows=498778 loops=1)
   Sort Key: id
   Sort Method: external merge  Disk: 6848kB
   ->  Seq Scan on test  (cost=0.00..14910.00 rows=495100 width=4) (actual time=12.039..40854.731 rows=498778 loops=1)
         Filter: (value IS NULL)
         Rows Removed by Filter: 501222
 Planning Time: 0.174 ms
 Execution Time: 48134.553 ms

Чтобы сэкономить место, мне очень хотелось сделать индекс функциональным:

CREATE UNIQUE INDEX ON test((value IS NULL), id);

Таким образом вместо целого поля будет использован логический тип всего с двумя значениями.

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

Первый запрос ожидаемо улучшился:

Index Scan using test_expr_id_idx on test  (cost=0.42..33882.43 rows=495100 width=4) (actual time=0.056..519.584 rows=498778 loops=1)
   Index Cond: ((value IS NULL) = true)
 Planning Time: 0.182 ms
 Execution Time: 894.551 ms

А второй — нет:

Sort  (cost=62738.26..64000.51 rows=504900 width=4) (actual time=1046.582..1471.180 rows=501222 loops=1)
   Sort Key: id
   Sort Method: external merge  Disk: 6880kB
   ->  Seq Scan on test  (cost=0.00..14910.00 rows=504900 width=4) (actual time=0.033..522.071 rows=501222 loops=1)
         Filter: (value IS NOT NULL)
         Rows Removed by Filter: 498778
 Planning Time: 0.136 ms
 Execution Time: 1841.282 ms

Несмотря на то, что в индексе содержится информация, достаточная для выполнения этого запроса, в данном случае «Постгрес» не понимает, что VALUE IS NOT NULL эквивалентно (VALUE IS NULL) = false.

Причём, если попробовать переписать запрос, чтобы условие выборки выглядело как (VALUE IS NULL) = false, то тут оптимизатор не оплошает — перепишет за нас условие в виде VALUE IS NOT NULL и опять не будет узнавать его в индексе.

Я вижу несколько путей решения этой проблемы, все с недостатками.

Во-первых, можно «замаскировать» конструкцию …IS [NOT] NULL, чтобы оптимизатор перестал его нормализировать:

CREATE UNIQUE INDEX ON test((CASE WHEN value IS NULL THEN TRUE ELSE FALSE END), id);

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

Во-вторых, можно создать два индекса вместо одного:

CREATE UNIQUE INDEX ON test((value IS NULL), id);
CREATE UNIQUE INDEX ON test((value IS NOT NULL), id);

Недостаток: у нас два индекса — при вставке или обновлении будем писать в два места, раздуваться (bloat) у нас будут тоже два индекса вместо одного.

В-третьих, можно не выпендриваться, а создать обычный индекс:

CREATE UNIQUE INDEX ON test(value, id);

Фатальный недостаток: индекс, по сути, бесполезен — он содержит всю таблицу целиком, «Постгрес» скорее всего выберет последовательное сканирование таблицы, а индекс использовать не будет.

И, наконец, вариант, который мне нравится в этой ситуации больше всего — частичные индексы:

CREATE UNIQUE INDEX ON test(id) WHERE value IS NULL;
CREATE UNIQUE INDEX ON test(id) WHERE value IS NOT NULL;

Да, у нас опять два индекса, но они довольно компактны по размеру: в каждом примерно половина данных, кроме того, в нём вообще только одно поле — второго нет вовсе, его заменяет условие индекса.

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

Я тут подумал, что было бы очень круто как помечать запросы флагом, который бы говорил СУБД «если такой же запрос уже выполняется, то меня устроят его результаты, новый запускать не надо». Было бы очень полезно для запросов, в которых не нужна оперативность и которые заказываются большим числом пользователей.

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

Со стороны СУБД было бы интереснее такое увидеть.

POSTQUEL — это язык запросов, который когда-то поддерживала СУБД «Постгрес». Наверняка многие задумывались почему языков программирования так много, а языков в базах данных, кроме SQL и его диалектов, не видать; SQL оказался исключительно удачным, но у него были когда-то и соперники. «Постквел» один из них.

POSTQUEL расшифровывается как «POSTgres QUEry Language», «язык запросов Постгреса», он был разработам в 1985 году в Калифорнийском университете в Беркли под руководством Майкла Стоунбрейкера, POSTQUEL основан на языке запросов QUEL, который использовался на тот момент в БД «Ингрес».

Примеры того на что был похож POSTQUEL есть в польской Википедии:

Получить размер заработной платы сотрудника Ковальски (pracownicy — сотрудники, płace — зарплата):

retrieve (PRACOWNICY.placa) from PRACOWNICY where PRACOWNICY.nazwisko = "Kowalski"

Все сотрудники старше 40 лет (wiek — возраст, nazwisko — имя):

retrieve (P.nazwisko) from P in PRACOWNICY where P.wiek > 40

Найти все департаменты, целиком занимающие один этаж (pietro — этаж, dnazwa — сокращение от «название департамента»):

retrieve (DEPART.dnazwa)
where DEPART.pietro NOT-IN {D.pietro from D in DEPART where D.dnazwa != DEPART.dnazwa}

«Постквел» был более формализованным языком, чем Эскюэль, все команды строились по одному образцу и не допускали вариаций. Других подробностей я не нашёл, к сожалению, детального описания языка мне обнаружить пока не удалось, было бы любопытно посмотреть на него и проанализировать сильные стороны.

Добавлено позднее. Я обнаружил документацию 1992 года на «Постгрес», где довольно подробно упоминается и «Постквел» (ссылка есть в комментариях). Интересный язык-то был!

Например, оперировал он объектами, поддерживал наследование (все примеры из упомянутой документации):

create STUD_EMP (location = point) inherits (EMP)

Поддерживал массивы (индексы начинаются с единицы):

create SAL_EMP (name = char[], pay_by_quarter = int4[4])

append SAL_EMP (name = "bill", pay_by_quarter="{10000, 10000, 10000, 10000}")

retrieve (SAL_EMP.name) where SAL_EMP.pay_by_quarter[1] !=SAL_EMP.pay_by_quarter[2]

Поддерживал историю, вот, например, срез данных с первого января 1970 по наши дни:

retrieve (E.salary)
    from E in EMP["Jan 1 00:00:00 1970 GMT", "now"]
    where E.name = "Sam"

Была возможность создавать пользовательские типы (тут создаётся новый тип массива):

define type int_array
    (element = int4, internallength = variable,
    input = array_in, output = array_out)

Так же как и пользовательские функции:

define function eq_area_circle
    (language = "c", returntype = bool)
    arg is (circle, circle)
    as "/usr/postgres/tutorial/circle.o"

define function manager
    (language = "postquel", returntype = EMP)
    arg is (EMP)
    as "retrieve (E.all) from E in EMP
    where E.name = DEPT.manager
    and DEPT.name = $1.dept"

retrieve (EMP.name)
    where name(manager(EMP)) = "Joe"

Была даже перегрузка операторов!

define operator =
    (arg1 = circle, arg2 = circle,
    procedure = eq_area_circle)

И так далее.

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

SELECT id FROM (
    SELECT id, id-@prev AS diff, @prev:=id
    FROM
        (SELECT @prev:=NULL) ``,
        sourceofdata
   ORDER BY id
) `` WHERE diff>1

Внутри есть напрасный запрос «SELECT @prev:=NULL», который там только затем, чтобы решение получилось в одну строку.

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

Может кто-то придумать проще? Не важно для какой СУБД.