By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
Help with an interesting Postgres question: Why isn't an Index Only Scan used on a partition accessed via the parent table?.
-- Data model where packages and versions are combined,
-- and dependencies refer to packages
create table packages (
package_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
name text unique not null,
version int[] not null
);
create unique index on packages(name, version);
insert into packages (name, version) values ('base', '{1,0,0,0}');
insert into packages (name, version) values ('vector', '{0,0,7,0}');
insert into packages (name, version) values ('random', '{0,1,5,8}');
insert into packages (name, version) values ('unix', '{1,2,1,0}');
insert into packages (name, version) values ('time', '{3,14,1,2}');
create table dependencies (
dependency_id bigint generated always as identity PRIMARY KEY,
dependent_id bigint references packages(package_id),
depended_id bigint references packages(package_id)
);
create unique index on dependencies(dependent_id, depended_id);
insert into dependencies (dependent_id, depended_id) values (2, 1);
insert into dependencies (dependent_id, depended_id) values (3, 1);
insert into dependencies (dependent_id, depended_id) values (3, 2);
insert into dependencies (dependent_id, depended_id) values (4, 1);
insert into dependencies (dependent_id, depended_id) values (5, 1);
insert into dependencies (dependent_id, depended_id) values (5, 3);
insert into dependencies (dependent_id, depended_id) values (5, 4);
select dependent.package_id, dependent.name as dependent, depended.name as depended
from dependencies as d1
inner join packages as dependent on d1.dependent_id = dependent.package_id
CREATE TABLE
CREATE INDEX
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
CREATE TABLE
CREATE INDEX
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
| package_id | dependent | depended |
|---|---|---|
| 2 | vector | base |
| 3 | random | base |
| 3 | random | vector |
| 4 | unix | base |
| 5 | time | base |
| 5 | time | random |
| 5 | time | unix |
SELECT 7
with recursive transitive_dependencies ( dependent_id, dependent, depended_id, breadcrumbs) as
( select dependent.package_id as dependent_id
, dependent.name as dependent
, depended.package_id as depended_id
, concat_ws(' > ', dependent.name, depended.name) as breadcrumbs
from dependencies as d1
inner join packages as dependent on d1.dependent_id = dependent.package_id
inner join packages as depended on d1.depended_id = depended.package_id
where dependent_id = 5
union all
select dependent.package_id as dependent_id
, dependent.name as dependent
, depended.package_id as depended_id
, concat_ws(' > ', t2.breadcrumbs, depended.name) as breadcrumbs
from dependencies as d1
inner join packages as dependent on d1.dependent_id = dependent.package_id
inner join packages as depended on d1.depended_id = depended.package_id
inner join transitive_dependencies as t2 on t2.depended_id = dependent.package_id
)
cycle dependent_id set is_cycle using path
select t3.dependent_id
, t3.dependent
, t3.depended_id
, t3.breadcrumbs
from transitive_dependencies as t3;
| dependent_id | dependent | depended_id | breadcrumbs |
|---|---|---|---|
| 5 | time | 1 | time > base |
| 5 | time | 3 | time > random |
| 5 | time | 4 | time > unix |
| 3 | random | 1 | time > random > base |
| 3 | random | 2 | time > random > vector |
| 4 | unix | 1 | time > unix > base |
| 2 | vector | 1 | time > random > vector > base |
SELECT 7
-- Data model where packages and releases are separated
create table packages2 (
package_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
name text unique not null
);
create table releases2 (
release_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
package_id bigint references packages2,
version int[] not null
);
create unique index on releases2(package_id, version);
insert into packages2 (name) values ('base'); -- 1
insert into packages2 (name) values ('vector'); -- 2
insert into packages2 (name) values ('random'); -- 3
insert into packages2 (name) values ('unix'); -- 4
insert into packages2 (name) values ('time'); -- 5
insert into releases2 (package_id, version) values (1, '{1,0,0,0}');
insert into releases2 (package_id, version) values (2, '{0,0,7,0}');
insert into releases2 (package_id, version) values (3, '{0,1,5,8}');
insert into releases2 (package_id, version) values (4, '{1,2,1,0}');
insert into releases2 (package_id, version) values (5, '{3,14,1,2}');
CREATE TABLE
CREATE TABLE
CREATE INDEX
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
create table dependencies2 (
dependency_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
release_id bigint references releases2 not null,
package_id bigint references packages2 not null,
requirement text not null
);
insert into dependencies2 (release_id, package_id, requirement) values ( 2, 1, '== 1.0.0.0' );
insert into dependencies2 (release_id, package_id, requirement) values ( 3, 1, '== 1.0.0.0' );
insert into dependencies2 (release_id, package_id, requirement) values ( 3, 2, '>= 0.0.7.0' );
insert into dependencies2 (release_id, package_id, requirement) values ( 4, 1, '== 1.0.0.0' );
insert into dependencies2 (release_id, package_id, requirement) values ( 5, 1, '== 1.0.0.0' );
insert into dependencies2 (release_id, package_id, requirement) values ( 5, 3, '<= 0.1.5.8' );
insert into dependencies2 (release_id, package_id, requirement) values ( 5, 4, '== 1.2.1.0' );
CREATE TABLE
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
select dependents.package_id as dependent_id
, dependents.name as dependent
, dependencies.package_id as dependencies_id
, concat_ws(' > ', dependents.name, dependencies.name) as breadcrumbs
from dependencies2 as d0
inner join releases2 as r1 on d0.release_id = r1.release_id
inner join packages2 as dependents on r1.package_id = dependents.package_id
inner join packages2 as dependencies on d0.package_id = dependencies.package_id
;
| dependent_id | dependent | dependencies_id | breadcrumbs |
|---|---|---|---|
| 2 | vector | 1 | vector > base |
| 3 | random | 1 | random > base |
| 3 | random | 2 | random > vector |
| 4 | unix | 1 | unix > base |
| 5 | time | 1 | time > base |
| 5 | time | 3 | time > random |
| 5 | time | 4 | time > unix |
SELECT 7
with recursive transitive_dependencies2 ( dependent_id, dependent, dependency_id, breadcrumbs) as
(select p2.package_id as dependent_id
, p2.name as dependent
, p3.package_id as dependency_id
, concat_ws(' > ', p2.name, p3.name) as breadcrumbs
from dependencies2 as d0
-- Dependent releases
inner join releases2 as r1 on d0.release_id = r1.release_id
-- Dependent packages
inner join packages2 as p2 on r1.package_id = p2.package_id
-- Dependencies packages
inner join packages2 as p3 on d0.package_id = p3.package_id
where r1.release_id = 5
union
select p2.package_id as dependent_id
, p2.name as dependent
, p3.package_id as dependency_id
, concat_ws(' > ', p2.name, p3.name) as breadcrumbs
from dependencies2 as d0
-- Dependent releases
inner join releases2 as r1 on d0.release_id = r1.release_id
-- Dependent packages
inner join packages2 as p2 on r1.package_id = p2.package_id
-- Dependencies packages
inner join packages2 as p3 on d0.package_id = p3.package_id
inner join transitive_dependencies2 as t2 on t2.dependency_id = p2.package_id
)
cycle dependent_id set is_cycle using path
select t3.dependent_id
, t3.dependent
, t3.dependency_id
, t3.breadcrumbs
| dependent_id | dependent | dependency_id | breadcrumbs |
|---|---|---|---|
| 5 | time | 1 | time > base |
| 5 | time | 3 | time > random |
| 5 | time | 4 | time > unix |
| 3 | random | 1 | random > base |
| 3 | random | 2 | random > vector |
| 4 | unix | 1 | unix > base |
| 2 | vector | 1 | vector > base |
SELECT 7