ProHoster > Blog > Rêveberî > SQL HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"

SQL HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"

Dem bi dem, peywira lêgerîna daneyên têkildar bi karanîna komek kilîtan derdikeve holê. heta ku em hejmara giştî ya tomarên pêwîst bistînin.

Mînaka herî "jiyana rast" nîşan e 20 pirsgirêkên herî kevn, di lîsteyê de li ser lîsteya karmendan (mînak, di nav yek dabeşkirinê de). Ji bo "dashboard"ên rêveberiyê yên cihêreng ên bi kurtasî yên qadên xebatê, mijarek wekhev pir caran hewce ye.

SQL HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"

Di vê gotarê de em ê li bicîhkirina PostgreSQL-ya çareseriyek "naîf" a pirsgirêkek wusa, algorîtmayek "aqilmend" û pir tevlihev binêrin. "loop" di SQL de bi şertek derketinê ji daneyên ku hatine dîtin, ku dikare hem ji bo pêşkeftina gelemperî û hem jî ji bo karanîna di rewşên din ên bi vî rengî de bikêr be.

Werin em komek daneya testê ji xwe bistînin gotara berê. Ji bo ku tomarên ku têne xuyang kirin ku dem bi dem dema ku nirxên rêzkirî bi hev re hevûdu ne "hilweşînin", bi lêzêdekirina mifteyek seretayî navnîşa mijarê berfireh bikin. Di heman demê de, ev ê tavilê wê yektabûnê bide û ji me re garantî bike ku rêzika veqetandinê nezelal e:

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

Çawa tê bihîstin, wisa jî hatiye nivîsandin

Pêşîn, bila em guhertoya herî hêsan a daxwazê ​​xêz bikin, ku nasnameyên performeran derbas bikin array wek parametre input:

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 HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"
[li ser şirove.tensor.ru binêre]

Piçek xemgîn - me tenê 20 tomar ferman kir, lê Index Scan ew li me vegerand 960 xetên, ku paşê jî diviyabû bihata rêzkirin... Em hewl bidin ku kêm bixwînin.

unnest + ARRAY

Nîqaşa yekem ku dê alîkariya me bike ev e ku ger hewce be tenê 20 veqetandî tomar, paşê tenê bixwînin ne bêtir ji 20 bi heman rêzê ji bo her yek qûfle. Baş, index minasib (xwedî_id, erk_date, id) me hene.

Werin em heman mekanîzmayê ji bo derxistin û "belavkirina nav stûnan" bikar bînin tomar sifrê entegre, wek di gotara dawî. Di heman demê de em dikarin bi karanîna fonksiyonê pelçiqandina nav rêzek jî bicîh bikin 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 HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"
[li ser şirove.tensor.ru binêre]

Oh, jixwe pir çêtir! 40% zûtir û 4.5 carî daneyên kêmtir Diviya bû ez bixwînim.

Materyalîzekirina tomarên tabloyê bi CTEBila bala we bikşînim ser wê yekê ku di hin rewşan de Hewldanek ku meriv tavilê bi zeviyên tomarê re bixebite piştî ku li wê di binpirsekê de bigere, bêyî ku wê di CTE de "pêç bike", dikare bibe sedema InitPlan "pircar bikin". li gorî hejmara van heman zeviyan:

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

Heman tomar 4 caran "nihêrî" bû... Heya PostgreSQL 11, ev tevger bi rêkûpêk çêdibe, û çareserî ew e ku ew di CTE de "pêçandin" e, ku ji bo optimîzatorê di van versiyonan de sînorek bêkêmasî ye.

Acumulatorê vegerî

Di guhertoya berê de, bi tevahî em dixwînin 200 xetên ji bo xatirê 20. Ne 960, lê hê kêmtir jî - ev gengaz e?

Werin em hewl bidin ku zanîna ku em hewce ne bikar bînin 20 tomar dike. Ango, em ê xwendina daneyê tenê dubare bikin heya ku em bigihîjin mîqdara ku em hewce ne.

Gav 1: Lîsteya Destpêkê

Eşkere ye, navnîşa meya "armanc" a ji 20 tomaran divê bi tomarên "yekemîn" ji bo yek ji bişkojkên meya xwediyê_id dest pê bike. Ji ber vê yekê, pêşî em ê weha bibînin "pir yekem" ji bo her yek ji keys û wê li navnîşê zêde bikin, li gorî rêza ku em dixwazin - (task_date, id) rêz bikin.

SQL HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"

Gav 2: Têketinên "paşê" bibînin

Naha heke em navnîşa yekem ji navnîşa xwe bistînin û dest pê bikin "gavek" bêtir li ser index parastina mifteya xwediyê_id-ê, wê hingê hemî tomarên hatine dîtin tam yên din ên di hilbijartina encam de ne. Bê guman, tenê heta ku em kilîla qûnê derbas bikin navnîşa duyemîn di lîsteyê de.

Ger derkeve holê ku me qeyda duyemîn "derbas kir", wê hingê têketina dawî ya xwendinê li şûna ya yekem divê li navnîşê were zêdekirin (bi heman xwediyê_id), piştî ku em navnîşê ji nû ve rêz bikin.

SQL HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"

Ango, em her gav werdigirin ku navnîş ji bo her bişkojkê ji yek têketinê zêdetir nîne (heke têketin bi dawî bibin û em "xaç nekin", wê hingê têketina yekem ji navnîşê dê bi hêsanî winda bibe û tiştek nayê zêdekirin. ), û ew her tim rêz kirin bi rêza hilkişîna mifteya serîlêdanê (task_date, id).

SQL HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"

Gava 3: Parzûna û "berfireh" tomar

Di hin rêzikên hilbijartina meya vegerî de, hin tomar hene rv têne dubare kirin - pêşî em wekî "derbaskirina sînorê navnîşa 2-emîn a navnîşê" dibînin, û dûv re wê wekî 1-emîn ji navnîşê biguhezînin. Ji ber vê yekê bûyera yekem pêdivî ye ku were fîlter kirin.

Pirsa dawî ya tirsnak

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; -- берем только "непересекающие" записи

SQL HowTo: nivîsandina dema ku rasterast di pirsê de, an "Elementary sê-gav"
[li ser şirove.tensor.ru binêre]

Bi vî awayî, em 50% ji daneyên xwendinê ji bo 20% ji dema darvekirinê bazirganî kir. Ango, heke sedemên we hebin ku hûn bawer bikin ku xwendin dibe ku demek dirêj bigire (mînak, dane bi gelemperî ne di cache de ne, û hûn neçar in ku ji bo wê biçin dîskê), wê hingê hûn dikarin bi vî rengî kêmtir bi xwendinê ve girêdayî bin. .

Di her rewşê de, dema darvekirinê ji vebijarka yekem a "naîf" çêtir derket. Lê kîjan ji van 3 vebijarkên ku hûn bikar bînin li ser we ye.

Source: www.habr.com

Add a comment