07.07.2022 11:00
Kilor 13 2600 Источник

Периодически приходится разбирать случаи внезапного промаха запроса мимо "вроде бы подходящего" индекса - а все дело оказывается в чуть-чуть не той сортировке.

Давайте посмотрим на примере:

CREATE TABLE tstord AS
SELECT
  i
, CASE
    WHEN random() < 0.99 THEN (random() * 1e6)::integer -- 1% NULLs
  END val
FROM
  generate_series(1, 1e6) i;

CREATE INDEX ON tstord(val); -- стандартный индекс

Давайте получим первую 1000 минимальных значений таблицы:

SELECT
  *
FROM
  tstord
ORDER BY
  val
LIMIT 1000;

Выдаст он ровно, что мы хотим, и достаточно быстро:

Limit (actual time=0.021..0.671 rows=1000 loops=1)
  Buffers: shared hit=1005
  ->  Index Scan using tstord_val_idx on tstord (actual time=0.020..0.606 rows=1000 loops=1)
        Buffers: shared hit=1005

Но что если мы захотим получить 1000 максимальных значений?

SELECT
  *
FROM
  tstord
ORDER BY
  val DESC -- обратная сортировка
LIMIT 1000;
Limit (actual time=0.020..0.506 rows=1000 loops=1)
  Buffers: shared hit=477
  ->  Index Scan Backward using tstord_val_idx on tstord (actual time=0.019..0.441 rows=1000 loops=1)
        Buffers: shared hit=477

Получилось даже еще быстрее, да и данных прочитать пришлось вдвое меньше! Какой PostgreSQL молодец, как он удачно использовал обратный проход по индексу Index Scan Backward!

Только вот получили мы что-то не совсем то - одни NULL:

  i    | val
995623 | [NULL]
995628 | [NULL]
995687 | [NULL]
...

Обратимся к мануалу:

... при прямом сканировании индекса по столбцу x порядок оказывается соответствующим указанию ORDER BY x (или точнее, ORDER BY x ASC NULLS LAST). Индекс также может сканироваться в обратную сторону, и тогда порядок соответствует указанию ORDER BY x DESC (или точнее, ORDER BY x DESC NULLS FIRST, так как для ORDER BY DESC подразумевается NULLS FIRST).

Оказывается, все просто - нам надо лишь сказать, чтобы NULL'ы сортировались "в конец", как и в первом запросе:

SELECT
  *
FROM
  tstord
ORDER BY
  val DESC NULLS LAST -- NULL'ы в конец
LIMIT 1000;

Теперь результат нас вполне устраивает. Или все-таки нет?

Внезапно наш запрос стал в 200 раз хуже по производительности, "слетел" с индекса и теперь вычитывает всю таблицу целиком:

Seq Scan при неудачной сортировке
Seq Scan при неудачной сортировке

Первый выход нам подсказывает сам сервис анализа планов - создать новый индекс с подходящей сортировкой:

CREATE INDEX CONCURRENTLY "~tstord-55d3ca1e"
  ON tstord(val DESC NULLS LAST);

И да, это конечно же поможет, но такой индекс...

  • потребует отдельного места для хранения на диске;

  • периодически будет вычитываться в память и вытеснять оттуда более актуальные данные;

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

А можно как-то без этого всего?

Так разве нас кто-то заставлял менять сортировку? Нет! Мы всего-то хотели исключить NULL'ы из "топа" нашей выборки - так почему бы не сделать это в явном виде?

SELECT
  *
FROM
  tstord
WHERE
  val IS NOT NULL -- просто убираем NULL'ы
ORDER BY
  val DESC -- никаких NULLS
LIMIT 1000;
Limit (actual time=0.024..0.741 rows=1000 loops=1)
  Buffers: shared hit=1007
  ->  Index Scan Backward using tstord_val_idx on tstord (actual time=0.023..0.658 rows=1000 loops=1)
        Index Cond: (val IS NOT NULL)
        Buffers: shared hit=1007

Да, такой запрос займет чуть больше времени, поскольку записи с NULL'ами все-таки надо исключить, но зато использует он ровно тот же самый индекс.

