Hi David, Attached is v3. I have reviewed every line of it myself, changed it where needed, and tested it. Please review v3 instead of v2.
My answers to your questions in my last mail are still valid. The
performance numbers there are also still valid.
0001 only refactors, with no behavior change. 0002 is the feature and
its tests. Both apply cleanly to today's master.
Some code in 0002 may be hard to understand, because it handles rare
cases. For your reference, here is a brief explanation. I hope it
makes your review easier. Line numbers are in the v3-0002 patch file.
1. Line 113, use_hashed_step in ExecInitExprRec(): the hashed step
reads a non-Const array only once. That is wrong in a PL/pgSQL
simple expression, which is reused with new parameter values, and
in JSON ON ERROR or ON EMPTY, where errors must be caught. So these
cases use the plain step.
2. Line 129, negfuncid in ExecInitExprRec(): a hashed NOT IN looks
values up with "=" (negfuncid). The plain step must use the
operator itself, "<>".
3. Line 379, ExecEvalHashedScalarArrayOp(): on master, this step only
gets a Const array that the planner has checked: not NULL, and with
at least 9 elements. A non-Const array is only known at run time,
so it can be NULL, empty or short. These lines handle that the
same way as ExecEvalScalarArrayOp(), in the same order, so
NULL = ANY ('{}') still gives false.
4. Line 578, saop_array_may_vary_walker(): only arrays built from
Consts, external Params and the node types listed in the switch are
hashed. Anything else is rejected, including rare nodes that change
from row to row: merge_action(), OLD/NEW in RETURNING, and
set-returning functions. Vars of any level are rejected too,
because outer references are not yet Params here.
The full test suite passes, for 0001 alone and for both patches. I
also compared about 48,000 random queries with unpatched master, and
found no differences.
Any comments are very welcome.
Regards,
Linden
On Sun, Oct 11, 2026 11:36 AM, best xmg <[email protected]> wrote:
>>
>> 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
v3-0001-Refactor-hashed-ScalarArrayOpExpr-evaluation.patch
Description: Binary data
v3-0002-Hash-a-ScalarArrayOpExpr-whose-array-is-fixed-for.patch
Description: Binary data
