Обсуждение: Backwards index scan

I am not sure if this is really a bug, but it certainly looks like one
to me...

I have a table that looks something like this:

create table huge_table
(
    int x,
    int y
);
create index huge_table_idx on huge_table (x,y);

It contains about 80 million rows...
I am trying to get those rows that have a particular value for x,
ordered by y in descending order (and I am looking to get just a few
first ones), so I am running a query like:

declare mycursor cursor for select * from huge_table where x=10 order by
x desc, y desc;
fetch 10 from mycursor;

this query takes 10 to 20 minutes!

This is because there are *lots* (a few million) of matches for x=10,
and _bt_first () scans through them *all* sequentually to get to the
last one.

Now, if I change the query to look like:

declare mycursor cursor for select * from huge_table where x > 9 and x <
11 order by x desc, y desc;
(which is the same thing)
then fetch 10 from mycursor; returns right away (under a second), just
as I expected.

I understand that with the generic approach to operators in postgres it
is, probably, not very feasible to try and teach _bt_first () to handle
this situation automatically (it would need to know how to get
next/previous value for every indexable type)... I guess, that could be
done by adding another kind of strategy to pg_amop for example...
Another way to work around this would be to allow ordering spec to be a
part of CREATE INDEX (I know, that informix does that for example) - so
that, I could do
create index huge_table_idx on huge_table (x, y desc);
... and then select * from huge_table where x=10 order x, y desc;
would not require a backwards scan to begin with.

Can something like this be done? What do you think?

Thanks!

Dima

On Mon, 7 Jul 2003, Dmitry Tkach wrote:

> I understand that with the generic approach to operators in postgres it
> is, probably, not very feasible to try and teach _bt_first () to handle
> this situation automatically (it would need to know how to get
> next/previous value for every indexable type)... I guess, that could be
> done by adding another kind of strategy to pg_amop for example...
> Another way to work around this would be to allow ordering spec to be a
> part of CREATE INDEX (I know, that informix does that for example) - so
> that, I could do
> create index huge_table_idx on huge_table (x, y desc);
> ... and then select * from huge_table where x=10 order x, y desc;
> would not require a backwards scan to begin with.
>
> Can something like this be done? What do you think?

If you make an opclass that orders in the reverse order you can use that
opclass in creating the index (which effectively can give you an index
like x, y desc by using the new opclass on y).  There was some talk
recently about whether we should provide such opclasses as builtins or
contrib items.

>
>
>If you make an opclass that orders in the reverse order you can use that
>opclass in creating the index (which effectively can give you an index
>like x, y desc by using the new opclass on y).  There was some talk
>recently about whether we should provide such opclasses as builtins or
>contrib items.
>
>
Ah! Nice :-)
I did not think about  it...

Thanks a lot for the hit!

Dima

Stephan Szabo wrote:

>If you make an opclass that orders in the reverse order you can use that
>opclass in creating the index (which effectively can give you an index
>like x, y desc by using the new opclass on y).  There was some talk
>recently about whether we should provide such opclasses as builtins or
>contrib items.
>
>
Actually, I just thought, it is not exactly equivalent, unless I am
missing something.
If I create this opclass and the index, and then make a query like
select * from huge_table where x=10 order by x,y desc

... it won't know to use the index for sorting, will it?
My understanding is that I'd have to get rid of the sort clause
completely, and just rely on the query plan, right?

In this situation, it will work... But it may be a problem when the
query is (a lot) more complicated, with several joins and a bunch of
different paths available to the planner - how can I guarantee then that
it will always choose this index and return the results in the right order?

Currently I just always use the sort clause, and that forces it to pick
the right index even if another path looks a little less expensive, but
with this custom opclass, I believe, having the sort clause will always
cause it to actually sort even if it does use the right index...

Or am I missing something here?

Thanks!

Dima

On Tue, 8 Jul 2003, Dmitry Tkach wrote:

> Stephan Szabo wrote:
>
> >If you make an opclass that orders in the reverse order you can use that
> >opclass in creating the index (which effectively can give you an index
> >like x, y desc by using the new opclass on y).  There was some talk
> >recently about whether we should provide such opclasses as builtins or
> >contrib items.
> >
> >
> Actually, I just thought, it is not exactly equivalent, unless I am
> missing something.
> If I create this opclass and the index, and then make a query like
> select * from huge_table where x=10 order by x,y desc
>
> ... it won't know to use the index for sorting, will it?

I don't know the mechanics (haven't looked) but it seems to know
based on the way the operators are assigned to the opclass. I've
done some minimal tests and for queries like
 select * from tab order by a, b desc
and then gotten effectively
 Index scan using <index> on <table>
as the plan with no sort steps.

> In this situation, it will work... But it may be a problem when the
> query is (a lot) more complicated, with several joins and a bunch of
> different paths available to the planner - how can I guarantee then that
> it will always choose this index and return the results in the right order?

You can't guarantee that it'll always choose this index because it's
possible that the index is more expensive for a particular query, but
it should consider the index.