Thread: Problem with indexes, LIMIT, ORDER BY ... DESC

Problem with indexes, LIMIT, ORDER BY ... DESC

From
Ken Williams
Date:
Hi,

I'm having trouble with indexes in PostgreSQL 7.1.3.  Here is a
transcript:

==========================================================================
=
announce=# \d foo
                  Table "foo"
  Attribute |           Type           | Modifier
-----------+--------------------------+----------
  code      | character varying(4)     | not null
  date      | timestamp with time zone | not null
  price     | numeric(10,2)            | not null
  volume    | integer                  | not null
  other     | boolean                  | not null
Index: foo_code_date

announce=# \d foo_code_date
       Index "foo_code_date"
  Attribute |           Type
-----------+--------------------------
  code      | character varying(4)
  date      | timestamp with time zone
btree

announce=# explain select date from foo where date < '06/08/2001
23:59' and code = 'FOO' order by code, date limit 1;
NOTICE:  QUERY PLAN:

Limit  (cost=0.00..3.78 rows=1 width=20)
   ->  Index Scan using foo_code_date on foo
(cost=0.00..23996.55 rows=6355 width=20)
==========================================================================
=

So far, so good.  The index is properly used, and the query is
fast.  However, if I want to sort *descending* (which is really
what I want to do, to find the closest row with a date less than
a given date), then a full table scan is done:


==========================================================================
=
announce=# explain select date from foo where date < '06/08/2001
23:59' and code = 'FOO' order by code, date DESC limit 1;
NOTICE:  QUERY PLAN:

Limit  (cost=24397.98..24397.98 rows=1 width=20)
   ->  Sort  (cost=24397.98..24397.98 rows=6355 width=20)
         ->  Index Scan using foo_code_date on foo
(cost=0.00..23996.55 rows=6355 width=20)
==========================================================================
=

What can I do to improve this?

Might it help if I reversed the order of the fields in the
index?  There are only about 50 possible values for the 'code'
field.  I'm not sure which order is better in this case.  The
'date' field is well spread out over a year.

  -Ken


Re: Problem with indexes, LIMIT, ORDER BY ... DESC

From
"Nick Fankhauser"
Date:
Ken-

I'd suggest trying the index with the date first, or even indexing them
separately. Essentially, it looks like the index works as expected to
selected the candidate rows, but since date isn't the initial part of the
index, the index can't be used for the sort that must be done on the entire
set of candidates before the first one is selected.

BTW, I believe there is a "max" function that you might be able to use on
this. It may amount to the same operations as far as the planner goes, but
it gives you one more option to play with.

Regards,

-Nick

--------------------------------------------------------------------------
Nick Fankhauser  nickf@ontko.com  Phone 1.765.935.4283  Fax 1.765.962.9788
Ray Ontko & Co.     Software Consulting Services     http://www.ontko.com/


Re: Problem with indexes, LIMIT, ORDER BY ... DESC

From
Stephan Szabo
Date:
On Fri, 7 Jun 2002, Ken Williams wrote:

> ==========================================================================
> =
> announce=# explain select date from foo where date < '06/08/2001
> 23:59' and code = 'FOO' order by code, date DESC limit 1;
> NOTICE:  QUERY PLAN:
>
> Limit  (cost=24397.98..24397.98 rows=1 width=20)
>    ->  Sort  (cost=24397.98..24397.98 rows=6355 width=20)
>          ->  Index Scan using foo_code_date on foo
> (cost=0.00..23996.55 rows=6355 width=20)
> ==========================================================================
> =
>
> What can I do to improve this?

I'd suggest trying:  order by code DESC, date DESC.
Otherwise the index order and sort order aren't exactly alike.  In this
case there's only one code value so we can see that it shouldn't matter
but I doubt the optimizer knows that.


Re: Problem with indexes, LIMIT, ORDER BY ... DESC

From
Ken Williams
Date:
On Saturday, June 8, 2002, at 02:41  AM, Stephan Szabo wrote:

> On Fri, 7 Jun 2002, Ken Williams wrote:
>
>> ========================================================================
>> ==
>> =
>> announce=# explain select date from foo where date < '06/08/2001
>> 23:59' and code = 'FOO' order by code, date DESC limit 1;
>> NOTICE:  QUERY PLAN:
>>
>> Limit  (cost=24397.98..24397.98 rows=1 width=20)
>>    ->  Sort  (cost=24397.98..24397.98 rows=6355 width=20)
>>          ->  Index Scan using foo_code_date on foo
>> (cost=0.00..23996.55 rows=6355 width=20)
>> ========================================================================
>> ==
>> =
>>
>> What can I do to improve this?
>
> I'd suggest trying:  order by code DESC, date DESC.
> Otherwise the index order and sort order aren't exactly alike.  In this
> case there's only one code value so we can see that it shouldn't matter
> but I doubt the optimizer knows that.

Aha!  That was the problem - in my head I meant for the "DESC"
to apply to both "ORDER BY" fields, but I forgot that it only
applies one field at a time.  So I can do this:

================================================================
announce=# explain select date from foo where date <
'2000-06-02' and code='FOO' order by code desc, date desc limit
1;
NOTICE:  QUERY PLAN:

Limit  (cost=0.00..3.90 rows=1 width=20)
   ->  Index Scan Backward using foo_code_date on trades
(cost=0.00..10373.82 rows=2663 width=20)
================================================================

Thanks!

  -Ken