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, parent_id, distance) AS (
    SELECT
      folders.id,
      folders.id,
      folders.parent_id,
      0
    FROM folders
    UNION ALL
    SELECT
      descendants.folder_id,
      folders.id,
      folders.parent_id,
      descendants.distance + 1
    FROM descendants
      INNER JOIN folders ON folders.id = descendants.parent_id
  )
  SELECT
    descendants.folder_id,
    descendants.ancestor_id,
    descendants.distance
  FROM descendants
);

-- Create Function

CREATE FUNCTION ancestry(search_folder_id integer)
 RETURNS TABLE(folder_id integer, ancestor_id integer, distance integer)
 LANGUAGE sql
 IMMUTABLE PARALLEL SAFE STRICT
AS $function$
  WITH RECURSIVE descendants(folder_id, ancestor_id, parent_id, distance) AS (
    SELECT
      folders.id,
      folders.id,
      folders.parent_id,
      0 AS distance
    FROM folders
    UNION ALL
    SELECT
      descendants.folder_id,
      folders.id,
      folders.parent_id,
      descendants.distance + 1
    FROM descendants
      INNER JOIN folders ON folders.id = descendants.parent_id
  )
  SELECT
    descendants.folder_id,
    descendants.ancestor_id,
    descendants.distance
  FROM descendants
  WHERE folder_id = search_folder_id
$function$;

-- 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



CREATE FUNCTION



INSERT 0 50



INSERT 0 100



INSERT 0 20



INSERT 0 20000



INSERT 0 1000



INSERT 0 2000


-- Query permissions using the "files" table
-- Method: Window function
-- Problem: Slow, 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
                folder_ancestry.folder_id,
                permissions.user_id,
                permissions.group_id
            ORDER BY
                folder_ancestry.distance
        ) AS rank
    FROM permissions
        INNER JOIN folder_ancestry ON folder_ancestry.ancestor_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


Merge Join  (cost=271424.65..322192.63 rows=141351 width=104) (actual time=6.971..7.769 rows=2850 loops=1)

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

  ->  Subquery Scan on permission_ancestry  (cost=270888.59..319520.09 rows=6484 width=64) (actual time=5.171..5.321 rows=151 loops=1)

        Filter: (permission_ancestry.rank = 1)

        ->  WindowAgg  (cost=270888.59..303309.59 rows=1296840 width=68) (actual time=5.170..5.303 rows=151 loops=1)

              ->  Sort  (cost=270888.59..274130.69 rows=1296840 width=60) (actual time=5.159..5.174 rows=152 loops=1)

                    Sort Key: descendants.folder_id, permissions.user_id, permissions.group_id, descendants.distance

                    Sort Method: quicksort  Memory: 331kB

                    ->  Merge Join  (cost=21933.43..41699.73 rows=1296840 width=60) (actual time=1.792..2.993 rows=3000 loops=1)

                          Merge Cond: (permissions.folder_id = descendants.ancestor_id)

                          ->  Sort  (cost=159.78..165.13 rows=2140 width=48) (actual time=1.685..1.873 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.017..0.550 rows=3000 loops=1)

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

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

                                      Sort Key: descendants.ancestor_id

                                      Sort Method: quicksort  Memory: 25kB

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

                                            CTE descendants

                                              ->  Recursive Union  (cost=0.00..5832.11 rows=121200 width=16) (actual time=0.010..0.074 rows=20 loops=1)

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

                                                    ->  Hash Join  (cost=37.00..338.61 rows=12000 width=16) (actual time=0.056..0.058 rows=0 loops=1)

                                                          Hash Cond: (descendants_1.parent_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.021..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.006..0.009 rows=20 loops=1)

  ->  Sort  (cost=536.06..546.96 rows=4360 width=40) (actual time=1.791..1.948 rows=2701 loops=1)

        Sort Key: files.folder_id

        Sort Method: quicksort  Memory: 25kB

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

              Filter: (id < 20)

              Rows Removed by Filter: 19981

Planning Time: 0.861 ms

Execution Time: 8.091 ms



EXPLAIN


