Planning-time measurement methodology
=====================================

This describes exactly how the planning-time numbers for the jointree-based
join removal patch were produced, so that others can reproduce them or explain
divergent results.  Scripts are at the end.

Since several people are reporting worse numbers than the single figure I
quoted earlier for the multi-self-join case, the short answer is at the top:
the regression is quadratic in the number of removable self joins, so any
single-point measurement understates it, and mine (an 8-way self join) was
close to the best case.  See "Results" below.


Machine and build
-----------------

  aarch64 (Apple silicon), 10 cores, 3 GB RAM, Linux 7.0.0-28-generic.
  meson buildtype=release, so -O3.  debug=false, cassert=false.
    meson setup build-opt --buildtype=release -Dcassert=false
  Both trees installed to separate prefixes with
    meson install -C build-opt --destdir=<prefix>
  and measured with their own binaries against their own data directory.

Baseline is the commit the branch forked from, not "master as of today", so
that unrelated commits cannot leak into the comparison.

An aarch64 VM with 3 GB is not an ideal benchmarking host.  Absolute numbers
here should not be compared against numbers from other machines; only the
base/patched ratios on the same host mean anything.


Cluster configuration
---------------------

  initdb -N --locale=C --encoding=UTF8
  postgres -c shared_buffers=128MB -c fsync=off

Everything else is default, including max_parallel_workers_per_gather.
Parallel path generation is a real part of planning, so it is left on.

Per session, four settings are pinned:

  set geqo = off;
  set join_collapse_limit = 100;
  set from_collapse_limit = 100;
  set jit = off;

The first two are not optional.  With geqo left on, any case above
geqo_threshold (12) plans by randomized search, and the resulting numbers are
noise rather than measurement.  With the collapse limits at their defaults of
8, query shapes above 8 relations stop being flattened, so the N-way series
measures two different things on either side of N=8 and the curve has a knee
that has nothing to do with the patch.  Anyone comparing results should state
what they used for these.


What is being timed
-------------------

The "Planning Time" line from

  EXPLAIN (COSTS OFF, SUMMARY ON) <query>;

SUMMARY has to be given explicitly: it defaults on only for EXPLAIN ANALYZE.

This number brackets pg_plan_query() alone.  It excludes parse analysis and
rewriting, which is what we want, and it also excludes the executor entirely,
so the tables can stay small without biasing anything.  Resolution is 1
microsecond (three decimal places in ms), which matters: at N=2 the whole
measurement is 4 to 8 ticks wide, so the small-N rows below carry no useful
precision.  The N>=8 rows are the trustworthy ones.

Statements are sent as simple queries from a psql script, so each iteration
does a full parse and plan.  No prepared statements, hence no plan caching.


Repetition and statistic
------------------------

Per case: one warmup iteration, then 200 measured iterations, all in a single
psql session driven from one script file.  Reported statistics are the minimum
and the median over the 200; the p90 is also collected as a noise indicator.

Minimum is the primary statistic.  The work is CPU-bound with no I/O and no
lock contention, so the distribution is a hard floor plus scheduler noise, and
the floor is the quantity of interest.  The median is reported alongside
because a min that moves while the median does not usually means the run was
disturbed.  In this data the two agree closely, which is the main evidence
that the run was clean.

Repeatability: I have two independent patched runs of the full matrix.  Their
minima differ by 3 to 8 percent at the larger sizes.  So a ratio of 1.1x on
this host is not distinguishable from noise; 2.4x is.


Cases
-----

All against a narrow table, three columns, 1000 rows, primary key on "a",
VACUUM ANALYZEd:

  CREATE TABLE sj (a int primary key, b int, c text);

  selfjoin   N-way self join on the unique column; N-1 rels removable by
             self-join elimination.
               select t1.b from sj t1 join sj t2 on t1.a = t2.a ...
  leftjoin   N-1 removable left joins (unique inner, no inner column used).
               select t1.b from sj t1 left join sj t2 on t1.a = t2.a ...
  semijoin   N-1 semijoins with unique inner rels, reducible to inner joins.
               select t1.b from sj t1
               where exists (select 1 from sj s2 where s2.a = t1.a) and ...
  innerjoin  Control: N-way join over N distinct tables, nothing removable.
             This one must be capped at N=8, see "Traps".

Table width is a parameter I did not vary and should have.  Several of the
per-pass costs (build_base_rel_tlists, the attr_needed bookkeeping) scale with
the number of columns, so a wide table will make the regression worse than
what is shown here.  Anyone seeing much larger numbers than mine should say
how wide their tables are.


Traps that will corrupt the numbers
-----------------------------------

Two of these cost me a run before I noticed.

1. The no-removal control cannot be extended to large N.  With geqo off and
   the collapse limits raised, an exhaustive 16-way join search on this host
   was killed by the OOM killer; the crash then poisoned the next case in the
   sequence, which reported an implausibly fast result because it had actually
   failed to connect during crash recovery.  The control is capped at N=8
   (already 4.4 ms, dominated by path generation rather than by anything this
   patch touches), and the postmaster now runs under
   "ulimit -v 4194304" so a runaway dies alone.

2. Check the server log after every run.  A case that silently produces no
   rows shows up as a fast outlier, not as an error.  The harness prints ERR
   rather than a number when it gets no Planning Time lines, which is what
   caught the above.

