Re: Reverse-sort indexes and NULLS FIRST/LAST sorting

Martijn van Oosterhout <kleptog(at)svana(dot)org> writes:
> On Mon, Jan 01, 2007 at 05:53:35PM -0500, Tom Lane wrote:
>> One way we could handle this is to say that reverse-sort indexes are
>> implemented by adding explicit catalog entries for reverse-sort opclasses,
>> with no additions to the underlying btree index mechanisms. So you
>> might make an index using a command like
>>
>> CREATE INDEX fooi ON foo (x, y reverse_int4_ops);

> Personally I favour this approach. It's also the approach similar to
> what I did with the COLLATE stuff. It's IMHO the cleanest because it
> encapsulates the order at the level where it's important.

> In particular, NULLS FIRST/LAST makes sense for btree, but no other
> index type, so storing the order seperatly is wasted space for any
> other index type.

After further thought I'm leaning towards doing it the other way, ie,
with explicit DESC and NULLS FIRST/LAST modifiers attached to index
columns, rather than specialized opclasses. Comparing this to the
concerns that have been mentioned:

* Allows indexes to support mixed nulls-first-or-last orderings.
Although I can't make a real strong argument why that's important,
I have a feeling that we'll miss it if we can't handle it.

* Solves the problem once, instead of requiring extra code in every
datatype. Even though that code would largely be boilerplate
copy-and-paste stuff, it's still tedious and easy to get wrong.

* Possible slowdown of btree code: after looking a bit, I think this is
a red herring. Most of the work would be done by flipping operator
strategy numbers during scan setup. As best I can tell without actually
coding it, the only addition required to the inner-loop comparison
function will be one extra test-and-branch in the code paths where we've
detected we are comparing a NULL to a non-NULL. That doesn't seem like
a big problem.

* Ugly wart added to pg_index: yeah, it is, although I have an idea that
might make it more palatable. Rather than add a couple of boolean
vectors (which is a datatype we don't have anyway), I'm thinking of
adding an int2vector field named something like "indoption" which would
store per-column flag bits with index-AM-specific meanings. DESC and
NULLS FIRST/LAST would take up two of these bits for btree (and any
other index AM that supports ordered scans), the rest are available for
expansion. I do not know if there's any immediate use for such flag
bits for GiST or GIN, but one obvious possible use for btree is to store
collation info. (I suppose we can find a way to identify a collation with
a dozen or less bits, so it should fit.)

Another possible objection is that in the proposed CREATE INDEX syntax

index-column-id [ opclass-name ] [ DESC ] [ NULLS {FIRST|LAST} ]

DESC must be a fully reserved word else it can't be distinguished from
an opclass name. But guess what, it already is.

Comments?

regards, tom lane