-- Query permissions using the "files" table
-- Method: Cross join lateral
-- See results: https://explain.dalibo.com/plan/1d7g337cg6cg4g96

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,
        folder_ancestry.distance,
        RANK() OVER (
            PARTITION BY
                folder_ancestry.folder_id,
                permissions.user_id,
                permissions.group_id
            ORDER BY
                folder_ancestry.distance
        ) AS rank
    FROM permissions
        CROSS JOIN LATERAL (
            SELECT
                folder_ancestry.folder_id,
                folder_ancestry.ancestor_id,
                folder_ancestry.distance
            FROM folder_ancestry
            WHERE folder_ancestry.ancestor_id = permissions.folder_id
        ) AS folder_ancestry
  ),
  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


Merge Join  (cost=262562.65..313330.63 rows=141351 width=104) (actual time=5.528..6.300 rows=2850 loops=1)

  Merge 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.107..4.243 rows=151 loops=1)

        Filter: (permission_ancestry.rank = 1)

        ->  WindowAgg  (cost=262026.59..294447.59 rows=1296840 width=64) (actual time=4.105..4.227 rows=151 loops=1)

              ->  Sort  (cost=262026.59..265268.69 rows=1296840 width=56) (actual time=4.097..4.112 rows=152 loops=1)

                    Sort Key: folder_ancestry.folder_id, permissions.user_id, permissions.group_id, folder_ancestry.distance

                    Sort Method: quicksort  Memory: 331kB

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

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

                          ->  Sort  (cost=159.78..165.13 rows=2140 width=48) (actual time=1.044..1.229 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.014..0.449 rows=3000 loops=1)

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

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

                                      Sort Key: folder_ancestry.ancestor_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.046 rows=20 loops=1)

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

                                                  CTE descendants

                                                    ->  Recursive Union  (cost=0.00..5832.11 rows=121200 width=16) (actual time=0.009..0.037 rows=20 loops=1)

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

                                                          ->  Hash Join  (cost=37.00..338.61 rows=12000 width=16) (actual time=0.020..0.022 rows=0 loops=1)

                                                                Hash Cond: (descendants_1.parent_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.011..0.012 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.007 rows=20 loops=1)

  ->  Sort  (cost=536.06..546.96 rows=4360 width=40) (actual time=1.418..1.575 rows=2701 loops=1)

        Sort Key: files.folder_id

        Sort Method: quicksort  Memory: 25kB

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

              Filter: (id < 20)

              Rows Removed by Filter: 19981

Planning Time: 0.509 ms

Execution Time: 6.461 ms



EXPLAIN


-- Query permissions using the "files" table
-- Method: Cross join lateral + function for rCTE

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,
        folder_ancestry.distance,
        RANK() OVER (
            PARTITION BY
                folder_ancestry.folder_id,
                permissions.user_id,
                permissions.group_id
            ORDER BY
                folder_ancestry.distance
        ) AS rank
    FROM permissions
        CROSS JOIN LATERAL ancestry(permissions.folder_id) AS folder_ancestry
  ),
  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


Merge Join  (cost=414682.93..498453.63 rows=233260 width=104) (actual time=127.712..128.565 rows=2850 loops=1)

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

  ->  Sort  (cost=536.06..546.96 rows=4360 width=40) (actual time=1.349..1.351 rows=19 loops=1)

        Sort Key: files.folder_id

        Sort Method: quicksort  Memory: 25kB

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

              Filter: (id < 20)

              Rows Removed by Filter: 19981

  ->  Materialize  (cost=414146.87..494423.62 rows=10700 width=64) (actual time=126.358..126.680 rows=2851 loops=1)

        ->  Subquery Scan on permission_ancestry  (cost=414146.87..494396.87 rows=10700 width=64) (actual time=126.355..126.480 rows=151 loops=1)

              Filter: (permission_ancestry.rank = 1)

              ->  WindowAgg  (cost=414146.87..467646.87 rows=2140000 width=64) (actual time=126.354..126.464 rows=151 loops=1)

                    ->  Sort  (cost=414146.87..419496.87 rows=2140000 width=56) (actual time=126.343..126.353 rows=152 loops=1)

                          Sort Key: folder_ancestry.folder_id, permissions.user_id, permissions.group_id, folder_ancestry.distance

                          Sort Method: quicksort  Memory: 331kB

                          ->  Nested Loop  (cost=0.25..42841.65 rows=2140000 width=56) (actual time=0.323..123.475 rows=3000 loops=1)

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

                                ->  Function Scan on ancestry folder_ancestry  (cost=0.25..10.25 rows=1000 width=8) (actual time=0.040..0.040 rows=1 loops=3000)

Planning Time: 0.247 ms

Execution Time: 128.706 ms



EXPLAIN