ProHoster > Блог > Администриране > SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“

Периодично възниква задача за намиране на свързани данни по набор от ключове, докато не съберем необходимото общо количество записи.

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

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“

В статията ще разгледаме реализацията на PostgreSQL на „наивен“ вариант на решение на такава задача, „по-умно“ и съвсем сложен алгоритъм „цикъл“ на SQL с условие за изход от намерените данни, който може да бъде полезен както за общо развитие, така и за приложение в други подобни случаи.

Нека вземем тестов набор от данни от предишната статия. За да не се „скачат“ изведените записи от веднъж на веднъж при съвпадение на сортираните стойности, ще разширим предметния индекс, добавяйки първичен ключ. Освен това това веднага ще му придаде уникалност и ще ни гарантира недвусмисленост на реда на сортиране:

CREATE INDEX ON task(owner_id, task_date, id);
-- а старият - ще бъде изтрит
DROP INDEX task_owner_id_task_date_idx;

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

Първо ще създадем най-простия вариант на заявката, предавайки ID на изпълнителите като масив в качестве входен параметър:

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;

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“
Както и предполагахме, намерихме всичките 30 записа. Но за това изразходихме 60% от общото време — защото направихме и 30 търсения по индекса. А по-малко — може ли?

Малко тъжно — заявихме само 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; -- ... и тук - също

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“
Както и предполагахме, намерихме всичките 30 записа. Но за това изразходихме 60% от общото време — защото направихме и 30 търсения по индекса. А по-малко — може ли?

О, вече е много по-добре! С 40% по-бързо и 4.5 пъти по-малко данни се наложи да прочетем.

Материализация на записите от таблици чрез CTEЩе обърна внимание, че в някои случаи опитът веднага да се работи с полетата на записа след неговото търсене в подзапрос, без "обвиване" в CTE може да доведе до "умножаване" на InitPlan пропорционално на броя на тези полета:

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

Резултат  (разход=4.77..4.78 редове=1 ширина=16) (реално време=0.063..0.063 редове=1 цикли=1)
  Буфери: споделено попадение=16
  Инициализационен план 1 (връща $0)
    ->  Ограничение  (разход=0.42..1.19 редове=1 ширина=48) (реално време=0.031..0.032 редове=1 цикли=1)
          Буфери: споделено попадение=4
          ->  Индексно сканиране с използване на task_owner_id_task_date_id_idx на задача t  (разход=0.42..387.57 редове=500 ширина=48) (реално време=0.030..0.030 редове=1 цикли=1)
                Условие на индекса: (owner_id = 1)
                Буфери: споделено попадение=4
  Инициализационен план 2 (връща $1)
    ->  Ограничение  (разход=0.42..1.19 редове=1 ширина=48) (реално време=0.008..0.009 редове=1 цикли=1)
          Буфери: споделено попадение=4
          ->  Индексно сканиране с използване на task_owner_id_task_date_id_idx на задача t_1  (разход=0.42..387.57 редове=500 ширина=48) (реално време=0.008..0.008 редове=1 цикли=1)
                Условие на индекса: (owner_id = 1)
                Буфери: споделено попадение=4
  Инициализационен план 3 (връща $2)
    ->  Ограничение  (разход=0.42..1.19 редове=1 ширина=48) (реално време=0.008..0.008 редове=1 цикли=1)
          Буфери: споделено попадение=4
          ->  Индексно сканиране с използване на task_owner_id_task_date_id_idx на задача t_2  (разход=0.42..387.57 редове=500 ширина=48) (реално време=0.008..0.008 редове=1 цикли=1)
                Условие на индекса: (owner_id = 1)
                Буфери: споделено попадение=4
  Инициализационен план 4 (връща $3)
    ->  Ограничение  (разход=0.42..1.19 редове=1 ширина=48) (реално време=0.009..0.009 редове=1 цикли=1)
          Буфери: споделено попадение=4
          ->  Индексно сканиране с използване на task_owner_id_task_date_id_idx на задача t_3  (разход=0.42..387.57 редове=500 ширина=48) (реално време=0.009..0.009 редове=1 цикли=1)
                Условие на индекса: (owner_id = 1)
                Буфери: споделено попадение=4

Една и съща запис „кандидатства“ 4 пъти… До PostgreSQL 11 това поведение е редовно наблюдавано, а решение е „обвиването“ в CTE, което е безусловна граница за оптимизатора в тези версии.

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

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

Нека опитаме да използваме знанието, че ни трябват всички 20 записи. Тоест ще итерираме извличането на данни само до достигане на желаното количество.

Стъпка 1: началния списък

Очевидно е, че нашият „целеви“ списък от 20 записи трябва да започне с „първите“ записи по един от нашите owner_id ключове. Ето защо първо ще намерим тези „най-първи“ по всеки от ключовете и ще ги запишем в списък, като го сортираме в желан ред — (task_date, id).

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“

Стъпка 2: намираме „следващите“ записи

Сега, ако вземем първата запис от нашия списък и започнем да „стъпваме“ по индекса като запазваме owner_id ключа, то всички намерени записи — точно следващите в резултатната селекция. Разбира се, само докато не преминем приложния ключ на втория запис в списъка.

Ако се е оказало, че сме "пресекли" втората запис, то последният прочетен запис трябва да бъде добавен в списъка вместо първия (със същия owner_id), след което списъкът отново се сортира.

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“

