V5: performance regression with RLS

[maximsmol]

Summary

Note: filed as a "question" rather than a bug since I am not including a working reproduction.

V5 splits some foreign-key joins into multiple SQL queries, producing SQL similar to the following in the subfield query:

select
  __result__.*
from (
  select
    ids.ordinality - 1
      as idx,
    (ids.value->>0)::"int8"
      as "id0"
  from
    json_array_elements($1::json) with ordinality
    as ids
)
  as __identifiers__,
lateral (
  select
    __table__.id::text
      as "0",
    __table__."data"::text
      as "1",
    __identifiers__.idx
      as "2"
  from
    "public"."ldata_node_event_ingress"
    as __table__
  where
    (__table__."id" = __identifiers__."id0")
) as __result__;

For contrast, here is roughly what V4 produced to query the same data:

select to_json(
  (
    json_build_object(
      '__identifiers'::text,
      json_build_array(
        (
          (__local_1__."id")::numeric
        )::text
      ),
      'id'::text,
      ((__local_1__."id"))::text,
      '@table'::text,
      (
        select json_build_object(
          '__identifiers'::text,
          json_build_array(
            (
              (__local_2__."id")::numeric
            )::text
          ),
          'id'::text,
          ((__local_2__."id"))::text,
          '@data'::text,
          (
            (
              (__local_2__."data")
            )::text
          )
        ) as object
        from "public"."table" as __local_2__
        where (
          __local_1__."table_id" = __local_2__."id"
        ) and (TRUE) and (TRUE)
      )
    )
  )
) as "@tables"
from
  "public"."top_level_table" as __local_1__

The former query is much slower when RLS is involved if public.table is large as the planner creates a plan with a very bad bad estimate for the number of rows that will pass the filter. The plan usually looks like this:

Hash Join  (cost=... rows=75 width=...) (actual time=... rows=0 loops=1)
Hash Cond: (__table__.id = ((ids.value ->> 0))::bigint)
->  Seq Scan on table __table__  (cost=... rows=1000000 width=...) (actual time=... rows=0 loops=1)
      Filter: (table_rls(...))
      Rows Removed by Filter: 1500000
->  Hash  (cost=1.00..1.00 rows=100 width=40) (never executed)
      ->  Function Scan on json_array_elements ids  (cost=0.00..1.00 rows=100 width=40) (never executed)

Note that the estimate for the Seq Scan is extremely bad. It assumes most of the table is visible, but RLS will actually dump it.

This might be exacerbated by the poor estimate for the cardinality of ids as the plan above was made with ids := [null]. The cardinality of json_array_elements is always estimated as 100 regardless of input

In V4, the plan is much better. I'm just guessing but this might be because the planner joins on the ID directly, so the cardinality of the join is not obscured by the json_array_elements function. Here is an outline of the plan:

SubPlan 1
  ->  Index Scan using table_pkey on table __local_2__  (cost=... rows=1 width=...)
        Index Cond: (id = __local_1__.table_id)
        Filter: (table_rls(...))

Workarounds

Our workaround right now is to inject comments for the pg_hint_plan extension into the generated SQL, but this needs manual intervention and requires a patched postgraphile. This might be an extremely rare edge case, but I'd like to document it just in case somebody else runs into similar issues.

It should also be possible to adjust the RLS policy to call a function that properly specifies a rows estimate/selectivity, but this requires a custom C extension to define a planner support function. We use AWS RDS and can't do this.

Additional context

I can provide actual table definitions, statistics, and explain plans privately if it would help. Unfortunately our schema is massive and I cannot spare the time coming up with a small reproduction example right now.

I think it should be possible to figure out a reproduction based on just the information above. The key details appear to be:

1. A join which splits into a two queries, with a lateral join on json_array_elements
2. A large table with an RLS function

[maximsmol]

BTW in our case, this deoptimization goes away if we get rid of this check:

crystal/grafast/dataplan-pg/src/steps/pgSelect.ts

Line 1592 in d886231

// Don't want to make this a join as it can result in the order being

Could you elaborate on why this is here? What are the cases where the order might get messed up that are mentioned in this comment?

[maximsmol]

Figured out that this only happens for procedures returning setof. Could you also clarify whether Postgraphile v4 preserved the order in this way?

My understanding is it did not, so it should be safe for us to switch this off in V5 as our old schema cannot be relying on the new strict behavior.

[benjie]

Can you factor the function into the above, seems like it’s an important detail? Also it’s weird that Postgres isn’t applying id= into the lateral join, it should know with ids having a cardinality of 100 that each entry will match at most one row… I assume ID does have a primary key constraint on it?

What version of postgres are you running?

I’m not going to attempt to create a reproduction based on the above, I know from the past this is an exercise in frustration because there’s always a missing piece to the puzzle. Currently I suspect the missing piece is a combination of the definition of your RLS policy and the fact there’s a setof involved somewhere. Are you sure you can’t have an LLM produce an anonymised version of the relevant parts of your schema, populated with generate_series(), that reproduces the issue?

