Thread: Reverse collations (initially for making keyset pagination covermore cases)

Folks,

Please find attached a patch for $Subject.

Motivation:

When people are doing keyset pagination, the simple cases redound to
adding a WHERE that looks like

    (a, b, c) > (most_recent_a, most_recent_b, most_recent_c)

which corresponds to an ORDER BY clause that looks like

    ORDER BY a, b, c

The fun starts when there are mixes of ASC and DESC in the ORDER BY
clause. Reverse collations make this simpler by inverting the meaning
of > (or similar), which makes the rowtypes still sortable in a new
dictionary order, so the pagination would look like:


    (a, b, c) > (most_recent_a, most_recent_b COLLATE "C_backwards", most_recent_c)

with an ORDER BY like:

    ORDER BY a, b DESC, c

What say?

Best,
David.
-- 
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

David Fetter <david@fetter.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?
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.

            regards, tom lane

>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:

 Tom> Lastly, your proposed use-case has some attraction, but this
 Tom> proposal only supports it if the column you need to be differently
 Tom> sorted is textual. What if the sort columns are all numerics and
 Tom> timestamps?

There are already trivial ways to reverse the orders of those, viz.
(-number) and (-extract(epoch from timestampcol)). The lack of any
equivalent method for text is what prompted this idea.

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

Well, one obvious completely general method is to teach the planner
(somehow) to spot conditions of the form

  (a > $1 OR (a = $1 AND b > $2) OR (a = $1 AND b = $2 AND c > $3) ...)
  
etc. and make them indexable if the sense of the > or < operator at
each step matched an ASC or DESC column in the index.

This would be a substantial win, because this kind of condition is one
often (incorrectly, for current PG) shown as an example of how to do
keyset pagination on multiple columns. But it would require some amount
of new logic in both the planner and, afaik, in the btree AM; I haven't
looked at how much.

-- 
Andrew (irc:RhodiumToad)

On Sun, Nov 17, 2019 at 02:30:35PM -0500, Tom Lane wrote:
> David Fetter <david@fetter.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)
...
ORDER BY a, b DESC, c

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)
...
ORDER BY a, b DESC, c

which may not even get optimized correctly.

Best,
David.
-- 
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

>>>>> "David" == David Fetter <david@fetter.org> writes:

First, in testing the patch I found there were indeed some missing
cases: the sortsupport version of the comparator needs to be fixed too.
I attach a draft addition to your patch, you should probably look at
adding test cases that need this to work.

 David> (a, b, c) < ($1, $2 COLLATE "C_backwards", $3)
 David> ...
 David> ORDER BY a, b DESC, c

That would have to be:

 WHERE (a, b COLLATE "C_backwards", c) < ($1, $2, $3)
 ...
 ORDER BY a, b COLLATE "C_backwards", c

Adding the below patch to yours, I can get this on the regression test
db (note that this is a -O0 asserts build, timings may be slow relative
to a production build):

create collation "C_rev" ( LOCALE = "C", REVERSE = true );
create index on tenk1 (hundred, (stringu1::text collate "C_rev"), string4);

explain analyze
  select hundred, stringu1::text, string4
    from tenk1
   where (hundred, stringu1::text COLLATE "C_rev", string4)
           > (10, 'WKAAAA', 'VVVVxx')
   order by hundred, (stringu1::text collate "C_rev"), string4
   limit 5;
                                                                       QUERY PLAN
                               
 

--------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.29..1.28 rows=5 width=132) (actual time=0.029..0.038 rows=5 loops=1)
   ->  Index Scan using tenk1_hundred_stringu1_string4_idx on tenk1  (cost=0.29..1768.49 rows=8900 width=132) (actual
time=0.028..0.036rows=5 loops=1)
 
         Index Cond: (ROW(hundred, ((stringu1)::text)::text, string4) > ROW(10, 'WKAAAA'::text, 'VVVVxx'::name))
 Planning Time: 0.225 ms
 Execution Time: 0.072 ms
(5 rows)

and I checked the results, and they look correct now.

-- 
Andrew (irc:RhodiumToad)

diff --git a/src/backend/utils/adt/varlena.c b/src/backend/utils/adt/varlena.c
index 02cbcbd23d..61ab9720c5 100644
--- a/src/backend/utils/adt/varlena.c
+++ b/src/backend/utils/adt/varlena.c
@@ -84,6 +84,7 @@ typedef struct
     int            last_returned;    /* Last comparison result (cache) */
     bool        cache_blob;        /* Does buf2 contain strxfrm() blob, etc? */
     bool        collate_c;
+    bool        reverse;
     Oid            typid;            /* Actual datatype (text/bpchar/bytea/name) */
     hyperLogLogState abbr_card; /* Abbreviated key cardinality state */
     hyperLogLogState full_card; /* Full key cardinality state */
@@ -2090,6 +2091,7 @@ varstr_sortsupport(SortSupport ssup, Oid typid, Oid collid)
         /* Initialize */
         sss->last_returned = 0;
         sss->locale = locale;
+        sss->reverse = (locale != 0) && locale->reverse;
 
         /*
          * To avoid somehow confusing a strxfrm() blob and an original string,
@@ -2401,6 +2403,9 @@ varstrfastcmp_locale(char *a1p, int len1, char *a2p, int len2, SortSupport ssup)
         (!sss->locale || sss->locale->deterministic))
         result = strcmp(sss->buf1, sss->buf2);
 
+    if (sss->reverse)
+        INVERT_COMPARE_RESULT(result);
+
     /* Cache result, perhaps saving an expensive strcoll() call next time */
     sss->cache_blob = false;
     sss->last_returned = result;
@@ -2663,6 +2668,13 @@ done:
      */
     res = DatumBigEndianToNative(res);
 
