Re: index prefetching

Hi Peter,

I had a look at v34, focusing on 0001 since you're about to push it.
All 12 patches apply cleanly to master (798bdcae89d). make check, the
src/test/modules/index tests, and amcheck (regress + TAP) pass with
0001 applied on its own; at the tip of the series those plus
btree_gist also pass.

1. I read through 0001 in full and didn't find any problems. To
double-check that behavior is unchanged, I ran A/B comparisons of an
0001-only build against an unpatched master build (same base commit):

* Index-only scans on name columns: padded key columns (including
63-character values), an index with two name key columns, a name
INCLUDE column, NULLs, and backward scans. Output was byte-identical
to master, and matched the same queries executed via seqscan.

* "Heap Fetches": byte-identical output in serial cases (including
the repro from point 4, where 0001 also reports 1325). For the
parallel case I used a repro built so that the total is deterministic
(every heap page keeps dead tuples, so no page can become all-visible
mid-scan): a parallel index-only scan with 2 workers reported exactly
the expected 300000 on both builds.

* get_actual_variable_range: identical row estimates for a case with
26000 dead entries at the top of the index (well past the 100-page
visited-pages cap) and for a small-bloat case, on tables small enough
that ANALYZE samples every row (so the two builds also start from
identical statistics).

2. Since v34 is about index-only scan regressions, I also timed two
index-only scans on pgbench_accounts_pkey (pgbench -s 5, everything in
shared_buffers, VACUUMed so Heap Fetches is 0; -O2 without assertions;
single client, -M prepared; 5 alternating 15-second rounds per build):

point: SELECT aid FROM pgbench_accounts WHERE aid = :aid
range: SELECT count(*) FROM pgbench_accounts
WHERE aid BETWEEN :lo AND :lo + 9999

median tps master master + 0001 full series
point 42875 44583 (+4.0%) 43726 (+2.0%)
range 1228 1228 (+0.0%) 1293 (+5.3%)

(min-max over the 5 rounds: point 42076-43062 / 43930-44759 /
42302-44176; range 1209-1257 / 1212-1245 / 1290-1311)

So with 0001 alone the 10k-row range scan is at parity and the point
lookup is a bit faster; the full series is faster on both.

3. On the 3 new amapi.h includes you flagged: I measured the effect
with gcc -MM over the 941 backend and contrib translation units whose
includes it could resolve on all three trees. The attached patch (on
top of v34-0001) adds a header for the table AM side of index scans,
access/tableam_index.h, and moves index_getnext_tid() there (verbatim,
still inline), restoring amapi.h's previous include list:

TUs including it master master + 0001 + attached patch
pgstat.h 146 280 149
access/relscan.h 127 235 126
utils/rel.h 316 358 316

The translation units that include amapi.h go from about 114 to about
133 headers each on average with 0001, and back to 114 with the patch.
The files that newly pull in pgstat.h with 0001 are 94 backend files
plus 21 of the 23 in contrib/btree_gist, all 5 in contrib/bloom, and 2
of the 4 in contrib/amcheck, since the index AM private headers
(nbtree.h, hash.h, gist_private.h, spgist.h, brin_internal.h,
gin_private.h) and reloptions.h all include amapi.h. The only in-tree
caller of index_getnext_tid() is heapam_indexscan.c; the new header is
included there and in indexam.c (for the index_fill_ios_slot prototype).

The header also declares index_fill_ios_slot(), the other helper meant
only for table AMs, and its comment spells out what an xs_getnext_slot
callback is expected to do, including maintaining
scan->instrument->ntabletuplefetches, which so far is only stated in
the commit message ("which table AMs are required to maintain"); a
table AM that doesn't maintain it just shows Heap Fetches: 0 under
EXPLAIN ANALYZE.

