Thread: 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.