Re: Index usage in order by with multiple columns in order-by-clause

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=# 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.

Thank you, really neat stuff.

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