Re: Comments for lossy ORDER BY are lacking - Mailing list pgsql-hackers

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