Re: Hash a ScalarArrayOpExpr whose array is fixed for one execution - Mailing list pgsql-hackers

Hi David,

Thanks for the comprehensive review.  It was very informative.

Attached is v2, split as you suggested (details below).

Please note that v2 was generated with Claude Code, so please don't
commit it yet.  I'm busy preparing for my exams, and I will finish
reviewing it line by line within two weeks.  In the meantime, I have
had an AI model check it many times to keep the number of bugs as low
as possible.

v2 also fixes these bugs in v1, each with a regression test now:

- In a PL/pgSQL simple expression, NOT IN / <> ALL compared with "="
  instead of "<>": v1 searched linearly there but kept the operator
  that hashed NOT IN uses.
- Some arrays that change from row to row were hashed once: arrays
  containing merge_action(), a set-returning function, or RETURNING
  OLD/NEW of a view column.  0002 now accepts only node types known to
  be fixed (an allowlist), so any other node is never hashed.
- A NULL scalar with an empty array returned NULL instead of false
  (true for NOT IN).
- In a JSON DEFAULT ... ON ERROR expression, an error in the array was
  not handled softly.  0002 doesn't hash there.

I also ran the whole test suite with a debug build that checks every
hashed result against a linear search, and compared about 60,000
random query executions with master.  Neither found anything else.

> That's indeed a pretty severe limitation that would be great to remove:
> Today, anything that doesn't use the database in the most
> straightforward doesn't profit from hashed IN.

Let me first make the scope precise, because my first mail described it
badly.

A prepared statement can run with two kinds of plan.  A custom plan is
built for each execution with the actual parameter values, so
"col = ANY ($1)" becomes "col = ANY ('{...}')", a Const, which the
existing PG 14 code hashes.  A generic plan is built once without values
and then reused, so the array stays a Param, which master searches
linearly for every row.  The generic plan saves planning time on every
execution, while a custom plan can be better because it sees the
values.

So the problem is specific to generic plans, plus arrays the planner can
never fold, such as the result of a stable function.  The table shows
whether the array is hashed (hash) or searched linearly (scan), with
12 elements unless noted.  "cust." is a custom plan, "gen." a generic
plan:

  master        patched
  cust.  gen.   cust.  gen.    query form

  Literal lists
  hash   hash   hash   hash    v IN (1, ..., 12)
  scan   scan   scan   scan    v IN (1, ..., 8)

  Parameters
  hash   scan   hash   hash    v = ANY ($1)
  hash   scan   hash   hash    v IN ($1, ..., $12)
  hash   scan   hash   hash    v IN ($1, 2, ..., 12)
  hash   scan   hash   hash    v = ANY ($1::int[])
  hash   scan   hash   hash    v = ANY (string_to_array($1, ','))
  scan   scan   scan   scan    v IN ($1, ..., $8)
  scan   scan   scan   scan    v = ANY ($1), only 5 elements
  hash   scan   hash   hash    SELECT v = ANY ($1) FROM t

  Stable and volatile functions
  scan   scan   hash   hash    v = ANY (stable_fn($1))
  scan   scan   hash   hash    v = ANY (current_setting('x')::int[])
  scan   scan   scan   scan    v = ANY (volatile_fn($1))

  NOT IN and other operators
  hash   scan   hash   hash    v NOT IN ($1, ..., $12)
  hash   scan   hash   hash    v <> ALL ($1)
  scan   scan   scan   scan    v < ANY ($1)  (no hash function)

  Arrays that change per row or group
  scan   scan   scan   scan    v = ANY (arr)  (arr is a column)
  scan   scan   scan   scan    v = ANY (ARRAY[v, v + 1, ...])
  scan   scan   scan   scan    HAVING 5 = ANY (array_agg(v))
  scan   scan   scan   scan    v = ANY (array_agg(v) OVER (...))
  scan   scan   scan   scan    v = ANY (ARRAY(SELECT ...))
  scan   scan   scan   scan    LATERAL: t.v = ANY (a.arr)

This matters in practice.  pgJDBC (after prepareThreshold), pgx,
asyncpg, psycopg 3 and PL/pgSQL all reuse prepared statements, and by
default PostgreSQL switches to the generic plan at the 6th execution if
it looks cheaper.  With a long list it often does, because the planner
assumes a $1 array has 10 elements.  For example, a 1M-row table
filtered by a 1000-element list and joined to a second table (release
build, default settings, medians of 5 runs):

  master:       custom plan 33 ms, generic plan 972 ms
  patched (v2): custom plan 31 ms, generic plan  30 ms

