Postgres 13

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?.
-- Create Tables

CREATE TABLE "users" (
  id SERIAL PRIMARY KEY,
  name text NOT NULL
);

CREATE TABLE "groups" (
  id SERIAL PRIMARY KEY,
  name text NOT NULL
);

CREATE TABLE "folders" (
  id SERIAL PRIMARY KEY,
  parent_id int REFERENCES folders(id) ON DELETE CASCADE,
  name text NOT NULL
);
CREATE INDEX ON folders(parent_id);

CREATE TABLE "files" (
  id SERIAL PRIMARY KEY,
  folder_id int NOT NULL REFERENCES folders(id) ON DELETE CASCADE,
  name text NOT NULL
);
CREATE INDEX ON files(folder_id);

CREATE TABLE "permissions" (
  id SERIAL PRIMARY KEY,
  folder_id int NOT NULL REFERENCES folders(id) ON DELETE CASCADE,
  user_id int REFERENCES users(id) ON DELETE CASCADE,
  group_id int REFERENCES groups(id) ON DELETE CASCADE,
  type text NOT NULL DEFAULT 'read',
  CONSTRAINT user_or_group_not_null CHECK ((user_id IS NULL) <> (group_id IS NULL))
);
CREATE UNIQUE INDEX ON permissions(folder_id, user_id, group_id);

-- Create Views

CREATE VIEW "folder_ancestry" AS (
  WITH RECURSIVE descendants(folder_id, ancestor_id, distance) AS (
    SELECT
      folders.id,
      folders.parent_id,
      1
    FROM folders
    UNION ALL
    SELECT
      descendants_1.folder_id,
      folders.parent_id,
      descendants_1.distance + 1
    FROM descendants descendants_1
      INNER JOIN folders ON folders.id = descendants_1.ancestor_id
  )
  SELECT
    descendants.folder_id,
    descendants.ancestor_id,
    descendants.distance
  FROM descendants
);

-- Add Random Data

INSERT INTO users(name)
SELECT 'test' || g FROM generate_series(1, 50) g;
INSERT INTO groups(name)
SELECT 'test' || g FROM generate_series(1, 100) g;
INSERT INTO folders(name)
SELECT 'test' || g FROM generate_series(1, 20) g;
INSERT INTO files(name, folder_id)
SELECT 'test' || g, g2 FROM generate_series(1, 1000) g, generate_series(1, 20) g2;
INSERT INTO permissions(folder_id, user_id)
SELECT g, g2 FROM generate_series(1, 20) g, generate_series(1, 50) g2;
INSERT INTO permissions(folder_id, group_id)
SELECT g, g2 FROM generate_series(1, 20) g, generate_series(1, 100) g2;

CREATE TABLE



CREATE TABLE



CREATE TABLE



CREATE INDEX



CREATE TABLE



CREATE INDEX



CREATE TABLE



CREATE INDEX



CREATE VIEW



INSERT 0 50



INSERT 0 100



INSERT 0 20



INSERT 0 20000



INSERT 0 1000



INSERT 0 2000


-- Folder permissions
-- Problem: "Slow" window aggregation.
-- See results: https://explain.dalibo.com/plan/3f540gacg2f02f43

EXPLAIN ANALYZE
WITH permission_ancestry AS (
    SELECT
        permissions.user_id,
        permissions.group_id,
        permissions.id AS permission_id,
        permissions.type AS permission_type,
        permissions.folder_id AS permission_folder_id,
        folder_ancestry.folder_id,
        CASE
            WHEN folder_ancestry.ancestor_id IS NULL THEN 0
            ELSE folder_ancestry.distance
        END AS distance,
        RANK() OVER (
            PARTITION BY
                permissions.user_id,
                permissions.group_id,
                folder_ancestry.folder_id
            ORDER BY (
                CASE
                    WHEN folder_ancestry.ancestor_id IS NULL THEN 0
                    ELSE folder_ancestry.distance
                END
            )
        ) AS rank
    FROM permissions
        INNER JOIN folder_ancestry ON COALESCE(folder_ancestry.ancestor_id, folder_ancestry.folder_id) = permissions.folder_id
    )
SELECT *
FROM permission_ancestry
WHERE permission_ancestry.rank = 1;


QUERY PLAN


