Re: Reverse collations (initially for making keyset pagination cover more cases)

From: David Fetter <david(at)fetter(dot)org>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: PostgreSQL Development <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Reverse collations (initially for making keyset pagination cover more cases)
Date: 2019-11-17 21:54:26
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

On Sun, Nov 17, 2019 at 02:30:35PM -0500, Tom Lane wrote:
> David Fetter <david(at)fetter(dot)org> writes:
> > Please find attached a patch for $Subject.
> I think there's a reason why this hasn't been proposed before.
> Back before we had full support of ASC/DESC index sort order, there was
> interest in having reverse-sort operator classes, and there are bits and
> pieces still in the code that tried to cater to that. But we never got
> it to the point where such things would really be pleasant to use.
> Now that we have ASC/DESC indexes, there's no value in a reverse-sort
> operator class, so the idea's pretty much been consigned to the dustbin.
> This looks to me like it's trying to go down that same path at the
> collation level, and it seems like just as bad of an idea here.
> The fundamental problem with what you propose is that it'd require
> a bunch of infrastructure (which you haven't even attempted) to teach
> the planner about the relationships between forward- and reverse-sort
> collation pairs, so that it could figure out that scanning some index
> backwards would satisfy a request for the reverse-sort collation,
> or vice versa. Without such infrastructure, the feature is really
> just a gotcha, because queries won't get optimized the way users
> would expect them to.
> And no, I don't think we should accept the feature and then go write
> that infrastructure. If we couldn't make it work well at the opclass
> level, I don't think things will go better at the collation level.
> Lastly, your proposed use-case has some attraction, but this proposal
> only supports it if the column you need to be differently sorted is
> textual. What if the sort columns are all numerics and timestamps?

Those are pretty straightforward to generate: -column, and
-extract('epoch' FROM column), respectively.

> Thinking about that, it seems like what we'd want is some sort of
> more-general notion of row comparison, to express "bounded below in
> an arbitrary ORDER BY ordering". Not quite sure what it ought to
> look like.

I'm not, either, but the one I'm proposing seems like a lot less
redundant code (and hence a lot less room for errors) than what people
generally see proposed for this use case, to wit:

(a, b, c) < ($1, $2 COLLATE "C_backwards", $3)

as opposed to the "standard" way to do it

(a > $1) OR
(a = $1 AND b < $2) OR
(a = $1 AND b = $2 AND c > $3)

which may not even get optimized correctly.

David Fetter <david(at)fetter(dot)org>
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres:

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Andrew Gierth 2019-11-17 23:23:23 Re: Reverse collations (initially for making keyset pagination cover more cases)
Previous Message Thomas Munro 2019-11-17 21:11:36 Re: Invisible PROMPT2