I also tried fixing this in choose_custom_plan(), by preferring a
custom plan when the generic plan would search a long parameter array.
That helps only in auto mode, not with force_generic_plan or for stable
expressions, and it re-plans every execution, so I think the executor
fix is better.

> one-off custom plan folds it to a Const and is fine -- which is
> why the slowdown tends to appear only after a statement has run a few
> times.  The PG 14 thread named the non-Const case as future work,
> deferred "from fear that we may slow down cases where the expression is
> evaluated only once".
>
> Why would that be? This "problem" also exists for the const case,
> doesn't it?

You're right, and my quote was misleading: building the hash table
for a single evaluation costs about the same for Const and non-Const
arrays (the measurements below show this).  In fact, the original
thread wanted this: Heikki suggested applying the optimization to
non-Const expressions and wrote "it would be nice to handle queries
like "WHERE column = ANY ($1)"" [1].

> We could make the choice of using the hashed SAOP or not depend on the
> estimated number of rows. But given that we don't do anything like that
> for the const case, I'm thinking we should do the same for the non-const
> case.

Agreed, I'll keep it consistent with the Const case.

> The patch is relatively big. How about splitting out the refactorings
> (replacing finfo with fcinfo->flinfo, moving
> MINARRAY_SIZE_FOR_HASHED_SAOP, caching typlen, etc. and the comment
> updates).

Done in v2:

- 0001 only refactors, with no behaviour change: finfo is replaced by
  fcinfo->flinfo, MIN_ARRAY_SIZE_FOR_HASHED_SAOP moves to primnodes.h,
  and the code that builds the hash table moves unchanged into a new
  function, saop_build_hashtable(), so that 0002 calls it instead of
  re-indenting it.
- 0002 is the feature and its tests.

Caching typlen stayed in 0002, because only the new short-array linear
path reads it; in 0001 it would be dead code.  I also dropped comment
rewording from v1 that the feature didn't need.

> Why does "patched" get faster with increasing N (57 ms for N=6 and 51 ms
> for N=51)?

The N=6 row is below MIN_ARRAY_SIZE_FOR_HASHED_SAOP (9), so it is a
linear search in both builds.  From N=9 on, patched uses the hash table
and stays flat; the 50-52 ms differences are noise.  Building the hash
table itself is cheap: about 0.6 us for 51 elements, the largest list
in your table, and 10 us for 1000, far too little to explain
differences of milliseconds.

> Do you have a table like the above for that variant?

Yes.  "SELECT count(*) FROM t WHERE v IN ($1, ..., $N)" on a 1M-row
table, generic plan, no parallel workers, each value matching one row
(release build, medians of 7 runs):

  N = 6:     master 154 ms,  patched 155 ms
  N = 9:     master 190 ms,  patched 52 ms
  N = 16:    master 250 ms,  patched 49 ms
  N = 64:    master 632 ms,  patched 50 ms
  N = 256:   master 2078 ms, patched 51 ms
  N = 1000:  master 7734 ms, patched 50 ms

> Maybe you can collect numbers for that case as well and show that the
> maximum slowdown is not bigger than what we accepted previously.

Here is the cost of a statement that uses the array only once, in
microseconds (generic plan, medians of 3 runs), with x the first
element of the array, the best case for a linear search:

- "literal": x = ANY ('{...}') on master, which master already hashes,
  so this is the cost accepted in PG 14
- "$1 linear": x = ANY ($1) on master, not hashed
- "$1 hashed": x = ANY ($1) with the patch

  N = 9:      literal 2.8,    $1 linear 2.8,  $1 hashed 3.0
  N = 100:    literal 5.1,    $1 linear 2.8,  $1 hashed 4.8
  N = 1000:   literal 12.9,   $1 linear 3.0,  $1 hashed 14.0
  N = 10000:  literal 159.2,  $1 linear 5.1,  $1 hashed 171.3

"$1 hashed" costs a little more than "literal": unlike a Const array,
a $1 array is not stored in the plan, so the patch copies it once
before building the hash table.  The worst case is therefore only
slightly above the one accepted for Const arrays in PG 14.

> What are your ideas for improving on that? You cannot know the runtime
> array length at planning time.

Agreed, not in general.  For IN ($1, ..., $N) the length is already
known at plan time, because it is an ArrayExpr, so only a bare Param or
a function result falls back to estimate_array_length()'s default of 10.
I propose to leave the costing as it is and document that, unless you
see a better option.

Just a kind reminder: I haven't reviewed v2 line by line myself yet.
Feedback and suggestions are very welcome, and I will respond to them,
together with v3, in about two weeks, after my exams.

[1] https://www.postgresql.org/message-id/557e8853-7cb8-9c01-6193-1d4109345401%40iki.fi

Regards,
Linden