From: Andreas Joseph Krogh <andreak@officenet.no>
Organization: OfficeNet AS
To: pgsql-sql@postgresql.org
Subject: Re: Index usage in order by with multiple columns in order-by-clause
Date: Sat, 11 Aug 2007 22:14:58 +0200
User-Agent: KMail/1.9.6
Cc: Tom Lane <tgl@sss.pgh.pa.us>
References: <200708101653.13011.andreak@officenet.no>
	<200708111122.08235.andreak@officenet.no>
	<7984.1186862149@sss.pgh.pa.us>
In-Reply-To: <7984.1186862149@sss.pgh.pa.us>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Message-Id: <200708112214.58176.andreak@officenet.no>

On Saturday 11 August 2007 21:55:49 Tom Lane wrote:
> 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=3D# 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=3D# create operator class rev_float8_ops for type float8 using
> btree regression-# as
> regression-#   operator 1 > ,
> regression-#   operator 2 >=3D ,
> regression-#   operator 3 =3D ,
> regression-#   operator 4 <=3D ,
> regression-#   operator 5 < ,
> regression-#   function 1 btrevfloat8cmp(float8,float8) ;
> CREATE OPERATOR CLASS
>
> And you're off:
>
> regression=3D# create table myt (f1 float8, f2 float8);
> CREATE TABLE
> regression=3D# create index myi on myt using btree (f1, f2 rev_float8_ops=
);
> CREATE INDEX
> regression=3D# insert into myt values(1,1),(1,2),(1,3),(2,1),(2,2),(2,3);
> INSERT 0 6
> regression=3D# explain select * from myt order by f1 asc, f2 desc;
>                              QUERY PLAN
> --------------------------------------------------------------------
>  Index Scan using myi on myt  (cost=3D0.00..72.70 rows=3D1630 width=3D16)
> (1 row)
>
> regression=3D# 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=3D# explain select * from myt order by f1 desc, f2 asc;
>                                  QUERY PLAN
> -------------------------------------------------------------------------=
=2D-
>-- Index Scan Backward using myi on myt  (cost=3D0.00..72.70 rows=3D1630
> width=3D16) (1 row)
>
> regression=3D# 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.

Thank you, really neat stuff.

=2D-=20
Andreas Joseph Krogh <andreak@officenet.no>
Senior Software Developer / Manager
=2D-----------------------+---------------------------------------------+
OfficeNet AS            | The most difficult thing in the world is to |
Karenslyst All=C3=A9 11      | know how to do a thing and to watch         |
PO. Box 529 Sk=C3=B8yen      | somebody else doing it wrong, without       |
0214 Oslo               | comment.                                    |
NORWAY                  |                                             |
Tlf:    +47 24 15 38 90 |                                             |
=46ax:    +47 24 15 38 91 |                                             |
Mobile: +47 909  56 963 |                                             |
=2D-----------------------+---------------------------------------------+