[maximsmol]

I'm gonna try and find the time to make a proper reproduction.

Could you please respond to the questions about the query inlining optimization?
The most important one is whether v4 used to have the equivalent of hasImplicitOrder for setof-returning functions. If it didn't, we're fine just disabling that for ourselves as it means we aren't relying on the order-preserving behavior anyway.

Besides that I think you should just not worry about this until I come back with a repro.

---

What version of postgres are you running?

This is AWS Aurora Postgres-compatible, PostgreSQL 16.8

Can you factor the function into the above, seems like it’s an important detail?

Yes, insofar as it prevents the select step from inlining as a join. I haven't realized it was relevant until after posting the original description.

Also it’s weird that Postgres isn’t applying id= into the lateral join, it should know with ids having a cardinality of 100 that each entry will match at most one row…

I'm not 100% sure what you mean, but I've tried manually rewriting the query in a lot of different ways to get a better plan here, including making a custom json_array_elements that is annotated as rows 1. It always gets a HashJoin, which means it walks the entire giant table running RLS on each row before it even looks at ids.

The only working option was using pg_plan_hint to force NestLoop(__table__ ids)

I assume ID does have a primary key constraint on it?

Yeah, public.table has id as its primary key. You can see in the plan from v4 Postgres correctly guesses that the IndexScan will return a single row per id.

the definition of your RLS policy

It's a lot of code if you include the function definitions, but it's something like this:

create policy gql_consumer_sel on public.table for select to graphql_consumer using (
  coalesce(private.can_view_table(id), false)
  or coalesce(public.can_view_account(created_by), false)
);

The procedures are plpgsql (opaque to the planner) and don't have any rows annotations, thus defaulting to rows 100.

a setof involved somewhere

Yeah, I didn't include it because I did not know it was relevant, but as mentioned the setof causes hasImplicitOrder to be set on this query's parent step. Without it, the query gets inlined as a left join and it looks and performs similar to v4.

It will be in the proper repro when I make it.

[benjie]

For the function implicit order question I’d like to see the GraphQL query and function signature to answer as I’ll need to actually check to answer the question, I don’t want to guess.

Thanks for sharing the policy; as I suspected: you’re committing the cardinal sin of RLS policies and passing row data to functions. This will net you incredibly poor performance and you were simply lucky in V4 that this particular query didn’t trigger it. More details:

https://postgraphile.org/postgraphile/5/required-knowledge#writing-performant-rls-policies

Refactoring your policy to:

create policy gql_consumer_sel on public.table for select to graphql_consumer using (
  id in (select private.visible_table_ids())
  or created_by in (select visible_account_ids())
);

Would massively improve things; but even this isn’t ideal as an “or” is expensive; even better would be:

create policy gql_consumer_sel on public.table for select to graphql_consumer using (
  id in (select private.visible_table_ids())
);

Where visible_table_ids() uses a union:

select id from table where (...conditions...)
union all
select id from table where created_by in (select visible_account_ids())

Here a union is used which is much cheaper than an “or”.

If this function is going to return more than a couple hundred thousand ids it might be worth implementing a more optimal function/policy, but I’d need more details to advise there.

[maximsmol]

For the function implicit order question I’d like to see the GraphQL query and function signature to answer as I’ll need to actually check to answer the question, I don’t want to guess.

OK got it.

committing the cardinal sin of RLS policies

Thank you for pointing this out. I think this would be workable even though I do think we'd feel the trade-off on calculating every accessible ID vs checking a single row.

I think ideally switching from v4 to v5 doesn't suddenly stop us from being simply lucky though. We have a lot of policies and all of them are in the above style, so rewriting everything is kind of impossible. That being said, this is the only query that has serious performance issues in v5 so far, so maybe this is the only thing that needs a rewrite.

---

Anyway, IMO we should focus on the difference between v4 and v5 rather than optimizing any specific RLS policies. I'll get back to you when I do the repro next week.

[maximsmol]

OK I got a repro! https://gist.github.com/maximsmol/c1cec07f1f7a76dba12bb35e5efcd5da

RLS is secondary in this issue, it is not needed to break the inlining, but it does trigger a HashJoin with a SeqScan which means even a 0.01ms function can make large tables unusable.

There are probably other ways to make the second query really slow while keeping the inlined version OK.

Queries and plans comparison

V5:

select
  __tiny_setof__."huge_id"::text as "0"
from "public"."tiny_setof"() as __tiny_setof__;
--
--  Function Scan on tiny_setof __tiny_setof__  (cost=0.25..15.25 rows=1000 width=32) (actual time=0.996..0.997 rows=2.00 loops=1)
--    Buffers: shared hit=161
--  Planning:
--    Buffers: shared hit=6
--  Planning Time: 0.182 ms
--  Execution Time: 1.056 ms
-- (6 rows)

