To: Andreas Joseph Krogh <andreak@officenet.no>
cc: pgsql-sql@postgresql.org
Subject: Re: Index usage in order by with multiple columns in order-by-clause 
In-reply-to: <200708111122.08235.andreak@officenet.no> 
References: <200708101653.13011.andreak@officenet.no>
	<14180.1186781414@sss.pgh.pa.us>
	<200708111122.08235.andreak@officenet.no>
Comments: In-reply-to Andreas Joseph Krogh <andreak@officenet.no>
	message dated "Sat, 11 Aug 2007 11:22:08 +0200"
Date: Sat, 11 Aug 2007 15:55:49 -0400
Message-ID: <7984.1186862149@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Andreas Joseph Krogh <andreak@officenet.no> writes:
> On Friday 10 August 2007 23:30:14 Tom Lane wrote:
>> Reverse-sorted index columns are possible but not well supported in
>> existing PG releases (you need a custom operator class, and the planner
>> is not all that bright about using them).  8.3 will have full support.

> How exactly do I build an index in which one of the columns is "reverse
> sorted" in 8.2 (and 8.3)?

Here's a minimal example (tested in 8.2).  The pain-in-the-neck part
is creating a btree comparison function that reverses the normal one's
comparisons.  For the example I just did it in plpgsql, but if you were
to do this sort of thing on large tables you'd probably find you needed
a function written in C for speed:

regression=# create function btrevfloat8cmp(float8,float8) returns int as
regression-# $$begin return btfloat8cmp($2, $1); end$$
regression-# language plpgsql strict immutable;
CREATE FUNCTION

You then make the opclass using the regular comparison operators listed
in backwards order, plus the reverse comparison function:

regression=# create operator class rev_float8_ops for type float8 using btree
regression-# as
regression-#   operator 1 > ,
regression-#   operator 2 >= ,
regression-#   operator 3 = ,
regression-#   operator 4 <= ,
regression-#   operator 5 < ,
regression-#   function 1 btrevfloat8cmp(float8,float8) ;
CREATE OPERATOR CLASS

And you're off:

regression=# create table myt (f1 float8, f2 float8);
CREATE TABLE
regression=# create index myi on myt using btree (f1, f2 rev_float8_ops);
CREATE INDEX
regression=# insert into myt values(1,1),(1,2),(1,3),(2,1),(2,2),(2,3);
INSERT 0 6
regression=# explain select * from myt order by f1 asc, f2 desc;
                             QUERY PLAN                             
--------------------------------------------------------------------
 Index Scan using myi on myt  (cost=0.00..72.70 rows=1630 width=16)
(1 row)

regression=# select * from myt order by f1 asc, f2 desc;
 f1 | f2 
----+----
  1 |  3
  1 |  2
  1 |  1
  2 |  3
  2 |  2
  2 |  1
(6 rows)

regression=# explain select * from myt order by f1 desc, f2 asc;
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Index Scan Backward using myi on myt  (cost=0.00..72.70 rows=1630 width=16)
(1 row)

regression=# select * from myt order by f1 desc, f2 asc;
 f1 | f2 
----+----
  2 |  1
  2 |  2
  2 |  3
  1 |  1
  1 |  2
  1 |  3
(6 rows)

This is only a minimal example because I didn't bother with any
cross-type comparisons; you might need those depending on how much
use you expect to get out of the index.

The main problem with this is that you don't have any control over the
NULLS FIRST/LAST behavior.  Pre-8.3, btree indexes will always put nulls
at the end; the opclass has no control over that.  So the effective sort
order here is like ORDER BY f1 ASC NULLS LAST, f2 DESC NULLS LAST (or
NULLS FIRST for the backward scan), which might not be what you'd want.
I'm also pretty sure that the pre-8.3 planner will not figure out how to
use such an index for mergejoins (and it might not work if it did figure
it out, because of the nulls-ordering issue).  You might be able to
finesse all that if you can choose to put the reverse-sort opclass on a
NOT NULL column.

			regards, tom lane