Комментарии (13)


  1. bigtrot
    07.07.2022 12:50
    #24505134

    Дополнительно, раз уж пошла речь про особенности работы с NULL, то есть видео
    https://www.youtube.com/watch?v=2qTczke77q4


  1. qw1
    07.07.2022 13:43
    #24505342

    Не имею postgre под рукой, но мне кажется будет оптимальнее

    SELECT * FROM tstord WHERE val < 1000000 ORDER BY val DESC LIMIT 1000;

    скан по индексу назад, без зачитывания и пропуска NULL-ов. Если сервер, конечно, до этого догадается.


    1. Kilor Автор
      07.07.2022 14:28
      #24505546

      Смысл примерно одинаковый, поэтому я не стал отдельно в статье приводить:

      Limit (actual time=0.013..0.775 rows=1000 loops=1)
  Buffers: shared hit=1007
  ->  Index Scan Backward using tstord_val_idx on tstord (actual time=0.011..0.709 rows=1000 loops=1)
        Index Cond: (val < 1000000)
        Buffers: shared hit=1007


      1. qw1
        07.07.2022 17:25
        #24506296

        В теории, оптимизатор должен был найти в дереве индекса значение, ближайшее в 1e6, и идти от него вперёд, т.е. по уменьшению val (сразу пропустив все null значения в начале).
        Видимо, тут null-ов слишком мало, чтобы их пропуск как-то повлиял на количество прочитанных страниц.


        1. Kilor Автор
          07.07.2022 17:38
          #24506338

          Фактически, он так и делает:

          По умолчанию элементы B-дерева хранятся в порядке возрастания, при этом значения NULL идут в конце (для упорядочивания равных записей используется табличный столбец TID).

          Ровно поэтому, ошибочно начитав кучу NULL'ов, мы увидели всего лишьshared hit=477, а, прочитав нужные -shared hit=1007.

          То есть экземпляры одного NULL-значения за счет дедупликации хранятся в индексе более эффективно, чем различные значения val.


          1. qw1
            07.07.2022 17:46
            #24506368

            есть экземпляры одного NULL-значения за счет дедупликации хранятся в индексе более эффективно, чем различные значения val
            Что-то как-то сомнительно. У каждого null-а в индексе должна быть ссылка на строку таблицы, откуда он взялся. Было бы интересно создать табличку из миллиона null-ов и табличку из миллиона единичек, построить на них индексы и посмотреть размеры этих индексов.


            1. Kilor Автор
              07.07.2022 17:55
              #24506394
              +1

              SELECT version();
-- PostgreSQL 13beta2 ... - уже есть дедупликация
CREATE TABLE tst0 AS
SELECT
  i
, 0 z
, NULL n
FROM
  generate_series(1, 1e6) i;
CREATE INDEX ON tst0(i);
CREATE INDEX ON tst0(z);
CREATE INDEX ON tst0(n);

SELECT relname, pg_relation_size(oid) FROM pg_class WHERE relname LIKE 'tst0%';
--  tst0       | 44285952
--  tst0_i_idx | 22487040
--  tst0_n_idx |  6955008
--  tst0_z_idx |  6955008


              1. qw1
                07.07.2022 18:32
                #24506516

                Из этого делаю вывод, что куча ноликов в индексе весит ровно столько же, сколько такая же куча null-ов.
                А если сделать всё то же самое, но

                SELECT
  i
, 123456789 z
, NULL n
                индекс по столбцу z будет того же размера? Если да, я поверю в дедупликацию, а не в кодирование переменной длины.


                1. Kilor Автор
                  07.07.2022 18:37
                  #24506534
                  +1

                  ALTER TABLE tst0 ADD COLUMN v integer;
UPDATE tst0 SET v = 123456789;
CREATE INDEX ON tst0(v);
VACUUM FULL tst0;
-- tst0       | 44285952
-- tst0_i_idx | 22487040
-- tst0_n_idx |  6955008
-- tst0_v_idx |  6955008
-- tst0_z_idx |  6955008


          1. qw1
            07.07.2022 17:49
            #24506376

            Ровно поэтому, ошибочно начитав кучу NULL'ов, мы увидели всего лишьshared hit=477, а, прочитав нужные -shared hit=1007
            Я бы это объяснил кодированием переменной длины. Число '1' занимает меньше бит в строке БД, чем число '123456789'. Хотя, по схеме данных, они оба int32, но известные мне движки БД (к сожалению, не postgre, а sqlite и firebird) меньшие числа кодируют меньшим числом бит. Также и null кодируется короче, чем типичный id из generate_series, но это не значит, что есть дедупликация null-ов.


            1. Kilor Автор
              07.07.2022 17:59
              #24506408
              +1

              NULL в записи кодируется короче (битом в заголовке), но вот fixlen-значения всегда занимают все выделенное под них место. Вот тут чуть подробнее: https://habr.com/ru/post/542058/


    1. edo1h
      07.07.2022 22:20
      #24507166

      SELECT * FROM tstord WHERE val < 1000000 ORDER BY val DESC LIMIT 1000;

      а в чём разница для постгреса?
      он может настолько же эффективно исключить все null с ипользованием индекса


      1. qw1
        08.07.2022 00:45
        #24507480

        Логика моих рассуждений была в том, что в том индексе ключи лежат в отсортированном виде в последовательности:
        null, null, null, ..., null, 999999, 999998, 999997, 999996,…
        И неравенство в WHERE включит режим сканирования индекса по диапазону, сразу скипнет все null-ы и начнёт с числа. Но автор статьи меня убедил, что одинаковые ключи в индексе не повторяются (если подумать, то это даже и логично), поэтому скипнуть тут можно только 1 узел индекса.