Skip to content

Mutually recursive query does not terminate depending on which CTE is used in the final query #14716

@aherlihy

Description

@aherlihy

What happens?

I have a mutually recursive query that models a simple points-to program analysis. As is, the query will terminate as expected. However if I switch the final statement to use a different relation (e.g. switch the last line of the snippet from recursive$1 to recursive$2), the query won't terminate. I would expect the query to terminate when all recursive CTEs reach a fixed point (so it should not matter which one is used at the end), but the behavior implies that there is something more complicated as a termination condition. Is this intended behavior?

I would really appreciate (1) if someone could point me to where in the DuckDB source code the termination condition for mutually recursive CTEs is checked, I could not figure it out myself and (2) help me understand where each mutually recursive relation is read from within each iteration. Is it always the delta from last iteration or something else? Thank you!

To Reproduce

DROP TABLE IF EXISTS new;
DROP TABLE IF EXISTS assign;
DROP TABLE IF EXISTS loadT;
DROP TABLE IF EXISTS store;
DROP TABLE IF EXISTS baseHPT;


CREATE TABLE new (
    x TEXT,
    y TEXT
);

CREATE TABLE assign (
    x TEXT,
    y TEXT
);

CREATE TABLE loadT (
    x TEXT,
    y TEXT,
    h TEXT
);

CREATE TABLE store (
    x TEXT,
    y TEXT,
    h TEXT
);

CREATE TABLE baseHPT (
    x TEXT,
    y TEXT,
    h TEXT
);

INSERT INTO new (x, y) VALUES
('a', 'b'),
('c', 'd');

INSERT INTO assign (x, y) VALUES
('e', 'a'),
('f', 'e');

INSERT INTO loadT (x, y, h) VALUES
('g', 'f', 'f');

INSERT INTO store (x, y, h) VALUES
('f', 'c', 'f');

      WITH RECURSIVE
          recursive$1 AS
            ((SELECT new$2.x as x, new$2.y as y
              FROM new as new$2)
                UNION ALL
            ((SELECT assign$4.x as x, ref$2.y as y
              FROM assign as assign$4, recursive$1 as ref$2
              WHERE assign$4.y = ref$2.x)
                UNION ALL
             (SELECT loadT$7.x as x, ref$5.h as y
              FROM loadT as loadT$7, recursive$2 as ref$5, recursive$1 as ref$6
              WHERE loadT$7.y = ref$6.x AND loadT$7.h = ref$5.y AND ref$6.y = ref$5.x))),
          recursive$2 AS
            ((SELECT *
              FROM baseHPT as baseHPT$13)
                UNION ALL
            ((SELECT ref$9.y as x, store$15.y as y, ref$10.y as h
              FROM store as store$15, recursive$1 as ref$9, recursive$1 as ref$10
              WHERE store$15.x = ref$9.x AND store$15.y = ref$10.x)))
        SELECT * FROM recursive$2 as recref$0;

OS:

tested on macos + ubuntu

DuckDB Version:

v1.1

DuckDB Client:

JDBC

Hardware:

No response

Full Name:

Anna Herlihy

Affiliation:

EPFL

What is the latest build you tested with? If possible, we recommend testing with the latest nightly build.

I have tested with a stable release

Did you include all relevant data sets for reproducing the issue?

Yes

Did you include all code required to reproduce the issue?

  • Yes, I have

Did you include all relevant configuration (e.g., CPU architecture, Python version, Linux distribution) to reproduce the issue?

  • Yes, I have

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions