Re: Optimize mergejoinscansel() by avoiding redundant computations

Hi hackers,

Attached is v4. Compared with v3, it takes a simpler approach. v3
traced Vars through subqueries and CTEs (is_same_simple_base_var())
and reused intermediate results step by step. v4 calls
examine_variable() on both inputs as before and compares what it
returns. v4 also adds an assert-only cross-check, and the numbers
below come from release builds and include EXPLAIN planning time.

What the patch does
-------------------

When both inputs of a merge clause are the same column (or
expression) of the same relation, as in self-joins or joins against
pulled-up subqueries and views, every get_variable_range() and
scalarineqsel() call in mergejoinscansel() gets identical inputs for
the two sides. The existing "exactly equal estimates" rules then
discard the results, so the answer is always the default (start =
0.0, end = 1.0, plus stanullfrac for nulls-first). Getting there can
be costly, since scalarineqsel() may probe an index through
get_actual_variable_range().

The new mergejoin_vardata_equivalent() detects this case after
examine_variable(), and mergejoinscansel() then returns the same
answer without doing that work. Calls per merge clause when the
inputs are equivalent:

master v4
examine_variable() 2 2
get_variable_range() 2 0 (1 for nulls-first)
scalarineqsel() 4 0

The inputs are treated as equivalent only if:

- they use the same statistics tuple (same pointer);
- vartype and acl_ok are equal;
- both are plain relations with the same relid and inh flag;
- for Vars, varattno is equal and varnullingrels is empty on both
sides or nonempty on both (match_index_to_operand() only checks
emptiness);
- for other expressions, they are equal() after mapping one varno to
the other.

The operator must also not be cross-type. The pointer test errs on
the safe side: unequal pointers (e.g. copies from a stats hook or
extended statistics) only mean the shortcut is not taken.

For nulls-first, master adds stanullfrac only if get_variable_range()
succeeds. To keep that behavior, the shortcut calls it once with NULL
min/max, which get_variable_range() now accepts and which only checks
whether a range is available.

The equivalence rules depend on what scalarineqsel() and
get_variable_range() look at, so they could drift if those functions
change. To catch that, the body of mergejoinscansel() moves to
mergejoinscansel_internal(), and in assert-enabled builds the full
computation is repeated whenever the shortcut is taken, with an
Assert that both give the same results. This follows the pattern of
verify_compact_attribute() and have_unsafe_outer_join_ref(). Release
builds do not contain this code.

Correctness
-----------

- 29 merge join cases (test.sql in the attachment) give identical
EXPLAIN output, plans and costs included, on master and v4.
- With assertions enabled, the regression suite (setup, regress)
passes and the cross-check never fires.
- To make sure the cross-check works, I injected a bug (adding
stanullfrac without checking get_variable_range()); the RLS case
with a non-leakproof operator then failed the Assert.
- On a release build, meson test including TAP passed everything it
ran: regress, isolation, ecpg, postgres_fdw, test_decoding,
pg_upgrade, recovery (59) and subscription (39). I stopped the run
after 409 of 422 tests, with no failures (365 ok, 40 skipped,
4 interrupted by the stop, 13 not run).

Performance
-----------

Release build (-O3, cassert=false), Intel i7-5500U, 4 cores, 15 GB,
WSL1, default statistics target. Each version is built twice: once
with temporary timing code around mergejoinscansel(), and once
without it, which is used for planning time. All four builds share
one instance and one set of statistics. Values are means after
dropping the minimum and maximum. The three columns are three
separate runs on an idle machine; their summaries are in the
attachment (results/runN/summary.txt).

Scenario 1: cold connections. The 29 cases run once per server
start, 12 starts per version, master and v4 alternating.

run 1 run 2 run 3
planning time, shortcut taken (18) -12.7% -12.8% -12.5%
planning time, shortcut not taken (10) +6.1% +11.7% +9.1%
same, without case 17 (9) -0.3% +3.9% +4.1%

