Re: Questions regarding Index AMs and natural ordering

On Thu, Nov 23, 2023 at 9:16 AM Matthias van de Meent
<boekewurm+postgres(at)gmail(dot)com> wrote:
> For example, btree ignores any ordering scan keys that it is given in
> btrescan, which seems fine for btree because the ordering of a btree
> is static (and no other order than that is expected apart from it's
> reverse order), but this becomes problematic for other indexes that
> could return ordered data but would prefer not to have to go through
> the motions of making sure the return order is 100% correct, rather
> than a k-sorted sequence, or just the matches to the quals (like
> GIST). Is returning index scan results in (reverse) natural order not
> optional but required with amcanorder? If it is required, why is the
> am indicator called 'canorder' instead of 'willorder', 'doesorder' or
> 'isordered'?

I don't know. I have a hard time imagining an index AM that is
amcanorder=true that isn't either nbtree, or something very similar
(so similar that it seems unlikely that anybody would actually go to
the trouble of implementing it from scratch).

You didn't mention support for merge joins. That's one of the defining
characteristics of an amcanorder=true index AM, since an
"ammarkpos/amrestrpos function need only be provided if the access
method supports ordered scans". It's hard to imagine how that could
work with a loosely ordered index. It seems to imply that the scan
must always work with a simple linear order.

Cases where the planner uses a merge join often involve an index path
with an "interesting sort order" that "enables" the merge join.
Perhaps most of the alternative plans (that were almost as cheap as
the merge join plan) would have had to scan the same index in the same
way anyway, so it ends up making sense to use a merge join. The merge
join can get ordered results from the index "at no extra cost". (All
of this is implicit, of course -- the actual reason why the planner
chose the merge join plan is because it worked out to be the cheapest
plan.)

My impression is that this structure is fairly well baked in -- which
the optimizer/README goes into. That is, the planner likes to think of
paths as having an intrinsic order that merge joins can take advantage
of -- merge joins tend to win by being "globally optimal" without
being "locally optimal". So generating extra index paths that don't
have any intrinsic order (but can be ordered using a special kind of
index scan) seems like it might be awkward to integrate.

I'm far from an expert on the planner, so take anything that I say
about it with a grain of salt.

> Alternatively, if an am should be using the order scan keys from
> .amrescan and natural order scans also get scan keys, is there some
> place I find the selection process for ordered index AMs, and how this
> ordering should be interepreted? There are no good examples available
> in core code because btree is special-cased, and there are no other
> in-tree AMs that have facilities where both `amcanorderbyop` and
> `amcanorder` are set.

The general notion of a data type's sort order comes from its default
btree operator class, so the whole idea of a generic sort order is
deeply tied to the nbtree AM. That's why we sometimes have btree
operator classes for types that you'd never actually want to index (at
least not using a btree index).

--
Peter Geoghegan