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

Hi Linden!

> Since PG 14 (50e17ad281) the executor can evaluate "col = ANY (array)"
> with a hash table instead of a linear scan, but only when the array is a
> Const. Every parameterised form stays on the O(rows * N) path:
>
> col = ANY ($1) -- Param, generic/cached plan
> col IN ($1, ..., $N) -- ArrayExpr of Params
> col = ANY ($1::int[]) -- ArrayCoerceExpr
> col = ANY (string_to_array($1, ',')) -- FuncExpr
>
> These are what drivers emit (JDBC setArray, psycopg "= ANY(%s)", asyncpg)
> and what anything that expands an IN list into bind placeholders produces.
> With a cached generic plan the list arrives as a Param and is never
> hashed;

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.

> 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? If we evaluate the IN only once, then it's always cheaper to
iterate over it instead of first creating a hash map. Or what am I missing?

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.

> The attached patch does that. It hashes any array argument the planner
> can prove is fixed for the whole execution: no Vars, no volatile
> functions, no aggregate/grouping/window functions, no sub-selects, and no
> Params other than PARAM_EXTERN. For such an array the executor compiles
> it as an independent sub-expression, evaluates it once on the first row,
> builds the hash table, and reuses it. MIN_ARRAY_SIZE_FOR_HASHED_SAOP is
> still enforced, now against the run-time element count; a shorter array
> falls back to the existing linear ExecEvalArrayCompareInternal(). A
> standalone ExprState (a PL/pgSQL "simple expression", reused across calls
> with different parameters) keeps the linear path -- the "one execution"
> proof needs an execution boundary it does not have.
>
> Not covered, because the array is not fixed for the execution: a Var (new
> array per row), a volatile function (per-row by definition), an
> aggregate/grouping/window value (per group/frame/row, and only evaluable
> inside its owning node), a sub-select, or a PARAM_EXEC (correlated /
> nestloop-inner). These stay linear.
>
> Diffstat: 5 backend files, ~360 lines, plus regression tests; no new GUC,
> syntax, or catalog change (as 50e17ad281).

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). That would reduce the noise in the other patches and make them
somewhat easier to review.

> Performance
> -----------
> Release build, no LLVM, generic plan forced, warm cache, one Ryzen 7
> 4800H laptop. Seq scan, "SELECT count(*) FROM t WHERE v = ANY($1)",
> 1,000,000 rows, median of 9:
>
> N master patched
> 6 59 ms 57 ms (below threshold: linear both)
> 9 65 ms 50 ms
> 40 150 ms 52 ms
> 100 297 ms 52 ms
> 1000 2494 ms 51 ms

Nice!

Why does "patched" get faster with increasing N (57 ms for N=6 and 51 ms
for N=51)? It needs to create a much bigger hash map for N=51 than for
N=6. That shouldn't take very long but if anything, it shouldn't make
the query run faster.

> Patched is flat in N once hashed. "IN ($1,...,$N)": 3.6x at N=9, 12x at
> N=60. No change on paths that stay linear (N < 9, literal IN, pgbench).

That means the speedup is even greater for the IN($1, ..., $N) case
because in that case for every parameter extra work is spent non-hashed
variant? Do you have a table like the above for that variant?

> Single evaluation -- the PG 14 concern. Plan built and run once, fresh
> connection:
>
> rows N master patched
> 1 40 0.025 ms 0.028 ms
> 1 200 0.023 ms 0.035 ms (+12 us, worst seen)
> 1000 100 0.316 ms 0.085 ms
>
> Break-even is around 10 rows; worst case is +12 us to build a 200-entry
> hash for a one-row scan.

That seems reasonable and should be the same for the const case that
works today already. Maybe you can collect numbers for that case as well
and show that the maximum slowdown is not bigger than what we accepted
previously.

> 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.

--
David Geier