Subquery Scan on permission_ancestry  (cost=262026.59..310658.09 rows=6484 width=64) (actual time=4.855..7.233 rows=3000 loops=1)

  Filter: (permission_ancestry.rank = 1)

  ->  WindowAgg  (cost=262026.59..294447.59 rows=1296840 width=64) (actual time=4.854..6.961 rows=3000 loops=1)

        ->  Sort  (cost=262026.59..265268.69 rows=1296840 width=56) (actual time=4.841..5.032 rows=3000 loops=1)

              Sort Key: permissions.user_id, permissions.group_id, folder_ancestry.folder_id, (CASE WHEN (folder_ancestry.ancestor_id IS NULL) THEN 0 ELSE folder_ancestry.distance END)

              Sort Method: quicksort  Memory: 331kB

              ->  Merge Join  (cost=21933.43..41699.73 rows=1296840 width=56) (actual time=1.375..2.620 rows=3000 loops=1)

                    Merge Cond: (permissions.folder_id = (COALESCE(folder_ancestry.ancestor_id, folder_ancestry.folder_id)))

                    ->  Sort  (cost=159.78..165.13 rows=2140 width=48) (actual time=1.291..1.472 rows=3000 loops=1)

                          Sort Key: permissions.folder_id

                          Sort Method: quicksort  Memory: 331kB

                          ->  Seq Scan on permissions  (cost=0.00..41.40 rows=2140 width=48) (actual time=0.015..0.535 rows=3000 loops=1)

                    ->  Materialize  (cost=21773.65..22379.65 rows=121200 width=12) (actual time=0.076..0.263 rows=2851 loops=1)

                          ->  Sort  (cost=21773.65..22076.65 rows=121200 width=12) (actual time=0.074..0.078 rows=20 loops=1)

                                Sort Key: (COALESCE(folder_ancestry.ancestor_id, folder_ancestry.folder_id))

                                Sort Method: quicksort  Memory: 25kB

                                ->  Subquery Scan on folder_ancestry  (cost=5832.11..9468.11 rows=121200 width=12) (actual time=0.010..0.069 rows=20 loops=1)

                                      ->  CTE Scan on descendants  (cost=5832.11..8256.11 rows=121200 width=12) (actual time=0.009..0.066 rows=20 loops=1)

                                            CTE descendants

                                              ->  Recursive Union  (cost=0.00..5832.11 rows=121200 width=12) (actual time=0.008..0.060 rows=20 loops=1)

                                                    ->  Seq Scan on folders  (cost=0.00..22.00 rows=1200 width=12) (actual time=0.007..0.009 rows=20 loops=1)

                                                    ->  Hash Join  (cost=37.00..338.61 rows=12000 width=12) (actual time=0.046..0.047 rows=0 loops=1)

                                                          Hash Cond: (descendants_1.ancestor_id = folders_1.id)

                                                          ->  WorkTable Scan on descendants descendants_1  (cost=0.00..240.00 rows=12000 width=12) (actual time=0.001..0.002 rows=20 loops=1)

                                                          ->  Hash  (cost=22.00..22.00 rows=1200 width=8) (actual time=0.022..0.022 rows=20 loops=1)

                                                                Buckets: 2048  Batches: 1  Memory Usage: 17kB

                                                                ->  Seq Scan on folders folders_1  (cost=0.00..22.00 rows=1200 width=8) (actual time=0.004..0.007 rows=20 loops=1)

Planning Time: 0.611 ms

Execution Time: 7.427 ms



EXPLAIN


-- Query the above using the "files" table
-- Problem: Even slower, as folder_id is only compared on the last step.
-- See results: https://explain.dalibo.com/plan/7e537cc6a5718c56

EXPLAIN ANALYZE
WITH permission_ancestry AS (
    SELECT
        permissions.user_id,
        permissions.group_id,
        permissions.id AS permission_id,
        permissions.type AS permission_type,
        permissions.folder_id AS permission_folder_id,
        folder_ancestry.folder_id,
        CASE
            WHEN folder_ancestry.ancestor_id IS NULL THEN 0
            ELSE folder_ancestry.distance
        END AS distance,
        RANK() OVER (
            PARTITION BY
                permissions.user_id,
                permissions.group_id,
                folder_ancestry.folder_id
            ORDER BY (
                CASE
                    WHEN folder_ancestry.ancestor_id IS NULL THEN 0
                    ELSE folder_ancestry.distance
                END
            )
        ) AS rank
    FROM permissions
        INNER JOIN folder_ancestry ON COALESCE(folder_ancestry.ancestor_id, folder_ancestry.folder_id) = permissions.folder_id
    ),
  folder_permissions AS (
    SELECT *
    FROM permission_ancestry
    WHERE permission_ancestry.rank = 1
  )
