PostgreSQL递归迭代生成中间点方案优化咨询

我需要在PostgreSQL中通过递归/迭代方式完成以下计算：现有直线上的两个初始点，在每对已有点的中点生成新点，同时记录每个点的位置（pos）、生成步骤（step）以及父点（Parent A、Parent B）信息。我已经实现了一套方案，现在寻求更优的解法。

示例数据初始化 #

CREATE TABLE IF NOT EXISTS public.points
(
    pos real
)
TABLESPACE pg_default;

INSERT INTO points VALUES (0),(1024);

期望输出格式 #

现有实现代码 #

自定义类型定义 #

CREATE TYPE public.points_type AS
(
    pos real,
    step integer,
    parenta real,
    parentb real
);

CREATE TYPE public.points_type_input AS
(
    pos real,
    step integer
);

中点计算函数 #

CREATE OR REPLACE FUNCTION public.points_calc(
_points points_type_input[])
    RETURNS SETOF points_type
    LANGUAGE 'plpgsql'
    COST 100
    VOLATILE PARALLEL UNSAFE
    ROWS 1000
AS $BODY$
 declare
 new_point points_type;
 Begin 
    FOR new_point IN 
        SELECT  (new_p).pos AS pos,
                (new_p).stepnow +1 AS step,
                (new_p).parentA AS parentA,
                (new_p).parentB AS parentB
        FROM (
            SELECT  ((p1.pos + p2.pos)/2)::real AS pos,
                    (array_agg(p1.pos) OVER (PARTITION BY 1)) AS oldpos,
                    (max(p1.step) OVER (PARTITION BY 1)) AS stepnow,
                    p1.pos AS parentA,
                    p2.pos AS parentB
            FROM unnest(_points) p1
            CROSS JOIN unnest(_points) p2
            WHERE p1.pos < p2.pos
        ) new_p
        WHERE not ARRAY[pos] <@ oldpos
    LOOP
        RETURN NEXT new_point;
    END LOOP;
    RETURN;
 END                                             

$BODY$;

迭代执行函数 #

CREATE OR REPLACE FUNCTION points_v2(end_step integer)
  RETURNS TABLE(pos real, step integer, parenta real, parentb real)
  LANGUAGE plpgsql AS
$func$
DECLARE
   t record;
   a boolean;
   cnt integer;
BEGIN
   DROP TABLE IF EXISTS pg_temp.result2;
   CREATE TEMP TABLE result2 (pos real, step integer, parenta real, parentb real) ON COMMIT DROP;

   FOR t IN 
          TABLE points ORDER BY pos
   LOOP
      INSERT INTO result2(pos, step, parenta, parentb)
        SELECT t.pos, 1 AS step, -1 AS parenta, -1 AS parentb;
   END LOOP;
    a = true;
    cnt = 0;
    WHILE a AND cnt<end_step
    LOOP
    a = false;
    cnt = cnt + 1;
       FOR t IN 
            SELECT  (newpoints.result).pos,
                (newpoints.result).step,
                (newpoints.result).parenta,
                (newpoints.result).parentb
            FROM ( SELECT points_calc(array_agg(ROW(p.pos, p.step)::points_type_input)) AS result
            FROM result2 p
            ) newpoints
       LOOP
            a = true;
            INSERT INTO result2(pos, step, parenta, parentb)
            SELECT t.pos, t.step, t.parenta, t.parentb;
       END LOOP;
   END LOOP;
   RETURN QUERY
   SELECT r.pos, r.step, r.parenta, r.parentb
   FROM   result2 r;
END
$func$;

调用语句 #

SELECT * FROM points_v2(3);

更优解法：使用递归CTE #

现有实现依赖自定义类型和PL/pgSQL循环，存在额外的类型转换和临时表开销。可以用递归CTE直接实现，代码更简洁高效，无需自定义类型和额外函数：

WITH RECURSIVE point_tree AS (
    -- 初始点：step=1，父点设为-1
    SELECT 
        pos,
        1 AS step,
        -1::real AS parenta,
        -1::real AS parentb
    FROM points
    UNION ALL
    -- 递归步骤：生成每对相邻点的中点，step+1，记录父点
    SELECT 
        (p1.pos + p2.pos)/2::real AS pos,
        p1.step + 1 AS step,
        p1.pos AS parenta,
        p2.pos AS parentb
    FROM point_tree p1
    JOIN point_tree p2 ON p2.pos > p1.pos
    -- 确保只生成相邻点的中点，避免重复计算
    AND NOT EXISTS (
        SELECT 1 FROM point_tree p3 
        WHERE p3.pos > p1.pos AND p3.pos < p2.pos
    )
    -- 控制递归深度
    WHERE p1.step < 3 -- 替换为你需要的结束step
)
SELECT * FROM point_tree ORDER BY step, pos;

解法优势 #

1. 无需自定义类型：直接用原生SQL实现，减少代码复杂度
2. 避免循环和临时表：递归CTE由PostgreSQL优化器高效处理，性能优于PL/pgSQL循环
3. 逻辑更清晰：初始条件和递归规则一目了然，易于维护
4. 可直接控制深度：修改WHERE p1.step < 3中的数值即可调整生成的步骤数

如果需要封装成可复用的函数，也可以基于递归CTE创建函数：

CREATE OR REPLACE FUNCTION generate_midpoints(end_step integer)
RETURNS TABLE(pos real, step integer, parenta real, parentb real)
LANGUAGE sql AS
$func$
WITH RECURSIVE point_tree AS (
    SELECT 
        pos,
        1 AS step,
        -1::real AS parenta,
        -1::real AS parentb
    FROM points
    UNION ALL
    SELECT 
        (p1.pos + p2.pos)/2::real AS pos,
        p1.step + 1 AS step,
        p1.pos AS parenta,
        p2.pos AS parentb
    FROM point_tree p1
    JOIN point_tree p2 ON p2.pos > p1.pos
    AND NOT EXISTS (
        SELECT 1 FROM point_tree p3 
        WHERE p3.pos > p1.pos AND p3.pos < p2.pos
    )
    WHERE p1.step < end_step
)
SELECT * FROM point_tree ORDER BY step, pos;
$func$;

调用方式：

SELECT * FROM generate_midpoints(3);

内容的提问来源于stack exchange，提问作者lrahlff