select __huge_table_result__.*
from (select ids.ordinality - 1 as idx, (ids.value->>0)::"int8" as "id0" from json_array_elements($1::json) with ordinality as ids) as __huge_table_identifiers__,
lateral (
  select
    __huge_table__."data"::text as "0",
    __huge_table_identifiers__.idx as "1"
  from "public"."huge_table" as __huge_table__
  where (
    __huge_table__."id" = __huge_table_identifiers__."id0"
  )
) as __huge_table_result__;
--
--  Hash Join  (cost=2.25..267908.83 rows=33 width=40) (actual time=13262.056..13426.945 rows=1.00 loops=1)
--    Hash Cond: (__huge_table__.id = ((ids.value ->> 0))::bigint)
--    Buffers: shared hit=5409
--    ->  Seq Scan on huge_table __huge_table__  (cost=0.00..265406.00 rows=333333 width=16) (actual time=0.171..13370.879 rows=500799.00 loops=1)
--          Filter: can_see_data(data)
--          Rows Removed by Filter: 499201
--          Buffers: shared hit=5409
--    ->  Hash  (cost=1.00..1.00 rows=100 width=40) (actual time=0.036..0.038 rows=1.00 loops=1)
--          Buckets: 1024  Batches: 1  Memory Usage: 9kB
--          ->  Function Scan on json_array_elements ids  (cost=0.00..1.00 rows=100 width=40) (actual time=0.023..0.024 rows=1.00 loops=1)
--  Planning:
--    Buffers: shared hit=354
--  Planning Time: 1.050 ms
--  Execution Time: 13427.012 ms
-- (14 rows)

V4:

with __local_0__ as (
  select to_json(
    (
      json_build_object(
        '__identifiers'::text,
        json_build_array(
          (
            (__local_1__."id")::numeric
          )::text
        ),
        '@huge'::text,
        (
          select json_build_object(
            '__identifiers'::text,
            json_build_array(
              (
                (__local_2__."id")::numeric
              )::text
            ),
            'data'::text,
            ((__local_2__."data"))::text
          ) as object
          from "public"."huge_table" as __local_2__
          where (__local_1__."huge_id" = __local_2__."id") and (TRUE) and (TRUE)
        )
      )
    )
  ) as "@nodes"
  from "public"."tiny_setof"( ) as __local_1__
  where (TRUE) and (TRUE)
),
__local_3__ as (
  select json_agg(
    to_json(__local_0__)
  ) as data
  from __local_0__
)
select coalesce(
  (
    select __local_3__.data
    from __local_3__
  ),
  '[]'::json
) as "data"

 Result  (cost=8740.26..8740.27 rows=1 width=32) (actual time=0.820..0.821 rows=1.00 loops=1)
   Buffers: shared hit=130
   InitPlan 2
     ->  Aggregate  (cost=8740.25..8740.26 rows=1 width=32) (actual time=0.818..0.819 rows=1.00 loops=1)
           Buffers: shared hit=130
           ->  Function Scan on tiny_setof __local_1__  (cost=0.25..10.25 rows=1000 width=16) (actual time=0.547..0.548 rows=2.00 loops=1)
                 Buffers: shared hit=119
           SubPlan 1
             ->  Index Scan using huge_table_id_idx on huge_table __local_2__  (cost=0.42..8.71 rows=1 width=32) (actual time=0.112..0.113 rows=1.00 loops=2)
                   Index Cond: (id = __local_1__.huge_id)
                   Filter: can_see_data(data)
                   Index Searches: 2
                   Buffers: shared hit=11
 Planning:
   Buffers: shared hit=309
 Planning Time: 1.279 ms
 Execution Time: 0.936 ms
(17 rows)

V5, patched to ignore hasImplicitOrder:

select
  __tiny_setof__."huge_id"::text as "0",
  __huge_table__."data"::text as "1"
from "public"."tiny_setof"() as __tiny_setof__
left outer join "public"."huge_table" as __huge_table__
on (
/* WHERE becoming ON */ (
  __huge_table__."id" = __tiny_setof__."huge_id"
));

 Nested Loop Left Join  (cost=0.68..7760.75 rows=1000 width=64) (actual time=0.104..0.128 rows=2.00 loops=1)
   Buffers: shared hit=9
   ->  Function Scan on tiny_setof __tiny_setof__  (cost=0.25..10.25 rows=1000 width=8) (actual time=0.053..0.054 rows=2.00 loops=1)
         Buffers: shared hit=1
   ->  Index Scan using huge_table_id_idx on huge_table __huge_table__  (cost=0.42..7.74 rows=1 width=16) (actual time=0.034..0.034 rows=1.00 loops=2)
         Index Cond: (id = __tiny_setof__.huge_id)
         Filter: can_see_data(data)
         Index Searches: 2
         Buffers: shared hit=8
 Planning Time: 0.177 ms
 Execution Time: 0.161 ms
(11 rows)