3. Do not leave a postmaster running on the data directory between runs from
   an interactive debugging session; pg_ctl will refuse to start and the
   harness will report an empty result set.


Results
-------

Minimum planning time in ms over 200 iterations, and the patched/base ratio.

  selfjoin      base   patched   ratio        leftjoin    base  patched  ratio
    N=2       0.0040    0.0040    1.00          N=2      0.0050  0.0050   1.00
    N=3       0.0070    0.0080    1.14          N=3      0.0060  0.0070   1.17
    N=4       0.0100    0.0120    1.20          N=4      0.0070  0.0080   1.14
    N=5       0.0110    0.0160    1.45          N=5      0.0100  0.0100   1.00
    N=6       0.0130    0.0220    1.69          N=6      0.0120  0.0110   0.92
    N=8       0.0190    0.0330    1.74          N=8      0.0160  0.0140   0.88
    N=10      0.0280    0.0510    1.82          N=10     0.0200  0.0180   0.90
    N=12      0.0330    0.0660    2.00          N=12     0.0230  0.0210   0.91
    N=16      0.0470    0.1050    2.23          N=16     0.0360  0.0300   0.83
    N=20      0.0670    0.1600    2.39          N=20     0.0460  0.0390   0.85

  semijoin      base   patched   ratio        innerjoin   base  patched  ratio
    N=2       0.0070    0.0070    1.00          N=2      0.0210  0.0220   1.05
    N=4       0.0130    0.0170    1.31          N=4      0.1240  0.1400   1.13
    N=8       0.0250    0.0440    1.76          N=6      0.6780  0.6660   0.98
    N=12      0.0420    0.0800    1.90          N=8      4.4150  4.3980   1.00
    N=16      0.0590    0.1270    2.15
    N=20      0.0790    0.1890    2.39

The control is flat, so the loop costs nothing when nothing is removed.
Left join removal is flat to slightly faster, increasingly so with N.
Self join elimination and reducible semijoins both degrade, and the ratio is
still climbing at N=20.


Why, and why single-point numbers mislead
-----------------------------------------

The cause is directly measurable rather than inferred.  Instrumenting the top
of query_planner's loop with an elog and counting iterations per plan:

  case        N=2   N=4   N=8   N=16
  leftjoin      2     2     2      2
  selfjoin      2     4     8     16
  semijoin      3     5     9     17

remove_useless_joins batches every removal it finds into a single pass, so
left join removal costs two passes no matter how many joins are removed, and
the second pass is cheap because the relations are gone.  That is why it comes
out ahead: it pays one extra derivation and saves all the incremental fixup
work.

remove_useless_self_joins returns after the first removal it makes, so an
N-way self join costs N passes over a shrinking jointree.  That is O(N^2)
derivation work, and it is the entire regression.

The semijoin case is the self join case wearing a hat.  Once
reduce_unique_semijoins converts the semijoins to inner joins, they are self
joins on a unique column, so self-join elimination then removes them one per
pass: one pass to derive, one to reduce, N-1 to remove.

So the fix is to make remove_useless_self_joins batch like
remove_useless_joins does, and the current numbers are an upper bound on the
cost rather than an inherent property of the approach.

Two corrections to what I said earlier in this thread.  First, I quoted the
8-way self join figure (there 0.023 -> 0.039 ms) as though it characterized
the case; at 1.7x it is near the low end of the curve, and quoting a single
point for a quadratic effect was the wrong thing to do.  Second, I described
the semijoin case as "a wash or slightly better".  That comparison was between
two variants of the patch, reduce_unique_semijoins running mid-loop versus
running last, and it holds as such.  It is not a patch-versus-master result,
and against master the semijoin case regresses by the same factor as the self
join case, which I had not measured at the time.


Scripts
-------

schema.sql:

  CREATE TABLE sj (a int primary key, b int, c text);
  INSERT INTO sj SELECT g, g, g::text FROM generate_series(1, 1000) g;
  DO $$
  BEGIN
    FOR i IN 1..40 LOOP
      EXECUTE format('CREATE TABLE j%s (a int primary key, b int, c text)', i);
      EXECUTE format('INSERT INTO j%s SELECT g, g, g::text
                      FROM generate_series(1,1000) g', i);
    END LOOP;
  END $$;
  VACUUM ANALYZE;

genquery.py builds one statement per (case, N):

  selfjoin   'select t1.b from sj t1 ' + ' '.join(
                 'join sj t%d on t1.a = t%d.a' % (i, i)
                 for i in range(2, n + 1))
  leftjoin   as above with 'left join'
  innerjoin  'select t1.b from j1 t1 ' + ' '.join(
                 'join j%d t%d on t1.a = t%d.a' % (i, i, i)
                 for i in range(2, n + 1))
  semijoin   'select t1.b from sj t1 where ' + ' and '.join(
                 'exists (select 1 from sj s%d where s%d.a = t1.a)' % (i, i)
                 for i in range(2, n + 1))

Measurement loop, per case: write the four SET commands followed by 201 copies
of "EXPLAIN (COSTS OFF, SUMMARY ON) <query>;" to a file, then

  psql -qAt -f $f | grep 'Planning Time' | sed 's/.*: //; s/ ms//' \
     | tail -n +2 | sort -g

and take element 1 (min), the middle element (median), and element 0.9*N (p90).
tail -n +2 discards the warmup.
