PostgreSQL 안티패턴: "무한대는 한계가 아닙니다!" 또는 재귀에 대한 약간의 설명

재귀 - 관련 데이터에 대해 동일한 "심층" 작업이 수행되는 경우 매우 강력하고 편리한 메커니즘입니다. 그러나 통제되지 않은 재귀는 다음 중 하나로 이어질 수 있는 해악입니다. 끝없는 실행 프로세스 또는 (더 자주 발생함) 사용 가능한 모든 메모리를 "먹는".

이와 관련하여 DBMS는 동일한 원칙에 따라 작동합니다. "파라고 해서 파는 거야". 귀하의 요청은 인접한 프로세스의 속도를 늦추고 지속적으로 프로세서 리소스를 차지할 뿐만 아니라 전체 데이터베이스를 "삭제"하여 사용 가능한 모든 메모리를 "먹습니다". 따라서 무한 재귀로부터 보호 - 개발자 자신의 책임입니다.

PostgreSQL에서는 다음을 통해 재귀 쿼리를 사용하는 기능이 있습니다. WITH RECURSIVE 버전 8.4부터 등장했지만 여전히 잠재적으로 취약한 "무방비" 요청을 자주 접할 수 있습니다. 이런 종류의 문제를 해결하는 방법은 무엇입니까?

재귀 쿼리를 작성하지 마세요

그리고 비재귀적인 것을 작성하세요. 진심으로, 당신의 K.O.

실제로 PostgreSQL은 다음 작업에 사용할 수 있는 꽤 많은 기능을 제공합니다. 아니 재귀를 적용합니다.

문제에 대해 근본적으로 다른 접근 방식을 사용하십시오.

때로는 "다른 측면"에서 문제를 볼 수도 있습니다. 나는 기사에서 그러한 상황의 예를 제시했습니다. "SQL HowTo: 1000 및 단일 집계 방법" — 사용자 정의 집계 함수를 사용하지 않고 숫자 집합의 곱셈:

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;

이 요청은 수학 전문가의 옵션으로 대체될 수 있습니다.

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

루프 대신 generate_series 사용

문자열에 대해 가능한 모든 접두사를 생성하는 작업에 직면했다고 가정해 보겠습니다. '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;

여기에 재귀가 필요합니까?.. 다음을 사용하는 경우 LATERAL и generate_series, 그러면 CTE도 필요하지 않습니다.

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

데이터베이스 구조 변경

예를 들어, 누가 누구에게 응답했는지 연결이 포함된 포럼 메시지 테이블이 있습니다. 소셜 네트워크:

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

한 주제에 대한 모든 메시지를 다운로드하라는 일반적인 요청은 다음과 같습니다.

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;

하지만 우리는 항상 루트 메시지의 전체 주제가 필요하므로 각 항목에 ID를 추가하세요. 자동적 인?

-- добавим поле с общим идентификатором темы и индекс на него
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();

이제 전체 재귀 쿼리를 다음과 같이 줄일 수 있습니다.

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

적용된 "리미터" 사용

어떤 이유로 데이터베이스의 구조를 변경할 수 없는 경우, 데이터에 오류가 있어도 끝없는 반복이 발생하지 않도록 무엇을 의지할 수 있는지 살펴보겠습니다.

재귀 깊이 카운터

우리는 명백히 부적절하다고 생각되는 한계에 도달할 때까지 각 재귀 단계에서 카운터를 하나씩 증가시킵니다.

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

직업 : 루프를 시도할 때 "깊이 있는" 반복의 지정된 제한 이상은 수행하지 않습니다.
단점 : 동일한 레코드를 다시 처리하지 않는다는 보장은 없습니다. 예를 들어 깊이 15와 25에서 그리고 +10마다. 그리고 아무도 "폭"에 대해 약속하지 않았습니다.

공식적으로 이러한 반복은 무한하지 않지만 각 단계에서 레코드 수가 기하급수적으로 증가하면 우리 모두는 그것이 어떻게 끝나는지 잘 알고 있습니다.

"체스판 위의 곡물 문제"를 참조하세요.

"길"의 수호자

우리는 재귀 경로를 따라 만난 모든 개체 식별자를 배열에 추가합니다. 배열은 배열에 대한 고유한 "경로"입니다.

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

직업 : 데이터에 순환이 있는 경우 동일한 경로 내에서 동일한 레코드를 반복적으로 처리하지 않습니다.
단점 : 그러나 동시에 우리는 반복하지 않고도 말 그대로 모든 기록을 우회할 수 있습니다.

"기사의 이동 문제"를 참조하세요.

경로 길이 제한

이해할 수 없는 깊이에서 재귀가 "방황"하는 상황을 피하기 위해 이전 두 가지 방법을 결합할 수 있습니다. 또는 불필요한 필드를 지원하지 않으려면 경로 길이 추정으로 재귀를 계속하기 위한 조건을 보완하세요.

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
)

취향에 맞게 방법을 선택해보세요!

출처 : habr.com