SELECT *
FROM files
    INNER JOIN folder_permissions ON folder_permissions.folder_id = files.folder_id
WHERE
  files.id < 20;


QUERY PLAN


Hash Join  (cost=262353.59..315948.59 rows=141351 width=104) (actual time=6.410..9.385 rows=2850 loops=1)

  Hash Cond: (permission_ancestry.folder_id = files.folder_id)

  ->  Subquery Scan on permission_ancestry  (cost=262026.59..310658.09 rows=6484 width=64) (actual time=4.656..7.049 rows=3000 loops=1)

        Filter: (permission_ancestry.rank = 1)

        ->  WindowAgg  (cost=262026.59..294447.59 rows=1296840 width=64) (actual time=4.655..6.781 rows=3000 loops=1)

              ->  Sort  (cost=262026.59..265268.69 rows=1296840 width=56) (actual time=4.634..4.825 rows=3000 loops=1)

                    Sort Key: permissions.user_id, permissions.group_id, folder_ancestry.folder_id, (CASE WHEN (folder_ancestry.ancestor_id IS NULL) THEN 0 ELSE folder_ancestry.distance END)

                    Sort Method: quicksort  Memory: 331kB

                    ->  Merge Join  (cost=21933.43..41699.73 rows=1296840 width=56) (actual time=1.193..2.438 rows=3000 loops=1)

                          Merge Cond: (permissions.folder_id = (COALESCE(folder_ancestry.ancestor_id, folder_ancestry.folder_id)))

                          ->  Sort  (cost=159.78..165.13 rows=2140 width=48) (actual time=1.118..1.312 rows=3000 loops=1)

                                Sort Key: permissions.folder_id

                                Sort Method: quicksort  Memory: 331kB

                                ->  Seq Scan on permissions  (cost=0.00..41.40 rows=2140 width=48) (actual time=0.010..0.437 rows=3000 loops=1)

                          ->  Materialize  (cost=21773.65..22379.65 rows=121200 width=12) (actual time=0.072..0.259 rows=2851 loops=1)

                                ->  Sort  (cost=21773.65..22076.65 rows=121200 width=12) (actual time=0.070..0.074 rows=20 loops=1)

                                      Sort Key: (COALESCE(folder_ancestry.ancestor_id, folder_ancestry.folder_id))

                                      Sort Method: quicksort  Memory: 25kB

                                      ->  Subquery Scan on folder_ancestry  (cost=5832.11..9468.11 rows=121200 width=12) (actual time=0.008..0.065 rows=20 loops=1)

                                            ->  CTE Scan on descendants  (cost=5832.11..8256.11 rows=121200 width=12) (actual time=0.008..0.062 rows=20 loops=1)

                                                  CTE descendants

                                                    ->  Recursive Union  (cost=0.00..5832.11 rows=121200 width=12) (actual time=0.007..0.057 rows=20 loops=1)

                                                          ->  Seq Scan on folders  (cost=0.00..22.00 rows=1200 width=12) (actual time=0.006..0.009 rows=20 loops=1)

                                                          ->  Hash Join  (cost=37.00..338.61 rows=12000 width=12) (actual time=0.044..0.045 rows=0 loops=1)

                                                                Hash Cond: (descendants_1.ancestor_id = folders_1.id)

                                                                ->  WorkTable Scan on descendants descendants_1  (cost=0.00..240.00 rows=12000 width=12) (actual time=0.001..0.002 rows=20 loops=1)

                                                                ->  Hash  (cost=22.00..22.00 rows=1200 width=8) (actual time=0.022..0.022 rows=20 loops=1)

                                                                      Buckets: 2048  Batches: 1  Memory Usage: 17kB

                                                                      ->  Seq Scan on folders folders_1  (cost=0.00..22.00 rows=1200 width=8) (actual time=0.005..0.008 rows=20 loops=1)

  ->  Hash  (cost=272.50..272.50 rows=4360 width=40) (actual time=1.748..1.748 rows=19 loops=1)

        Buckets: 8192  Batches: 1  Memory Usage: 65kB

        ->  Seq Scan on files  (cost=0.00..272.50 rows=4360 width=40) (actual time=0.016..1.744 rows=19 loops=1)

              Filter: (id < 20)

              Rows Removed by Filter: 19981

Planning Time: 0.488 ms

Execution Time: 9.546 ms



EXPLAIN