On the "XXX Is there a more elegant way to do this?" next to heapam's
hand-specialized copy of index_fill_ios_slot's IndexTuple case: I
tried making index_fill_ios_slot() itself a static inline in the new
header and dropping that copy. With the setup from point 2 the point
lookup dropped from a median of 43885 tps (0001) to 40636 (all 5
rounds below all 5 rounds of 0001), a second run of 6 alternating
rounds gave -6% again, and the range scan was unchanged both times.
perf stat on the backend over 300000 point lookups, 3 alternating
runs per build, per transaction:

0001 0001 + inline
instructions 45.0k - 45.5k 45.5k
cycles 49.3k - 53.6k 55.4k - 57.9k
L1 icache misses 4.30k - 4.40k 4.53k - 4.57k
branch misses 76 - 85 87 - 92

Same instruction count, more cycles. Per-symbol perf record puts only
about 100 of the roughly 4500 extra cycles per transaction in the
callback itself (heapam_index_only_tuple_getnext_slot goes from 84 to
147 cycles per transaction, plus a little in ExecStoreVirtualTuple and
index_deform_tuple); the rest is spread over some 300 unrelated
functions (_bt_compare, ExecInitQual, SearchCatCacheInternal, ...), so
most of it is a code-layout effect: the callback grows from 354 to 466
bytes (and from 4 to 6 callee-saved register pushes at entry), which
shifts everything after it in the text segment. The intrinsic cost is
small, but inlining buys nothing either, so the patch leaves
index_fill_ios_slot out of line and the hand-specialized copy in place.

make check, the modules/index tests, headerscheck and cpluspluscheck
pass with the patch, and it applies at the tip of the series with a
3-way merge.

Separately, 0003's indexbatch.h includes pgstat.h itself and is
included by nbtree.h, hash.h, gist_private.h and spgist_private.h, so
at the tip pgstat.h comes back into the index AM headers by that route
(73 translation units when I measure the series tip the same way).
The attached patch only addresses 0001, but the same split would work
there: what needs pgstat.h in indexbatch.h is
tableam_util_fetch_next_batch(), and it and the other tableam_util_*
helpers are only called from heapam_indexscan.c and indexbatch.c, so
they could go into tableam_index.h and leave indexbatch.h with the
batch structures that the index AMs need.

4. One behavioral difference with the full series applied (0001 alone
matches master exactly here):

CREATE TABLE hf (a int) WITH (autovacuum_enabled = off);
INSERT INTO hf SELECT g FROM generate_series(1, 1000) g;
CREATE INDEX hf_a_idx ON hf (a);
VACUUM (ANALYZE) hf;
UPDATE hf SET a = a + 1000; -- never HOT
SET enable_seqscan = off;
SET enable_bitmapscan = off;
EXPLAIN (ANALYZE, COSTS off, TIMING off, SUMMARY off, BUFFERS off)
SELECT count(*) FROM hf;

The first index-only scan after the update reports Heap Fetches: 1325
on master and 2000 with the series. The lower number on master comes
from the scan itself: pages that hold only new row versions get their
VM bits set by on-access pruning during the scan
(pg_visibility shows 0 all-visible pages before the scan and 3 after,
on both builds), and with retail VM lookups the later TIDs pointing at
those pages then skip the heap fetch. With amgetbatch the visibility
info for a batch's items is resolved ahead of consumption
(heapam_index_batch_pos_visibility), so a VM bit set mid-scan isn't
seen. effective_io_concurrency = 0 doesn't change it, and the query
results are the same on both builds. Not a correctness issue; I'm
noting it because on-access pruning setting VM bits is new this cycle.

5. With the full series I can also see prefetching engage on this box:
a plain index scan over ~25k scattered TIDs right after a restart
shows

Prefetch: avg=30.27 max=93 capacity=94
I/O: count=8618 waits=43 size=1.00 in-progress=15.77

under EXPLAIN (ANALYZE, IO). (No disk-bound numbers from me -- the
data was all in page cache.)

Regards,
Rui Zhao