Тоест, ние винаги имаме в списъка не повече от една запис по всеки от ключовете (ако записите са свършили, а ние не сме "пресекли", то първата запис в списъка просто ще изчезне и нищо няма да се добави), като те винаги са сортирани в нарастващ ред на приложния ключ (task_date, id).

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“

Стъпка 3: филтрираме и "разгръщаме" записите

В част от редовете на нашия рекурсивен избор, някои записи rv се дублират — първо намираме такива, които "пресичат границата на 2-рия запис в списъка", а след това ги поставяме като 1-ви в списъка. Така че първото появяване трябва да бъде отфилтрирано.

Страшен финален запитване

С РЕКУРСИЯ T КАТО (
  -- #1 : добавяме в списъка "първите" записи по всеки от ключовете на набора
  С wrap КАТО ( -- "материализираме" записите, за да няма умножаване на InitPlan/SubPlan при достъп до полета
    С T КАТО (
      ИЗБЕРИ
        (
          ИЗБЕРИ
            r
          ОТ
            task r
          КЪДЕ
            owner_id = unnest
          ПОДРЕДИ ПО
            task_date, id
          ОГРАНИЧИ 1
        ) r
      ОТ
        unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
    )
    ИЗБЕРИ
      array_agg(r ПОДРЕДИ ПО (r).task_date, (r).id) списък -- подреждаме списъка в нужния ред
    ОТ
      T
  )
  ИЗБЕРИ
    списък
  , списък[1] rv
  , FALSE not_cross
  , 0 размер
  ОТ
    wrap
СЪЮЗ ВСИЧКИ
  -- #2 : изчитаме записи с 1-ви ред по реда на ключа, докато не преминем през записа на 2-ри
  ИЗБЕРИ
    СЛУЧАЙ
      -- ако нищо не е намерено за ключа на 1-ва запис
      КОГАТО X._r Е НЕ РАЗЛИЧНО ОТ NULL ТОГАВА
        T.списък[2:] -- махаме я от списъка
      -- ако не сме преминали ключа на 2-ри запис
      КОГАТО X.not_cross ТОГАВА
        T.списък -- просто пренасяме същия списък без модификации
      -- ако в списъка вече няма 2-ри запис
      КОГАТО T.списък[2] Е NULL ТОГАВА
        -- просто връщаме празен списък
        '{}'
      -- преопределяме речника, премахвайки 1-ви запис и добавяйки последния от намерените
      ИНАКО (
        ИЗБЕРИ
          coalesce(T.списък[2] || array_agg(r ПОДРЕДИ ПО (r).task_date, (r).id), '{}')
        ОТ
          unnest(T.списък[3:] || X._r) r
      )
    КРАЙ
  , X._r
  , X.not_cross
  , T.размер + X.not_cross::integer
  ОТ
    T
  , LATERAL(
      С wrap КАТО ( -- "материализираме" запис
        ИЗБЕРИ
          СЛУЧАЙ
            -- ако все пак сме "преминали" през 2-ри запис
            КОГАТО НЕ T.not_cross
              -- то нужният запис е първият от списъка
              ТОГАВА T.списък[1]
            ИНАКО ( -- ако не сме преминали, ключът остава като в предходния запис - от него се отталказваме
              ИЗБЕРИ
                _r
              ОТ
                task _r
              КЪДЕ
                owner_id = (rv).owner_id И
                (task_date, id) > ((rv).task_date, (rv).id)
              ПОДРЕДИ ПО
                task_date, id
              ОГРАНИЧИ 1
            )
          КРАЙ _r
      )
      ИЗБЕРИ
        _r
      , СЛУЧАЙ
          -- ако 2-ри запис вече го няма в списъка, но ние все пак сме намерили нещо
          КОГАТО списък[2] Е NULL И _r Е РАЗЛИЧНО ОТ NULL ТОГАВА
            TRUE
          ИНАКО -- нищо не намерено или "преминали"
            coalesce(((_r).task_date, (_r).id) < ((списък[2]).task_date, (списък[2]).id), FALSE)
        КРАЙ not_cross
      ОТ
        wrap
    ) X
  КЪДЕ
    T.размер < 20 И -- ограничаваме тук количеството
    T.списък Е РАЗЛИЧНО ОТ '{}' -- или докато списъкът не свърши
)
-- #3 : "развиваме" записите - редът е гарантиран по построение
ИЗБЕРИ
  (rv).* 
ОТ
  T
КЪДЕ
  not_cross; -- вземаме само "непресичащите" записи

SQL Как да напишем while цикъл директно в запитването, или „Основен триходов модел“
Както и предполагахме, намерихме всичките 30 записа. Но за това изразходихме 60% от общото време — защото направихме и 30 търсения по индекса. А по-малко — може ли?

Така че, ние разменихме 50% от четенията на данни за 20% време за изпълнение. Тоест, ако имате основания да мислите, че четенето може да отнеме време (например, данните често не са в кеша и трябва да се извлекат от диска), то по този начин можете да зависи по-малко от четенето.

Във всеки случай, времето за изпълнение се оказа по-добро в сравнение с "наивния" първи вариант. Но кой от тези 3 варианта да използвате — вие избирате.

Източник: habr.com

Купете надежден хостинг за сайтове с защита от DDoS, VPS VDS сървъри 🔥 Купете надежден хостинг за сайтове с защита от DDoS, VPS VDS сървъри | ProHoster