Re: Comments for lossy ORDER BY are lacking

On Thu, Apr 18, 2019 at 05:30:20PM -0700, Andres Freund wrote:
> For not the first time I was trying to remember why and when the whole
> nodeIndexscan.c:IndexNextWithReorder() business is needed.
> [...]
> By reading enough code one can stitch together that that's really only
> needed for KNN like order bys with lossy distance functions. It'd be
> good if one had to dig less for that.

This thread got no replies, and on current master those comments are
the same as in 2015. I hit the same problem from the other side. I
was writing an out-of-tree index AM whose distances are approximate,
and I couldn't find the contract for xs_orderbyvals and
xs_recheckorderby in the index AM chapter. It's only in the GiST and
SP-GiST opclass chapters, written in terms of their distance support
functions, plus the short comment in relscan.h. I ended up
reconstructing it from IndexNextWithReorder(), from Heikki's
description of the queue in the 2015 "Buggy logic in nodeIndexscan.c
queue handling" thread [1], and from Robert's explanation of "index
returned tuples in wrong order" to the PostGIS folks [2].

The attached patch is comments and documentation only. It changes no
code.

What it says, and where:

- indexam.sgml, amgettuple: a new paragraph with the contract for a
scan with ordering operators. The AM fills xs_orderbyvals and
xs_orderbynulls, sets xs_recheckorderby, and returns tuples in
nondecreasing order of the values it reports. If xs_recheckorderby
is true, each value must be <= what the operator gives for the heap
tuple. The executor recomputes it, reorders, and errors out if the
bound is too big. In a scan that can return lossy tuples, the
values must have the operator's result type, and the values of
non-lossy tuples must be exact. Lossy ordering isn't supported in
index-only scans.

- nodeIndexscan.c, IndexNextWithReorder header: this is for ORDER BY
operators (amcanorderbyop), not btree ordering. It describes the
two promises the AM makes and why together they make the queue
correct, when a queued tuple can be returned, and what "index
returned tuples in wrong order" means. It also notes that the
ordering half of the contract is never checked, and what
reordering costs.

- nodeIndexscan.c, two in-loop comments: why the pop test compares
against the index's reported value rather than the recomputed one
(Tom asked exactly this in that thread; Heikki's answer is in [1]),
and what cmp < 0 means.

- nodeIndexscan.c, ReorderTuple and the ExecInitIndexScan setup
block: what is queued, and what is set up and why. The old comment
said "if we need to re-check ORDER BY exprs", but the block runs
for every scan with ORDER BY operators.

- execnodes.h, IndexScanState: which fields exist only for ORDER BY
operator scans, and how iss_OrderByValues differs from
xs_orderbyvals.

- relscan.h, xs_orderbyvals / xs_recheckorderby: "ordering operator"
means amcanorderbyop, plus the same contract in brief.

- pathnodes.h, IndexPath.indexorderbys: these are ORDER BY operator
expressions (typically distances). The list is NIL for btree-style
ordering, which is described only by pathkeys.

Your secondary point, setting up the reorder machinery for every
ORDER BY operator scan even when no opclass can be lossy, is still
true. I've left it alone: this patch only documents the current
behaviour, and the ExecInitIndexScan comment now says so. Fixing it
would need a way for an opclass to declare up front that its ordering
values are exact, which is a behaviour change and belongs in its own
thread. I haven't measured what the setup costs.

This overlaps with my patch in "Let an ordering index scan hand its
ORDER BY value to the target list", which touches the same files and
also documents xs_recheckorderby in indexam.sgml (one hunk here, the
ExecInitIndexScan comment, conflicts with it). This one is
independent and documents master as it is; I'll rebase whichever
lands second, and if both go in the indexam.sgml text should be merged
into one paragraph.

Build/check: compiled with -Wall on master (73d4ba8), touched files
pgindent-clean, "make -C doc/src/sgml check" passes. It applies
cleanly to current master (1f22453); none of the five files changed
in between.

[1] https://postgr.es/m/55639897.4030204@iki.fi
[2] https://postgr.es/m/CA+TgmoauhLf6R07sAUzQiRcstF5KfRw7nwiWn4VZgiSF8MaQaw@mail.gmail.com

--
Greg