>
> 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
>
v2-0001-Refactor-hashed-ScalarArrayOpExpr-evaluation.patch
Description: Binary data
Description: Binary data
