Thread: BUG #17703: Recursive query early terminate when subquery result of the recursive term is NULL

The following bug has been logged on the website:

Bug reference:      17703
Logged by:          Jiangshan Liu
Email address:      jiangshan.liu@tju.edu.cn
PostgreSQL version: 15.1
Operating system:   Ubuntu 18.04.6 LTS
Description:

Hello! I actually found the problem stems from a more complex code, this is
the example after minimization.

-- create table and insert data
DROP TABLE IF EXISTS "public"."table1";
CREATE TABLE "public"."table1" (
  "id" int4 NOT NULL
);
INSERT INTO "public"."table1" VALUES (1);
INSERT INTO "public"."table1" VALUES (2);
INSERT INTO "public"."table1" VALUES (3);

-- execute recursive query with potential early terminate
WITH RECURSIVE run(__AUX_CTRL_COL_REC__,__AUX_CTRL_COL_RES__,i,r,id_table1)
AS (
(SELECT True, NULL::int, i_0, r_0, id_table1 FROM
  LATERAL (SELECT NULL::int) AS let_id_table1(id_table1),
  LATERAL (SELECT ( 0)::int) AS let_r_0(r_0),
  LATERAL (SELECT ( 1)::int) AS let_i_0(i_0))
    UNION ALL
  SELECT result.* FROM run,
    LATERAL (
      (SELECT if_p_0.* FROM
        LATERAL (SELECT ( i <= 10)::boolean) AS let_p_0(p_0),
        LATERAL (
          SELECT True, NULL::int, i_1, r_1, id_table1_0 FROM
            LATERAL ( SELECT id FROM table1 WHERE id = i ) AS
let_id_table1_0(id_table1_0),
            LATERAL (SELECT ( r + 1)::int) AS let_r_1(r_1),
            LATERAL (SELECT ( i + 1)::int) AS let_i_1(i_1)
            WHERE p_0
              UNION ALL
          SELECT False, r, NULL::int, NULL::int, NULL::int
            WHERE NOT p_0 OR p_0 IS NULL
        )AS if_p_0
      )
    )AS result
    WHERE run.__AUX_CTRL_COL_REC__
)
SELECT run.__AUX_CTRL_COL_RES__ AS test FROM run WHERE NOT
run.__AUX_CTRL_COL_REC__;
-- end of example

The result table of recursive query has 1 expected column named "test", but
it is an unexpected empty table with 0 row.
 test 
------
(0 row)

Actually, if recursive query does not early terminate, it will return result
with 1 row. The value of result will be 10. I remove the SELECT subquery in
LATERAL and the result performs normally.

-- execute normal recursive query
WITH RECURSIVE run(__AUX_CTRL_COL_REC__,__AUX_CTRL_COL_RES__,i,r,id_table1)
AS (
(SELECT True, NULL::int, i_0, r_0, id_table1 FROM
  LATERAL (SELECT NULL::int) AS let_id_table1(id_table1),
  LATERAL (SELECT ( 0)::int) AS let_r_0(r_0),
  LATERAL (SELECT ( 1)::int) AS let_i_0(i_0))
    UNION ALL
  SELECT result.* FROM run,
    LATERAL (
      (SELECT if_p_0.* FROM
        LATERAL (SELECT ( i <= 10)::boolean) AS let_p_0(p_0),
        LATERAL (
          SELECT True, NULL::int, i_1, r_1, id_table1 FROM
            LATERAL (SELECT ( r + 1)::int) AS let_r_1(r_1),
            LATERAL (SELECT ( i + 1)::int) AS let_i_1(i_1)
            WHERE p_0
              UNION ALL
          SELECT False, r, NULL::int, NULL::int, NULL::int
            WHERE NOT p_0 OR p_0 IS NULL
        )AS if_p_0
      )
    )AS result
    WHERE run.__AUX_CTRL_COL_REC__
)
SELECT run.__AUX_CTRL_COL_RES__ AS test FROM run WHERE NOT
run.__AUX_CTRL_COL_REC__;
-- end of example

The result of this query is expected.
 test 
------
   10
(1 row)

This is an unexpected case where the recursive query seems to have
terminated early. I wanted to figure out the details of the problem, so I
replaced the final SELECT query of the recursive query from 
  SELECT run.__AUX_CTRL_COL_RES__ AS test FROM run WHERE NOT
run.__AUX_CTRL_COL_REC__;
to
  SELECT * FROM run;
and I got the intermediate results of recursive query.

-- intermediate results of recursive query with potential early terminate
 __aux_ctrl_col_rec__ | __aux_ctrl_col_res__ | i | r | id_table1 
----------------------+----------------------+---+---+-----------
 t                    |                      | 1 | 0 |          
 t                    |                      | 2 | 1 |         1
 t                    |                      | 3 | 2 |         2
 t                    |                      | 4 | 3 |         3
(4 rows)

-- intermediate results of normal recursive query
 __aux_ctrl_col_rec__ | __aux_ctrl_col_res__ | i  | r  | id_table1 
----------------------+----------------------+----+----+-----------
 t                    |                      |  1 |  0 |          
 t                    |                      |  2 |  1 |          
 t                    |                      |  3 |  2 |          
 t                    |                      |  4 |  3 |          
 t                    |                      |  5 |  4 |          
 t                    |                      |  6 |  5 |          
 t                    |                      |  7 |  6 |          
 t                    |                      |  8 |  7 |          
 t                    |                      |  9 |  8 |          
 t                    |                      | 10 |  9 |          
 t                    |                      | 11 | 10 |          
 f                    |                   10 |    |    |          
(12 rows)

This is all the objective phenomenon I have observed. It looks like during
the recursive query, the subquery result of
  SELECT id FROM table1 WHERE id = i
is NULL when i=4 is encountered, leading to an unexpected early termination
of the recursive query. Is this a bug of recursive query, and how to avoid
this early termination?


By the way, I would like to elaborate on the importance of this query
structure for me, even though it is a subjective motivation and may mean
nothing to you. Please think of it as a nag.
I want to use recursive queries in SQL to replace LOOP statements in
PL/pgSQL. The methodology used draws on the paper [1]. The initial problem
stems from the equivalence of the recursive query with potential early
terminate above and this PL/SQL function.

-- drop function
DROP FUNCTION test();

-- create function
CREATE OR REPLACE FUNCTION test() RETURNS int AS $$
DECLARE
    id_table1 int;
    r int := 0;
BEGIN
    FOR i IN 1 .. 10 LOOP
        id_table1 := (SELECT id FROM table1 WHERE id = i);
        r := r+1;
    END LOOP;
    return r;
END;
$$ LANGUAGE PLPGSQL;

-- call function
SELECT test();
-- end of example

The result of function call is expected.
 test 
------
   10
(1 row)

And the normal recursive query is equivalent to removing the 
  id_table1 := (SELECT id FROM table1 WHERE id = i);
statement from this PL/SQL function.

It also returns an expected result table.
 test 
------
   10
(1 row)

----
[1] Hirn, Denis, and Torsten Grust. "One with recursive is worth many
GOTOs." Proceedings of the 2021 International Conference on Management of
Data. 2021.

Thank you and look forward to your reply!

Regards,
Jiangshan Liu