BUG #18064: Order of cascading deletes by foreign key; "on delete restrict"

The following bug has been logged on the website:

Bug reference:      18064
Logged by:          Ilya V. Portnov
Email address:      portnov@bk.ru
PostgreSQL version: 15.4
Operating system:   Ubuntu Linux
Description:

Hello.

I stumbled upon an interesting situation which appears when there is a
number of tables connected with foreign keys, some of which are "on delete
cascade" and others are "on delete restrict" or "on delete no action". The
general requirement is that we have one table which is "main", and related
records from other (detail) tables must be deleted automatically when one
deletes a record from the "main" table. But should be not possible to delete
from some of detail tables before deleting corresponding records from other
detail tables.
I discussed it in local telegram PSQL community, and Yaroslav Schekin
advised me to bring this matter to -bugs for discussion.

Steps to reproduce:

-- main table
create table tst_t1 (
    id int not null primary key,
    name text
);

-- other are detail tables
create table tst_a (
    id int not null primary key,
    t1id int references tst_t1 on delete cascade,
    name text
);

create table tst_b (
    id int not null primary key,
    aid int references tst_a on delete cascade,
    name text
);

create table tst_d (
    id int not null primary key,
    t1id int references tst_t1 on delete cascade,
    name text
);

create table tst_c (
    id int not null primary key,
    bid int references tst_b on delete cascade,
    did int references tst_d on delete restrict, -- or: on delete no action
    name text
);

insert into tst_t1 (id, name) values (1, 'T1');
insert into tst_a (id, t1id, name) values (1, 1, 'A');
insert into tst_b (id, aid, name) values (1, 1, 'B');
insert into tst_d (id, t1id, name) values (1, 1, 'D');
insert into tst_c (id, bid, did, name) values (1, 1, 1, 'C');

-- delete from the master table
delete from tst_t1 where id = 1;

I also tried with "on delete no action" instead of "on delete restrict", but
the result did not change.

Expected behavior:

the last delete statement works fine: all records we inserted are deleted,
and no error is thrown.
For example, in Oracle the same scenario works without error.

Actual behavior:

|--------------------------------------------------------------------------------------------------------------|
| delete from tst_t1 where id = 1
                                  |
|--------------------------------------------------------------------------------------------------------------|
| ERROR:  update or delete on table "tst_d" violates foreign key constraint
"tst_c_did_fkey" on table "tst_c"  |
| DETAIL:  Key (id)=(1) is still referenced from table "tst_c".
                                  |

My interpretation of the problem:

It appears that PostgreSQL is not able to figure out, in which order should
it delete records from detail tables in order to not be restricted with "on
delete restrict / no action" constraints. Probably PG should do topological
sorting in order to understand the correct order of deletes.

Another interpretation of problem: PG does not see the difference between
"restrict" and "no action"; as far as I understood, "restrict" variant
should do it's consistency check only after all rows which are to be deleted
by one SQL statement are deleted; but actually the check is triggered right
after "delete from tst_d", without waiting for when the record from tst_c
will be deleted by the same SQL statement.

There is more or less obvious workaround for this problem (delete from
detail records in the correct order either manually or by writing a correct
sequence of explicit triggers), but in applications with complex schemas
such workaround will take a number of man-hours. So I think PG's behavior
should be changed.

Best regards,
Ilya Portnov.