+    /*
+     * Account for reverse-ordering locales by flipping the bits. Note that
+     * Datum is an unsigned type (uintptr_t).
+     */
+    if (sss->reverse)
+        res ^= ~(Datum)0;
+
     /* Don't leak memory here */
     if (PointerGetDatum(authoritative) != original)
         pfree(authoritative);

On Sun, Nov 17, 2019 at 11:23:23PM +0000, Andrew Gierth wrote:
> >>>>> "David" == David Fetter <david@fetter.org> writes:
> 
> First, in testing the patch I found there were indeed some missing
> cases: the sortsupport version of the comparator needs to be fixed too.
> I attach a draft addition to your patch, you should probably look at
> adding test cases that need this to work.
> 
>  David> (a, b, c) < ($1, $2 COLLATE "C_backwards", $3)
>  David> ...
>  David> ORDER BY a, b DESC, c
> 
> That would have to be:
> 
>  WHERE (a, b COLLATE "C_backwards", c) < ($1, $2, $3)
>  ...
>  ORDER BY a, b COLLATE "C_backwards", c
> 
> Adding the below patch to yours, I can get this on the regression test
> db (note that this is a -O0 asserts build, timings may be slow relative
> to a production build):
> 
> create collation "C_rev" ( LOCALE = "C", REVERSE = true );
> create index on tenk1 (hundred, (stringu1::text collate "C_rev"), string4);
> 
> explain analyze
>   select hundred, stringu1::text, string4
>     from tenk1
>    where (hundred, stringu1::text COLLATE "C_rev", string4)
>            > (10, 'WKAAAA', 'VVVVxx')
>    order by hundred, (stringu1::text collate "C_rev"), string4
>    limit 5;
>                                                                        QUERY PLAN
                                 
 
>
--------------------------------------------------------------------------------------------------------------------------------------------------------
>  Limit  (cost=0.29..1.28 rows=5 width=132) (actual time=0.029..0.038 rows=5 loops=1)
>    ->  Index Scan using tenk1_hundred_stringu1_string4_idx on tenk1  (cost=0.29..1768.49 rows=8900 width=132) (actual
time=0.028..0.036rows=5 loops=1)
 
>          Index Cond: (ROW(hundred, ((stringu1)::text)::text, string4) > ROW(10, 'WKAAAA'::text, 'VVVVxx'::name))
>  Planning Time: 0.225 ms
>  Execution Time: 0.072 ms
> (5 rows)
> 
> and I checked the results, and they look correct now.

Here's that patch with your correction rolled in.

This will need more tests, and possibly more documentation.

Best,
David.
-- 
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
>  Tom> Lastly, your proposed use-case has some attraction, but this
>  Tom> proposal only supports it if the column you need to be differently
>  Tom> sorted is textual. What if the sort columns are all numerics and
>  Tom> timestamps?

> There are already trivial ways to reverse the orders of those, viz.
> (-number) and (-extract(epoch from timestampcol)). The lack of any
> equivalent method for text is what prompted this idea.

Those "trivial ways" have failure cases, eg with INT_MIN.  I don't buy
that this argument justifies introducing a kluge into text comparison.

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

> Well, one obvious completely general method is to teach the planner
> (somehow) to spot conditions of the form
>   (a > $1 OR (a = $1 AND b > $2) OR (a = $1 AND b = $2 AND c > $3) ...)
> etc. and make them indexable if the sense of the > or < operator at
> each step matched an ASC or DESC column in the index.

I think really the only attraction of that is that it could be argued
to be standard --- but I rather doubt that it's common for DBMSes to
recognize such things.  It'd certainly be a royal pain in the rear
both to implement and to use, at least for more than about two sort
columns.

Back at
https://www.postgresql.org/message-id/10492.1531515255%40sss.pgh.pa.us
I proposed that we might consider allowing row comparisons to specify
an explicit list of operators:

>> One idea for resolving that is to extend the OPERATOR syntax to allow
>> multiple operator names for row comparisons, along the lines of
>>    ROW(a,b) OPERATOR(pg_catalog.<, public.<) ROW(c,d)

I wonder whether it'd be feasible to solve this problem by doing that
and then allowing the operators to be of different comparison types,
that is "ROW(a,b) OPERATOR(<, >) ROW(c,d)".  The semantics would be
that the first not-equal column pair determines the result according
to the relevant operator.  But I'm not quite sure what to do if the
rows are in fact equal --- if some of the operators are like "<" and
some are like "<=", what should the result be?  Maybe let the last
column's operator decide that?

            regards, tom lane

>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:

 >> Well, one obvious completely general method is to teach the planner
 >> (somehow) to spot conditions of the form
 >> (a > $1 OR (a = $1 AND b > $2) OR (a = $1 AND b = $2 AND c > $3) ...)
 >> etc. and make them indexable if the sense of the > or < operator at
 >> each step matched an ASC or DESC column in the index.

 Tom> I think really the only attraction of that is that it could be
 Tom> argued to be standard --- but I rather doubt that it's common for
 Tom> DBMSes to recognize such things.

At least MSSQL can recognize that a query with

  WHERE (a > @a OR (a = @a AND b > @b)) ORDER BY a,b

can be satisfied with an ordered index scan on an (a,b) index and no
sort, which is good enough for pagination queries. Haven't confirmed
yes/no for any other databases yet.

(As an aside, if you try and do that in PG using UNION ALL in place of
the OR, to try and get a mergeappend of two index scans, it doesn't work
well because of how we discard redundant pathkeys; you end up with Sort
nodes in the plan.)

 Tom> It'd certainly be a royal pain in the rear both to implement and
 Tom> to use, at least for more than about two sort columns.

For pagination one or two columns seems most likely, but in any event
the query can be generated mechanically if need be.

-- 
Andrew (irc:RhodiumToad)