SQL HowTo: напишете додека-јамка директно во барањето, или „Основно тринасочно“

Периодично, се поставува задачата за пребарување на поврзани податоци со помош на збир на клучеви. додека не го добиеме потребниот вкупен број на записи.

Најмногу „вистински“ пример е да се прикаже 20 најстари проблеми, наведени на списокот на вработени (на пример, во рамките на една поделба). За различни управувачки „табли“ со кратки резимеа на работни области, често се бара слична тема.

Во оваа статија ќе ја разгледаме имплементацијата во PostgreSQL на „наивно“ решение за таков проблем, „попаметен“ и многу сложен алгоритам „јамка“ во SQL со излезна состојба од пронајдените податоци, што може да биде корисно и за општ развој и за употреба во други слични случаи.

Ајде да земеме тест сет на податоци од претходната статија. За да спречите прикажаните записи да „скокаат“ од време на време кога се совпаѓаат подредените вредности, проширете го предметниот индекс со додавање на примарен клуч. Во исто време, ова веднаш ќе му даде уникатност и ќе ни гарантира дека редоследот на сортирање е недвосмислен:

CREATE INDEX ON task(owner_id, task_date, id);
-- а старый - удалим
DROP INDEX task_owner_id_task_date_idx;

Како што се слуша, така се пишува

Прво, да ја скицираме наједноставната верзија на барањето, со предавање на личните карти на изведувачите низа како влезен параметар:

SELECT
  *
FROM
  task
WHERE
  owner_id = ANY('{1,2,4,8,16,32,64,128,256,512}'::integer[])
ORDER BY
  task_date, id
LIMIT 20;

[погледнете на објаснување.tensor.ru]

Малку тажно - нарачавме само 20 плочи, но Index Scan ни ги врати 960 линии, кој потоа исто така мораше да се подреди... Да се ​​потрудиме да читаме помалку.

unnest + ARRAY

Првото размислување што ќе ни помогне е ако ни треба само 20 подредени записи, па само прочитајте не повеќе од 20 подредени по ист редослед за секој клуч. Добро, соодветен индекс (owner_id, task_date, id) имаме.

Да го користиме истиот механизам за извлекување и „ширење во колони“ запис на интегрална табела, како во последна статија. Можеме да примениме и преклопување во низа користејќи ја функцијата ARRAY():

