From: Tom Lane <tgl@sss.pgh.pa.us>
To: Peter Geoghegan <pg@bowt.ie>
cc: Matthias van de Meent <boekewurm+postgres@gmail.com>,
        PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Questions regarding Index AMs and natural ordering
In-reply-to: <CAH2-WznVkprOOxEAq5wj4vUJOh4u7Tqvt_hG2EQODzoTxHTogA@mail.gmail.com>
References: <CAEze2WgOAiKHoQFXujDd8kopq=bJLFVHh9mKfA502Rxf1Xh3dQ@mail.gmail.com> <CAH2-WznVkprOOxEAq5wj4vUJOh4u7Tqvt_hG2EQODzoTxHTogA@mail.gmail.com>
Comments: In-reply-to Peter Geoghegan <pg@bowt.ie>
	message dated "Thu, 23 Nov 2023 10:51:51 -0800"
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-ID: <3167404.1700766950.1@sss.pgh.pa.us>
Content-Transfer-Encoding: 8bit
Date: Thu, 23 Nov 2023 14:15:50 -0500
Message-ID: <3167405.1700766950@sss.pgh.pa.us>
Archived-At: <https://www.postgresql.org/message-id/3167405.1700766950%40sss.pgh.pa.us>
Precedence: bulk

Peter Geoghegan <pg@bowt.ie> writes:
> On Thu, Nov 23, 2023 at 9:16 AM Matthias van de Meent
> <boekewurm+postgres@gmail.com> wrote:
>> 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).

Agreed on that, but I don't have that hard a time imagining cases
where it might be useful for btree not to guarantee ordered output.
IIRC, it currently has to do extra pushups to ensure that behavior
in ScalarArrayOp cases.  We've not bothered to expand the planner
infrastructure to distinguish "could, but doesn't" paths for btree
scans, but that's more about it not being a priority than because it
wouldn't make sense.  If we did put work into that, we'd probably
generate multiple indexscan Paths for the same index and same index
conditions, some of which are marked with sort ordering PathKeys and
some of which aren't (and have a flag that would eventually tell the
index AM not to bother with sorting at runtime).

> 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.

Right.  There hasn't been a reason to decouple that, just as our
notions of hashing are tied to the hash AM.  This doesn't entirely
foreclose other AMs that handle sorted output, but it constrains
them to use btree's opclasses to represent the ordering.

			regards, tom lane