Re: Hash a ScalarArrayOpExpr whose array is fixed for one execution

Hi David, Ayoub,

Thanks for the reviews. Attached is v5. 0001 is unchanged. 0002 has
all the changes below.

David wrote:
> But we could copy it, couldn't we? I'm more looking for a reason like
> performance. As in, if we unified the code, what would happen that we
> don't want to happen? Because we would get rid of a bunch of if-else and
> harder to understand code if also Const arrays went through array_expr.

You are right. In v5 a Const array goes through array_expr too, and
saop_hash_eval_array() is gone. The array is evaluated once, in
per-query memory, and it is no longer copied.

Ayoub wrote:
> +1 to simplifying the code, but we should be careful about hot-path
> overhead. In master, Const arrays are pre-validated at plan time,
> so ExecEvalHashedScalarArrayOp runs without checking for NULL, empty, or
> short arrays on every tuple (aren't those for the whole execution? so
> why check every time?). In v4, having this in the inner loop for every
> row is not insignificant.

Agreed. In v5, a NULL, empty or short array is handled behind one
check per row: is there a hash table? The result for a NULL scalar
depends only on the array, so it is worked out once, on the first
row. So a row makes no more checks than on master.

Looking up a value in a Const list is now faster than on master. The
step that loaded the Const array on every row is gone. The hashed step
itself also runs fewer instructions per row (callgrind, 10 items): 113
instead of 122 for a match, and 118 instead of 124 for no match.

David wrote:
> Ah, this is because raw_expression_tree_walker_impl() skips T_WhenExpr
> and directly recurses into its contents. You could add the case with a
> comment to be on the safe side, if the code ever gets changed.

Done.

> I thought that part below from v1 would be good to preserve in the
> commit message:

Done, with small fixes. NOT IN is hashed too since PG 15
(29f45e299e7), so I dropped "with useOr". I added casts to the list
of nodes. I wrote "psycopg 3", because psycopg 2 puts the values into
the query text on the client. I dropped the MySQL/MariaDB sentence,
because their manuals describe the binary search only for lists of
constants.

> I think you can go ahead and open a commit fest entry.

It already exists:
https://www.google.com/url?q=https://commitfest.postgresql.org/patch/7285/&source=gmail&ust=1793649679948000&sa=E
Please add yourself as a reviewer there, if you like.

Ayoub wrote:
> AI suggests also NamedArtExpr and CollateExpr, i think they are safe as
> well to allow.

Added both. They change nothing today: eval_const_expressions() runs
before our walker. It puts named arguments in position and turns a
CollateExpr into a RelabelType, so these queries are already hashed.
The two cases are only there in case that changes.

> While it is true that val <> ALL(array) == NOT(val = ANY (array)) (in
> Logic), however for user defined types and operators that are not
> strict, comparing NULL with a value can return false for both = and <> ...
> So this makes the equivalence in that case not always true. (Attached is
> a reprod of the bug)

Thanks for the reproducer. The root cause is the operators in your
test: the <> is not a valid negator of the =. The documentation [1]
requires "(x A y) equals NOT (x B y) for all possible inputs x, y", but
for a NULL input both return false. So NOT IN does not work well with
them even on master. The same question gets different answers,
depending on the length of the list:

SELECT v <> ALL (ARRAY[1,2,3,4,5,6,7,8,9]::my_int[])
FROM (SELECT NULL::my_int AS v OFFSET 0) s; -- t (9 items)

SELECT v <> ALL (ARRAY[1,2]::my_int[])
FROM (SELECT NULL::my_int AS v OFFSET 0) s; -- f (2 items)

The reason: a list of 9 or more items is hashed. A hashed NOT IN looks
for an equal item, so it calls = and inverts the result (since PG 15,
29f45e299e7). A shorter list is searched linearly, and that calls <>.
The two ways agree only if <> is the negator of =.

v5 hashes $1 too, so the example in your test now gets the hashed
answer.

Master's code for a hashed NOT IN depends on <> being the negator of =.
So does the recent fix for non-strict operators [2]. So I chose not
to fix it for now.

[1] https://www.google.com/url?q=https://www.postgresql.org/docs/current/xoper-optimization.html%23XOPER-NEGATOR&source=gmail&ust=1793649679948000&sa=E
[2] https://www.google.com/url?q=https://postgr.es/m/A16187AE-2359-4265-9F5E-71D015EC2B2D@outlook.com&source=gmail&ust=1793649679948000&sa=E

> We should be cautious about charging an O(1) per-tuple cost during
> generic planning when the array length is unknown, given that the
> executor can unilaterally decide to abandon hashing and execute an O(N)
> linear scan instead.

Agreed, fixed. An array of unknown length, such as ANY($1), is now
costed as a linear search, as on master. So your large_bench case gets
the same plan and costs as on master. Only a Const or an ARRAY[...]
with at least 9 items is costed as hashed. The planner knows their
length, so they are hashed at run time. This replaces my earlier
proposal to David, to leave the costing as it was.