WITH T AS (
  SELECT
    unnest(ARRAY(
      SELECT
        t
      FROM
        task t
      WHERE
        owner_id = unnest
      ORDER BY
        task_date, id
      LIMIT 20 -- ограничиваем тут...
    )) r
  FROM
    unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
  (r).*
FROM
  T
ORDER BY
  (r).task_date, (r).id
LIMIT 20; -- ... и тут - тоже

[погледнете на објаснување.tensor.ru]

О, веќе многу подобро! 40% побрзо и 4.5 пати помалку податоци Морав да го прочитам.

Материјализирање на записите од табелата преку CTEДозволете ми да ви го свртам вниманието на фактот дека во некои случаи Обидот веднаш да се работи со полињата на записот откако ќе го побарате во подпрашање, без да го „завиткате“ во CTE, може да доведе до „помножи“ InitPlan пропорционално на бројот на истите полиња:

SELECT
  ((
    SELECT
      t
    FROM
      task t
    WHERE
      owner_id = 1
    ORDER BY
      task_date, id
    LIMIT 1
  ).*);

Result  (cost=4.77..4.78 rows=1 width=16) (actual time=0.063..0.063 rows=1 loops=1)
  Buffers: shared hit=16
  InitPlan 1 (returns $0)
    ->  Limit  (cost=0.42..1.19 rows=1 width=48) (actual time=0.031..0.032 rows=1 loops=1)
          Buffers: shared hit=4
          ->  Index Scan using task_owner_id_task_date_id_idx on task t  (cost=0.42..387.57 rows=500 width=48) (actual time=0.030..0.030 rows=1 loops=1)
                Index Cond: (owner_id = 1)
                Buffers: shared hit=4
  InitPlan 2 (returns $1)
    ->  Limit  (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.009 rows=1 loops=1)
          Buffers: shared hit=4
          ->  Index Scan using task_owner_id_task_date_id_idx on task t_1  (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
                Index Cond: (owner_id = 1)
                Buffers: shared hit=4
  InitPlan 3 (returns $2)
    ->  Limit  (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.008 rows=1 loops=1)
          Buffers: shared hit=4
          ->  Index Scan using task_owner_id_task_date_id_idx on task t_2  (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
                Index Cond: (owner_id = 1)
                Buffers: shared hit=4"
  InitPlan 4 (returns $3)
    ->  Limit  (cost=0.42..1.19 rows=1 width=48) (actual time=0.009..0.009 rows=1 loops=1)
          Buffers: shared hit=4
          ->  Index Scan using task_owner_id_task_date_id_idx on task t_3  (cost=0.42..387.57 rows=500 width=48) (actual time=0.009..0.009 rows=1 loops=1)
                Index Cond: (owner_id = 1)
                Buffers: shared hit=4

Истиот рекорд беше „изгледан“ 4 пати... До PostgreSQL 11, ова однесување се случува редовно, а решението е да се „завитка“ во CTE, што е апсолутна граница за оптимизатор во овие верзии.

Рекурзивен акумулатор

Во претходната верзија, вкупно читаме 200 линии за доброто на потребните 20. Не 960, но уште помалку - дали е можно?

Ајде да се обидеме да го искористиме знаењето што ни е потребно вкупно 20 рекорди. Односно, ќе го повторуваме читањето на податоците само додека не ја достигнеме потребната количина.

Чекор 1: Почетна листа

Очигледно, нашата „целна“ листа од 20 записи треба да започне со „првите“ записи за еден од нашите клучеви сопственик_ид. Затоа, прво ќе најдеме такви „многу прво“ за секое од копчињата и додајте го во списокот, подредувајќи го по редоследот што го сакаме - (датум_задача, id).

Чекор 2: Најдете ги „следните“ записи

Сега ако го земеме првиот запис од нашата листа и почнеме „чекорете“ понатаму по индексот со зачувување на клучот owner_id, тогаш сите пронајдени записи се токму следните во добиениот избор. Се разбира, само додека не го прекрстиме клучот на задникот втор запис во списокот.

Ако се покаже дека го „прекрстивме“ вториот рекорд, тогаш последниот прочитан запис треба да се додаде на листата наместо првиот (со истиот сопственик_ид), по што повторно ја подредуваме листата.

Односно, секогаш добиваме дека списокот нема повеќе од еден запис за секое од клучевите (ако записите се потрошат и не се „вкрстиме“, тогаш првиот запис од списокот едноставно ќе исчезне и ништо нема да се додаде ), и тие секогаш подредени по растечки редослед на клучот на апликацијата (датум_задача, ид).

Чекор 3: филтрирајте и „проширете“ записи

Во некои од редовите на нашиот рекурзивен избор, некои записи rv се дуплираат - прво наоѓаме како „преминување на границата на вториот запис од списокот“, а потоа го заменуваме како 2 од списокот. Значи, првата појава треба да се филтрира.

Страшното последно прашање

WITH RECURSIVE T AS (
  -- #1 : заносим в список "первые" записи по каждому из ключей набора
  WITH wrap AS ( -- "материализуем" record'ы, чтобы обращение к полям не вызывало умножения InitPlan/SubPlan
    WITH T AS (
      SELECT
        (
          SELECT
            r
          FROM
            task r
          WHERE
            owner_id = unnest
          ORDER BY
            task_date, id
          LIMIT 1
        ) r
      FROM
        unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
    )
    SELECT
      array_agg(r ORDER BY (r).task_date, (r).id) list -- сортируем список в нужном порядке
    FROM
      T
  )
  SELECT
    list
  , list[1] rv
  , FALSE not_cross
  , 0 size
  FROM
    wrap
UNION ALL
  -- #2 : вычитываем записи 1-го по порядку ключа, пока не перешагнем через запись 2-го
  SELECT
    CASE
      -- если ничего не найдено для ключа 1-й записи
      WHEN X._r IS NOT DISTINCT FROM NULL THEN
        T.list[2:] -- убираем ее из списка
      -- если мы НЕ пересекли прикладной ключ 2-й записи
      WHEN X.not_cross THEN
        T.list -- просто протягиваем тот же список без модификаций
      -- если в списке уже нет 2-й записи
      WHEN T.list[2] IS NULL THEN
        -- просто возвращаем пустой список
        '{}'
      -- пересортировываем словарь, убирая 1-ю запись и добавляя последнюю из найденных
      ELSE (
        SELECT
          coalesce(T.list[2] || array_agg(r ORDER BY (r).task_date, (r).id), '{}')
        FROM
          unnest(T.list[3:] || X._r) r
      )
    END
  , X._r
  , X.not_cross
  , T.size + X.not_cross::integer
  FROM
    T
  , LATERAL(
      WITH wrap AS ( -- "материализуем" record
        SELECT
          CASE
            -- если все-таки "перешагнули" через 2-ю запись
            WHEN NOT T.not_cross
              -- то нужная запись - первая из спписка
              THEN T.list[1]
            ELSE ( -- если не пересекли, то ключ остался как в предыдущей записи - отталкиваемся от нее
              SELECT
                _r
              FROM
                task _r
              WHERE
                owner_id = (rv).owner_id AND
                (task_date, id) > ((rv).task_date, (rv).id)
              ORDER BY
                task_date, id
              LIMIT 1
            )
          END _r
      )
      SELECT
        _r
      , CASE
          -- если 2-й записи уже нет в списке, но мы хоть что-то нашли
          WHEN list[2] IS NULL AND _r IS DISTINCT FROM NULL THEN
            TRUE
          ELSE -- ничего не нашли или "перешагнули"
            coalesce(((_r).task_date, (_r).id) < ((list[2]).task_date, (list[2]).id), FALSE)
        END not_cross
      FROM
        wrap
    ) X
  WHERE
    T.size < 20 AND -- ограничиваем тут количество
    T.list IS DISTINCT FROM '{}' -- или пока список не кончился
)
-- #3 : "разворачиваем" записи - порядок гарантирован по построению
SELECT
  (rv).*
FROM
  T
WHERE
  not_cross; -- берем только "непересекающие" записи

[погледнете на објаснување.tensor.ru]

Така, ние тргуваше со 50% од читањата на податоците за 20% од времето на извршување. Односно, ако имате причини да верувате дека читањето може да потрае долго (на пример, податоците честопати не се во кешот, а за тоа треба да одите на диск), тогаш на овој начин можете помалку да зависите од читањето .

Во секој случај, времето на извршување се покажа подобро отколку во „наивната“ прва опција. Но, која од овие 3 опции да ја користите зависи од вас.

Извор: www.habr.com