Optimizing query that finds closest unique records

Question

I've been trying out different queries to get the best performance when querying hierarchical data on Postgres 13.6.

• Fiddle: https://dbfiddle.uk/060f_h96
• Explain: https://explain.dalibo.com/plan/7e537cc6a5718c56

Background

I have the following tables in my database: folders, users, groups, permissions.

# \d users;
Column    | Type | Nullable
id        | int  | not null
name      | text | not null

# \d groups;
Column    | Type | Nullable
id        | int  | not null
name      | text | not null

# \d folders;
Column    | Type | Nullable
id        | int  | not null
parent_id | int  |
name      | text | not null

# \d permissions;
Column    | Type | Nullable
id        | int  | not null
folder_id | int  | not null
user_id   | int  |
group_id  | int  |
type      | text |
-- constraint: user_id IS NULL <> group_id IS NULL
-- type: e.g. 'read' or 'edit'

I also have a view called folder_ancestry that runs a recursive CTE query on the folders table to build an ancestry tree. It's very fast:

# SELECT * FROM folder_ancestry;
folder_id | ancestor_id | distance
1         | NULL        | 1
2         | NULL        | 2
2         | 1           | 1

Well, this works

I am trying to get the closest user (user_id) or group (group_id) permission for each folder_id. I have achieved this with a rank() windowed function, which is pretty fast:

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

Performance issue

Here is where I'm facing a performance problem. If I query the above with a specific folder_id, the query is super fast as it only looks up permissions for a specific folder_id. However, when I join the query above with another table, the planner will gather every folder permission, and then filter it down to the 3 that I actually need:

SELECT *
FROM file_versions
    INNER JOIN files ON files.id = file_versions.file_id
    INNER JOIN folder_permissions ON folder_permissions.folder_id = files.folder_id
WHERE file_versions.status = 'complete'

Is there a way I can change something so that the planner finds the file folders first, and only then runs the query on those folder_id fields?

Or is there a better way to write the permission summarizer query that gets unique relationships without having to run another query to check where the rank = 1?

Thank you for your help.

Update 1

I have changed the folder_ancestry view to have 0 distances so that I don't have to use a case statement when trying to find the closest permission.

I also created a function called ancestry() that does the same things as the folder_ancestry view, but for a single folder ID.

Fiddle: https://dbfiddle.uk/7OVDpJrj

The literal join with a function in the fiddle is very slow for some reason; however, I'm getting similar results when using literal join with a function vs using literal join with a view on live data.

I suppose I could move everything (including the rank() window function) into a new permissions function, but I was hoping I could get away with views.

Observation on live data

What's interesting, is that I was tinkering with the queries on the live data, and noticed that Postgres pushes down predicates nicely into the "with" part of the query that uses the folder_ancestry view with a lateral join. It does not do the push down the same predicates as soon as I move the "with" part into its own view.

I tried researching this and found that rCTE and aggregation might break pushing things down, but even after trying to make folder_ancestry a materialized view and changing window aggregator to a distinct on(), the planner still fails to push predicates.

Update

I ended up removing the RANK() window function in favor of DISTINCT ON and it has sped up the query about performance 10x.

Answer 1

You may need to manually push down the conditions, or rewrite the join to start with the smaller table. Depending on the version of PostgreSQL in use, CTEs can also be an optimization barrier (not so much on PG13). As we say, “Join to the aggregate, don’t aggregate the join.”

A fiddle would help with developing a more concrete answer.

Update 1

The way forward might be to redefine folder_ancestry as a table-returning function, then call it as a lateral join with the list of files/folders you are interested in and join the resultant set with permissions. The distance parameter is maintained so your app can make the determination of what is the "closest" permission, and you can run your RANK() window function as well. This way we're only searching for the requested data and nothing more.

The function definition would be something like this, but with a rCTE that returns just the path to the root starting at infolder (this definition does NOT do that, but works with the fiddle data for illustration purposes):

CREATE OR REPLACE FUNCTION ancestry(infolder 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, 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 WHERE folder_id=infolder
$function$

Then call with

SELECT * FROM files, ancestry(files.id) a 
JOIN permissions fp USING (folder_id) WHERE files.id<20;

For the comma operator adverse:

select * from files
cross join lateral ancestry(files.id) a 
join permissions fp on a.folder_id=fp.folder_id
where files.id<20

You'll have to try this on your live data to see if there is any significant performance improvement. The fiddle's data set is too small to see any appreciable speed difference (both the 2nd query and my function-based one with the window function run in about 10ms on my personal server).

And of course the rCTE is wrong. I will try to figure that out for the next update. Unless someone else who can write them wants to contribute one.