I tested the plan choice on a 1M-row table with master and v5, and
timed each scan type. ANY($1) gets the same plans as master.
IN ($1, ..., $N) with N = 1000 changed from an index scan to a bitmap
scan in three of 31 cases. Two got faster (1.5x and 2.9x). One got
2.5 ms slower, but with random_page_cost = 1.1 v5 picks the faster
plan. The plan cache now picks the generic plan for such IN lists more
often, and it was 2-40% faster.

I also tested v5 against master: the regression suites with generic
plans, forced parallel workers and JIT; a random comparison over 20
data types; Valgrind; and a build that checks every hashed result
against the linear search. No differences.

Any further advice or corrections would be much appreciated.

Regards,
Linden

On Sat, Oct 31, 2026 at 6:56 AM Ayoub Kazar <ayoub(dot)kazar(at)data-bene(dot)io> wrote:
>
> Hello Linden, David,
>
> On 29/10/2026 10:46, David Geier wrote:
>
> A comment saying why we cannot unify the Const and non-Const case in
> execExprInterp.c would be useful. One could think that it might be a
> good idea to now always go the non-Const route for code simplicity /
> consistency.
>
> Done, above saop_hash_eval_array(). The non-Const route copies the
> array, and a Const array needs no copy, because it is part of the plan.
>
> But we could copy it, couldn't we? I'm more looking for a reason like
> performance. As in, if we unified the code, what would happen that we
> don't want to happen? Because we would get rid of a bunch of if-else and
> harder to understand code if also Const arrays went through array_expr.
>
> +1 to simplifying the code, but we should be careful about hot-path overhead. In master, Const arrays are pre-validated at plan time, so ExecEvalHashedScalarArrayOp runs without checking for NULL, empty, or short arrays on every tuple (aren't those for the whole execution? so why check every time?). In v4, having this in the inner loop for every row is not insignificant.
>
> Doesn't saop_array_may_vary_walker() misses T_CaseWhen? T_CaseExpr's
> args is a list of CaseWhen nodes. When recursing it doesn't match
> against T_CaseWhen and returns true while CaseWhen doesn't vary. I think
> that would only occur in this form:
>
> x = ANY(CASE WHEN $2 THEN $1 ELSE '{...}' END
>
> This form is hashed. The walker never gets a CaseWhen node, so
> T_CaseWhen is not needed. I went through expression_tree_walker() and
> ran a test to confirm this.
>
> Ah, this is because raw_expression_tree_walker_impl() skips T_WhenExpr
> and directly recurses into its contents. You could add the case with a
> comment to be on the safe side, if the code ever gets changed.
>
> AI suggests also NamedArtExpr and CollateExpr, i think they are safe as well to allow.
>
>
> Other findings:
> While it is true that val <> ALL(array) == NOT(val = ANY (array)) (in Logic), however for user defined types and operators that are not strict, comparing NULL with a value can return false for both = and <> ...
> So this makes the equivalence in that case not always true. (Attached is a reprod of the bug)
>
>
>
> >> Open question
> >> ------------
> >> cost_qual_eval charges the hashed cost for an opaque stable array using
> >> estimate_array_length()'s default guess, which slightly over-estimates
> >> startup for an array that turns out short at run time. I have left that
> >> for a follow-up; happy to fold in a fix if reviewers prefer.
> > What are your ideas for improving on that? You cannot know the runtime
> > array length at planning time.
> We should be cautious about charging an O(1) per-tuple cost during generic planning when the array length is unknown, given that the executor can unilaterally decide to abandon hashing and execute an O(N) linear scan instead.
>
> Here's a case:
>
> CREATE TABLE large_bench (id bigint, cat int, val text);
> INSERT INTO large_bench SELECT g, (g / 100) % 11, repeat('x', 100) FROM generate_series(1, 5000000) g;
> CREATE INDEX idx_large_bench_cat ON large_bench(cat);
> ANALYZE large_bench;
> PREPARE p_query(int[]) AS SELECT * FROM large_bench WHERE cat = ANY($1);
> SET plan_cache_mode = force_generic_plan;
>
> Optimizer Costs:
> Master: Bitmap Index Scan (187,282) < Seq Scan (203,410)
> Patched v4: Seq Scan (165,910) < Bitmap Index Scan (187,282) (because of the cheap cost per tuple)
>
> test executing with ARRAY[1, 2]:
> Cold Cache:
> Patched Seq Scan: 1,519 ms (reads 168k buffer pages, filters 4.09M rows)
> Unpatched Index Scan: 129 ms (reads 24k buffer pages)
> Impact: 11.7x slowdown
> Warm Cache (5-run average):
> Patched Seq Scan: 233.8 ms (touches all 90,910 table blocks)
> Unpatched Index Scan: 84.1 ms (touches only 22,730 blocks)
> Impact: 2.8x slowdown and 4x more buffer I/O
>
> I think costing both cases (array length known or unknown) as unhashed linear scans isn't a bad idea maybe, i admit i haven't thought a lot about it yet.
>
> Regards,
> Ayoub