Most of the increase in the second row comes from case 17, which
takes about 0.3 ms longer on v4 (0.27-0.37 ms in the three runs). On
a cold connection, master warms the catalog cache and the index of
column c while planning cases 3-5. v4 skips that work there, so the
first index probe moves to case 17, the next query that needs it.
Without case 17 the group changes by -0.3% to +4.1%, about 0.01 ms
per statement, which is within the run-to-run scatter of single cases
(up to +/-13%). This explanation is inferred from the per-case
numbers; I have not verified it separately. Scenario 2 below shows
no change for these cases in steady state. (In summary.txt these
rows are "fast", "slow" and "slow-17" under "Scenario 1 summary".)

Scenario 2: steady state. Each case runs 128 times in one session.

run 1 run 2 run 3
mergejoinscansel(), shortcut (18) -95.9% -95.9% -95.7%
mergejoinscansel(), no shortcut (10) -4.4% -6.1% +1.0%
planning time, shortcut (18) -22.2% -18.6% -21.3%
planning time, no shortcut (10) -0.7% +4.5% +0.5%

When the shortcut applies, planning time goes from about 0.245 ms to
about 0.195 ms per statement, which matches the time saved in
mergejoinscansel() itself. When it does not apply,
mergejoinscansel() takes about 0.013 ms on both master and v4, and
both rows change sign from run to run, i.e. the extra equivalence
check is lost in the noise. (In summary.txt these rows are
"slow+fast" and "slow+slow" under "Scenario 2 summary".)

In short: estimates are unchanged; when the shortcut applies,
mergejoinscansel() is about 96% faster and planning time for simple
queries drops by about 20% in steady state and about 13% on cold
connections; other queries show no measurable change.

Reproducing the numbers
-----------------------

mergejoinscansel-perf.tar.gz contains the scripts (perf/scripts) and
the summaries of the three runs above (perf/results/run1..3, each
with summary.txt and env.txt). It needs a Linux machine with git,
meson, ninja, python3 and stdbuf. Start from a clean master checkout
that the patch applies to.

# paths; adjust to your setup
P=/path/to/perf # extracted from the tarball
SRCDIR=/path/to/postgresql # clean master checkout
BUILD=/path/to/build_release
PATCH=/path/to/v4-0001-Skip-redundant-work-in-mergejoinscansel-for-equiv.patch
SRC=$SRCDIR/src/backend/utils/adt/selfuncs.c

# 0. release build directory, assertions off
meson setup $BUILD $SRCDIR --prefix=/tmp/pg-perf-prefix \
-Dbuildtype=release -Dcassert=false

# 1. generate four selfuncs.c variants: master and v4, each with
# and without the timing wrapper
cp $SRC /tmp/master.c
git -C $SRCDIR apply $PATCH
cp $SRC /tmp/v4.c
mkdir -p $P/bin/src
python3 -I $P/scripts/make_variants.py /tmp/master.c /tmp/v4.c $P/bin/src

# 2. build and install each variant under $P/bin/<variant>
# (this overwrites selfuncs.c in the tree; it is restored to v4)
for v in master_notiming master_timing v4_notiming v4_timing; do
cp $P/bin/src/$v.c $SRC
ninja -C $BUILD || break
rm -rf $P/bin/$v
DESTDIR=$P/bin/$v meson install -C $BUILD --no-rebuild --quiet || break
done
cp /tmp/v4.c $SRC

# 3. run both scenarios (about 5 minutes). The first run creates a
# test instance in $P/data (port 54330, socket in /tmp; override
# with PORT and SOCKDIR) and loads it with init.sql; later runs
# reuse it, so all results share the same statistics.
cd $P && ROUNDS=2 S1REP=12 SLEEP=5 BUILD=$BUILD ./scripts/run_all.sh
grep ERROR results/run.log # should print nothing

# 4. summarize into results/summary.txt
python3 -I scripts/summarize.py

Before rerunning, move away master/, v4/ and results/; summarize.py
reads every output file it finds there.

Attachments
-----------

- v4-0001-Skip-redundant-work-in-mergejoinscansel-for-equiv.patch
- mergejoinscansel-perf.tar.gz

Comments and reviews are welcome.

regards,
--
ZizhuanLiu (X-MAN) 
44973863(at)qq(dot)com