PostgreSQL Antipatterns: "Oneindigheid is nie die limiet nie!", of 'n bietjie oor rekursie

Rekursie - 'n baie kragtige en gerieflike meganisme as dieselfde "in-diepte" aksies op verwante data uitgevoer word. Maar onbeheerde rekursie is 'n euwel wat tot óf kan lei eindelose uitvoering proses, of (wat meer dikwels gebeur) aan "eet" alle beskikbare geheue.

DBBS in hierdie verband werk op dieselfde beginsels - "Hulle het vir my gesê om te grawe, so ek grawe". Jou versoek kan nie net naburige prosesse vertraag, voortdurend verwerkerhulpbronne opneem nie, maar ook die hele databasis "drop" en alle beskikbare geheue "eet". beskerming teen oneindige rekursie - die verantwoordelikheid van die ontwikkelaar self.

In PostgreSQL, die vermoë om rekursiewe navrae te gebruik via WITH RECURSIVE verskyn in die ou tyd van weergawe 8.4, maar jy kan steeds gereeld potensieel kwesbare "weerlose" navrae teëkom. Hoe om van hierdie soort probleme ontslae te raak?

Moenie rekursiewe navrae skryf nie

En skryf nie-rekursiewe. Die uwe, jou K.O.

Trouens, PostgreSQL bied nogal baie funksies waaraan u kan gebruik geen rekursie toe te pas.

Gebruik 'n fundamenteel ander benadering tot die probleem

Soms kan jy maar van die “ander kant” na die probleem kyk. Ek het 'n voorbeeld van so 'n situasie in die artikel gegee "SQL HowTo: 1000 en een manier van samevoeging" - vermenigvuldiging van 'n stel getalle sonder die gebruik van persoonlike aggregaat funksies:

WITH RECURSIVE src AS (
  SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr
)
, T(i, val) AS (
  SELECT
    1::bigint
  , 1
UNION ALL
  SELECT
    i + 1
  , val * arr[i]
  FROM
    T
  , src
  WHERE
    i <= array_length(arr, 1)
)
SELECT
  val
FROM
  T
ORDER BY -- отбор финального результата
  i DESC
LIMIT 1;

Hierdie versoek kan vervang word met 'n opsie van wiskundekundiges:

WITH src AS (
  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
  exp(sum(ln(prime)))::integer val
FROM
  src;

Gebruik genereer_reeks in plaas van lusse

Kom ons sê ons staan ​​voor die taak om alle moontlike voorvoegsels vir 'n string te genereer 'abcdefgh':

WITH RECURSIVE T AS (
  SELECT 'abcdefgh' str
UNION ALL
  SELECT
    substr(str, 1, length(str) - 1)
  FROM
    T
  WHERE
    length(str) > 1
)
TABLE T;

Is jy seker jy het rekursie hier nodig?.. As jy gebruik LATERAL и generate_series, dan sal jy nie eers CTE nodig hê nie:

SELECT
  substr(str, 1, ln) str
FROM
  (VALUES('abcdefgh')) T(str)
, LATERAL(
    SELECT generate_series(length(str), 1, -1) ln
  ) X;

Verander databasisstruktuur

Byvoorbeeld, jy het 'n tabel van forumboodskappe met verbindings van wie op wie gereageer het, of 'n draad in sosiale netwerk:

CREATE TABLE message(
  message_id
    uuid
      PRIMARY KEY
, reply_to
    uuid
      REFERENCES message
, body
    text
);
CREATE INDEX ON message(reply_to);

Wel, 'n tipiese versoek om alle boodskappe oor een onderwerp af te laai, lyk iets soos volg:

WITH RECURSIVE T AS (
  SELECT
    *
  FROM
    message
  WHERE
    message_id = $1
UNION ALL
  SELECT
    m.*
  FROM
    T
  JOIN
    message m
      ON m.reply_to = T.message_id
)
TABLE T;

Maar aangesien ons altyd die hele onderwerp van die hoofboodskap nodig het, hoekom het ons dan nie voeg sy ID by elke inskrywing outomaties?

-- добавим поле с общим идентификатором темы и индекс на него
ALTER TABLE message
  ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);

-- инициализируем идентификатор темы в триггере при вставке
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
  NEW.theme_id = CASE
    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- берем из стартового события
    ELSE ( -- или из сообщения, на которое отвечаем
      SELECT
        theme_id
      FROM
        message
      WHERE
        message_id = NEW.reply_to
    )
  END;
  RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER ins BEFORE INSERT
  ON message
    FOR EACH ROW
      EXECUTE PROCEDURE ins();

Nou kan ons hele rekursiewe navraag tot net dit verminder word:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Gebruik toegepaste "beperkers"

As ons om een ​​of ander rede nie die struktuur van die databasis kan verander nie, kom ons kyk waarop ons kan staatmaak sodat selfs die teenwoordigheid van 'n fout in die data nie tot eindelose herhaling lei nie.

Rekursie diepte teller

Ons verhoog eenvoudig die teller met een by elke rekursiestap totdat ons 'n limiet bereik wat ons as ooglopend onvoldoende beskou:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- предел
)

Pro: Wanneer ons probeer lus, sal ons steeds nie meer as die gespesifiseerde limiet van iterasies "in diepte" doen nie.
nadele: Daar is geen waarborg dat ons nie dieselfde rekord weer sal verwerk nie - byvoorbeeld op 'n diepte van 15 en 25, en dan elke +10. En niemand het iets oor “breedte” belowe nie.

Formeel sal so 'n rekursie nie oneindig wees nie, maar as die aantal rekords by elke stap eksponensieel toeneem, weet ons almal goed hoe dit eindig ...

sien "Die probleem van korrels op 'n skaakbord"

Bewaker van die "pad"

Ons voeg alternatiewelik al die objekidentifiseerders wat ons langs die rekursiepad teëgekom het by 'n skikking, wat 'n unieke "pad" daarvoor is:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) -- не совпадает ни с одним из
)

Pro: As daar 'n siklus in die data is, sal ons absoluut nie dieselfde rekord herhaaldelik binne dieselfde pad verwerk nie.
nadele: Maar terselfdertyd kan ons letterlik al die rekords omseil sonder om onsself te herhaal.

sien "Knight's Move Probleem"

Padlengtebeperking

Om die situasie van rekursie op 'n onbegryplike diepte te vermy, kan ons die twee vorige metodes kombineer. Of, as ons nie onnodige velde wil ondersteun nie, vul die voorwaarde vir voortsetting van die rekursie aan met 'n skatting van die padlengte:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) AND
    array_length(T.path, 1) < 10
)

Kies 'n metode na jou smaak!

Bron: will.com