pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedThe usual sequential scan, but with LIMIT !
8+ messages / 4 participants
[nested] [flat]
* The usual sequential scan, but with LIMIT !
@ 2004-09-06 12:15 Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 12:27 ` Re: The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 12:45 ` Re: The usual sequential scan, but with LIMIT ! Dennis Bjorklund <db@zigo.dhs.org>
2004-09-06 16:40 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 3 replies; 8+ messages in thread
From: Pierre-Frédéric Caillaud @ 2004-09-06 12:15 UTC (permalink / raw)
To: pgsql-performance
Hello,
I have this table :
CREATE TABLE apparts
(
id SERIAL NOT NULL PRIMARY KEY,
price FLOAT NOT NULL,
surface INTEGER NOT NULL,
price_sq FLOAT NOT NULL,
rooms INTEGER NULL,
vente BOOL NOT NULL,
category TEXT NOT NULL,
zipcode INTEGER NOT NULL,
departement INTEGER NOT NULL
) WITHOUT OIDS;
There is a BTREE index on 'departement'.
The table fits in RAM.
When I want to SELECT according to my indexed field, postgres chooses a
sequential scan unless the number of rows to be returned is very, very
small :
apparts=> explain analyze select * from apparts where departement=42;
Seq Scan on apparts (cost=0.00..853.12 rows=1403 width=47) (actual
time=5.094..52.026 rows=1516 loops=1)
Filter: (departement = 42)
Total runtime: 52.634 ms
OK, it returns 1516 rows, so maybe the seq scan is right.
apparts=> SET enable_seqscan = 0;
apparts=> explain analyze select * from apparts where departement=42;
Index Scan using apparts_dept on apparts (cost=0.00..1514.59 rows=1403
width=47) (actual time=0.045..2.770 rows=1516 loops=1)
Index Cond: (departement = 42)
Total runtime: 3.404 ms
Um, 15 times faster...
Index scan is called only when there are few rows. With other values for
'departement' where there are few rows, the Index is used automatically.
This is logical, even if I should adjust the page costs. I wish I could
tell postgres "this table will fit in RAM and be accessed often, so for
this table, the page seek cost should be very low".
Everything is vacuum full analyze.
Now, if I LIMIT the query to 10 rows, the index should be used all the
time, because it will always return few rows... well, it doesn't !
apparts=> SET enable_seqscan = 1;
apparts=> explain analyze select * from apparts where departement=42 LIMIT
10;
Limit (cost=0.00..6.08 rows=10 width=47) (actual time=5.003..5.023
rows=10 loops=1)
-> Seq Scan on apparts (cost=0.00..853.12 rows=1403 width=47) (actual
time=4.998..5.013 rows=10 loops=1)
Filter: (departement = 42)
Total runtime: 5.107 ms
Now, let's try :
apparts=> SET enable_seqscan = 0;
apparts=> explain analyze select * from apparts where departement=42 LIMIT
10;
Limit (cost=0.00..10.80 rows=10 width=47) (actual time=0.047..0.072
rows=10 loops=1)
-> Index Scan using apparts_dept on apparts (cost=0.00..1514.59
rows=1403 width=47) (actual time=0.044..0.061 rows=10 loops=1)
Index Cond: (departement = 42)
Total runtime: 0.157 ms
So, by itself, Postgres will select a very bad query plan (32x slower) on
a query which would be executed very fast using indexes. If I use OFFSET
+ LIMIT, it only gets worse because the seq scan has to scan more rows :
apparts=> SET enable_seqscan = 1;
apparts=> explain analyze select * from apparts where departement=42 LIMIT
10 OFFSET 85;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Limit (cost=51.69..57.77 rows=10 width=47) (actual time=10.224..10.246
rows=10 loops=1)
-> Seq Scan on apparts (cost=0.00..853.12 rows=1403 width=47) (actual
time=5.254..10.200 rows=95 loops=1)
Filter: (departement = 42)
Total runtime: 10.326 ms
apparts=> SET enable_seqscan = 1;
apparts=> explain analyze select * from apparts where departement=42 LIMIT
10 OFFSET 1000;
Limit (cost=608.07..614.15 rows=10 width=47) (actual time=43.993..44.047
rows=10 loops=1)
-> Seq Scan on apparts (cost=0.00..853.12 rows=1403 width=47) (actual
time=5.328..43.791 rows=1010 loops=1)
Filter: (departement = 42)
Total runtime: 44.128 ms
apparts=> SET enable_seqscan = 0;
apparts=> explain analyze select * from apparts where departement=42 LIMIT
10 OFFSET 1000;
Limit (cost=1079.54..1090.33 rows=10 width=47) (actual time=2.147..2.170
rows=10 loops=1)
-> Index Scan using apparts_dept on apparts (cost=0.00..1514.59
rows=1403 width=47) (actual time=0.044..1.860 rows=1010 loops=1)
Index Cond: (departement = 42)
Total runtime: 2.259 ms
Why is it that way ? The planner should use the LIMIT values when
planning the query, should it not ?
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: The usual sequential scan, but with LIMIT !
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
@ 2004-09-06 12:27 ` Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2 siblings, 0 replies; 8+ messages in thread
From: Pierre-Frédéric Caillaud @ 2004-09-06 12:27 UTC (permalink / raw)
To: pgsql-performance
Update :
select * from apparts where departement=69 order by departement limit 10;
does use an index scan (because of the ORDER BY), even with OFFSET, and
it's a lot faster.
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: The usual sequential scan, but with LIMIT !
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
@ 2004-09-06 12:45 ` Dennis Bjorklund <db@zigo.dhs.org>
2 siblings, 0 replies; 8+ messages in thread
From: Dennis Bjorklund @ 2004-09-06 12:45 UTC (permalink / raw)
To: Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>; +Cc: pgsql-performance
On Mon, 6 Sep 2004, [iso-8859-15] Pierre-Frédéric Caillaud wrote:
> Why is it that way ? The planner should use the LIMIT values when
> planning the query, should it not ?
And it do use limit values, the estimated cost was lower when you had the
limit,
What you need to do is to tune pg for your computer. For example the
following settings:
* effective_cache - this setting tells pg how much the os are caching
(for example use top to find out during a normal work load). You said
that the tables fit in memory and by telling pg how much is cached it
might adjust it's plans accordingly.
* random_page_cost - how expensive is a random access compared to seq.
access. This is dependent on the computer and disk system you have.
If the setting above does not help, maybe you need to lower this to
variable to 2 or something.
And don't forget the shared_buffer setting. But most people usually have
it tuned in my experience (but usually too high). Here is an article that
might help you:
http://www.varlena.com/varlena/GeneralBits/Tidbits/perf.html
--
/Dennis Björklund
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: The usual sequential scan, but with LIMIT !
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
@ 2004-09-06 16:40 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 06:51 ` Re: The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2 siblings, 1 reply; 8+ messages in thread
From: Tom Lane @ 2004-09-06 16:40 UTC (permalink / raw)
To: Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>; +Cc: pgsql-performance
=?iso-8859-15?Q?Pierre-Fr=E9d=E9ric_Caillaud?= <lists@boutiquenumerique.com> writes:
> Now, if I LIMIT the query to 10 rows, the index should be used all the
> time, because it will always return few rows... well, it doesn't !
Not at all. From the planner's point of view, the LIMIT is going to
reduce the cost by about a factor of 10/1403, since the underlying plan
step will only be run partway through. That's not going to change the
decision about which underlying plan step is cheapest: 10/1403 of a
cheaper plan is still always less than 10/1403 of a more expensive plan.
Later, you note that LIMIT with ORDER BY does affect the plan choice
--- that's because in that situation one plan alternative has a much
higher startup cost than the other (namely the cost of a sort step).
A small LIMIT can allow the fast-startup plan to be chosen even though
it would be estimated to be the loser if run to completion.
regards, tom lane
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: The usual sequential scan, but with LIMIT !
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 16:40 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
@ 2004-09-07 06:51 ` Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-07 13:47 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 8+ messages in thread
From: Pierre-Frédéric Caillaud @ 2004-09-07 06:51 UTC (permalink / raw)
To: pgsql-performance
OK, thanks a lot for your explanations. Knowing how the planner "thinks",
makes it pretty logical. Thank you.
Now another question...
I have a table of records representing forum posts with a primary key
(id), a topic_id, a timestamp, and other fields which I won't detail. I
want to split them into pages (like forums usually do), with N posts per
page. In that case :
SELECT * FROM table WHERE topic_id=... ORDER BY post_timestamp asc LIMIT
N OFFSET N*page;
Also it's almost the same to order by id rather than post_timestamp (id
being a serial).
SELECT * FROM table WHERE topic_id=... ORDER BY id asc LIMIT N OFFSET
N*page;
This query runs slower and slower as the OFFSET grows, which is a problem
because the most accessed page in a forum is the last one.
So, for the last page, I tried :
SELECT * FROM table WHERE topic_id=... ORDER BY id desc LIMIT N;
But this does not use the index at all (seq scan + sort + limit).
My solution is simple : build an index on (-id), or on (some
date)-post_timestamp, then :
SELECT * FROM table WHERE topic_id=... ORDER BY (-id) desc LIMIT N;
Then the last page is the fastest one, but it always shows N posts.
That's not a problem, so I guess I'll use that. I don't like forums which
show 1 post on the last page because the number of posts modulo N is 1.
I may store the number of posts in a forum (updated by a trigger) to
avoid costly COUNT queries to count the pages, so I could use ORDER BY id
for the first half of the pages, and ORDER BY (-id) for the rest, so it
will always be fastest.
I could even create a pages table to store the id of the first post on
that page and then :
SELECT * FROM table WHERE topic_id=... AND id>id_of_first_post_in_page
ORDER BY id asc LIMIT N;
then all pages would be aqually fast.
Or, I could cache the query results for all pages but the last one.
Finally, the question : having a multiple field btree, it is not harder
to scan it in "desc order" than in "asc order". So why does not Postgres
do it ? Here is a btree example :
topic_id id
1 1
1 10
2 2
2 5
2 17
3 4
3 6
suppose I SELECT WHERE topic_id=2 ORDER BY topic_id ASC,id ASC.
Postgres simply finds the first row with topic_id=2 and goes from there.
suppose I SELECT WHERE topic_id=2 ORDER BY topic_id ASC,id DESC.
Postgres does a seq scan, but it could think a bit more and start at
"first index node which has topic_id>2" (simple to find in a btree) then
go backwards in the index. This can ge beneralized to any combination of
(asc,desc).
I made some more experiments, and saw Postgres does an 'Index Scan' when
ORDER BY clauses are all ASC, and an 'Index Scan Backwards' when all ORDER
BY are DESC. However, it does not handle a combination of ASC and DESC?
What do you think of this ?
On Mon, 06 Sep 2004 12:40:41 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> =?iso-8859-15?Q?Pierre-Fr=E9d=E9ric_Caillaud?=
> <lists@boutiquenumerique.com> writes:
>> Now, if I LIMIT the query to 10 rows, the index should be used all the
>> time, because it will always return few rows... well, it doesn't !
>
> Not at all. From the planner's point of view, the LIMIT is going to
> reduce the cost by about a factor of 10/1403, since the underlying plan
> step will only be run partway through. That's not going to change the
> decision about which underlying plan step is cheapest: 10/1403 of a
> cheaper plan is still always less than 10/1403 of a more expensive plan.
>
> Later, you note that LIMIT with ORDER BY does affect the plan choice
> --- that's because in that situation one plan alternative has a much
> higher startup cost than the other (namely the cost of a sort step).
> A small LIMIT can allow the fast-startup plan to be chosen even though
> it would be estimated to be the loser if run to completion.
>
> regards, tom lane
>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: Have you searched our list archives?
>
> http://archives.postgresql.org
>
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: The usual sequential scan, but with LIMIT !
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 16:40 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 06:51 ` Re: The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
@ 2004-09-07 13:47 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 14:30 ` Re: The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
0 siblings, 1 reply; 8+ messages in thread
From: Tom Lane @ 2004-09-07 13:47 UTC (permalink / raw)
To: Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>; +Cc: pgsql-performance
=?iso-8859-15?Q?Pierre-Fr=E9d=E9ric_Caillaud?= <lists@boutiquenumerique.com> writes:
> suppose I SELECT WHERE topic_id=2 ORDER BY topic_id ASC,id DESC.
> Postgres does a seq scan, but it could think a bit more and start at
> "first index node which has topic_id>2" (simple to find in a btree) then
> go backwards in the index.
If you write it as
SELECT WHERE topic_id=2 ORDER BY topic_id DESC,id DESC.
then an index on (topic_id, id) will work fine. The mixed ASC/DESC
ordering is not compatible with the index.
regards, tom lane
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: The usual sequential scan, but with LIMIT !
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 16:40 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 06:51 ` Re: The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-07 13:47 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
@ 2004-09-07 14:30 ` Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-07 16:54 ` Re: The usual sequential scan, but with LIMIT ! Gaetano Mendola <mendola@bigfoot.com>
0 siblings, 1 reply; 8+ messages in thread
From: Pierre-Frédéric Caillaud @ 2004-09-07 14:30 UTC (permalink / raw)
To: pgsql-performance
Yes, you're right as usual.
I had not thought about playing with ORDER BY on a field which has only
one value in the result set.
> If you write it as
> SELECT WHERE topic_id=2 ORDER BY topic_id DESC,id DESC.
> then an index on (topic_id, id) will work fine. The mixed ASC/DESC
> ordering is not compatible with the index.
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: The usual sequential scan, but with LIMIT !
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 16:40 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 06:51 ` Re: The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-07 13:47 ` Re: The usual sequential scan, but with LIMIT ! Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 14:30 ` Re: The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
@ 2004-09-07 16:54 ` Gaetano Mendola <mendola@bigfoot.com>
0 siblings, 0 replies; 8+ messages in thread
From: Gaetano Mendola @ 2004-09-07 16:54 UTC (permalink / raw)
To: Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
Pierre-Frédéric Caillaud wrote:
>
> Yes, you're right as usual.
As usual ? Do you think your father can be wrong on you ? :-)
Gaetano
^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2004-09-07 16:54 UTC | newest]
Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2004-09-06 12:15 The usual sequential scan, but with LIMIT ! Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 12:27 ` Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-06 12:45 ` Dennis Bjorklund <db@zigo.dhs.org>
2004-09-06 16:40 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 06:51 ` Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-07 13:47 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-09-07 14:30 ` Pierre-Frédéric Caillaud <lists@boutiquenumerique.com>
2004-09-07 16:54 ` Gaetano Mendola <mendola@bigfoot.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox