Thread: select distinct and index usage
I have a reasonably large table (~75m rows,~18gb) called "vals". It
includes an integer datestamp column with approximately 4000 unique
entries across the rows; there is a normal btree index on the
datestamp column. When I attempt something like "select distinct
datestamp from vals", however, explain tells me it's doing a
sequential scan:
explain select distinct datestamp from vals;
QUERY PLAN
--------------------------------------------------------------------------------------
Unique (cost=15003047.47..15380004.83 rows=4263 width=4)
-> Sort (cost=15003047.47..15191526.15 rows=75391472 width=4)
Sort Key: datestamp
-> Seq Scan on vals v (cost=0.00..1531261.72 rows=75391472 width=4)
On another table in the same database with a much smaller number of
total rows (~15m rows), I have the exact same situation- but in this
case the index on the datestamp column *is* used:
explain select distinct datestamp from sdays;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
Unique (cost=0.00..974675.99 rows=4254 width=4)
-> Index Scan using sdays_datestamp_idx on sdays
(cost=0.00..932822.79 rows=16741280 width=4)
Any help on why the index isn't being used, or how I can set up the
index/query to make use of the index rather than doing an 18gb
sequential scan, would be very much appreciated.
--
- David T. Wilson
Princeton Satellite Systems
david.t.wilson@gmail.com
David Wilson wrote: > On another table in the same database with a much smaller number of > total rows (~15m rows), I have the exact same situation- but in this > case the index on the datestamp column *is* used: > Have you run ANALYZE on both tables? It might be worth increasing the stats collected on the datestamp column (or all columns in the table), re-running ANALYZE on the table, and seeing what happens. Also, is there any chance that that's a lot more variation in datestamp values in your problem table than the one where the index is used? -- Craig Ringer
Both tables are vacuumed and analyzed. I have other queries that are using various indices on the vals table in an intelligent fashion. I can try increasing the stats, certainly, although they're at the defaults for both tables. The variation is definitely identical- the set of datestamps in the vals table is a large (~98%) subset of the set of datestamps in the sdays table. Of the approximately 4000 distinct datestamps, there are 80 that appear in the sdays table and not in the vals table. On Sun, Apr 6, 2008 at 10:20 PM, Craig Ringer <craig@postnewspapers.com.au> wrote: > David Wilson wrote: > > > On another table in the same database with a much smaller number of > > total rows (~15m rows), I have the exact same situation- but in this > > case the index on the datestamp column *is* used: > > > > > Have you run ANALYZE on both tables? > > It might be worth increasing the stats collected on the datestamp column > (or all columns in the table), re-running ANALYZE on the table, and seeing > what happens. > > Also, is there any chance that that's a lot more variation in datestamp > values in your problem table than the one where the index is used? > > -- > Craig Ringer > -- - David T. Wilson Princeton Satellite Systems david.t.wilson@gmail.com
On Apr 7, 2008, at 1:32 AM, David Wilson wrote: > I have a reasonably large table (~75m rows,~18gb) called "vals". It > includes an integer datestamp column with approximately 4000 unique > entries across the rows; there is a normal btree index on the > datestamp column. When I attempt something like "select distinct > datestamp from vals", however, explain tells me it's doing a > sequential scan: > > explain select distinct datestamp from vals; > QUERY PLAN > ---------------------------------------------------------------------- > ---------------- > Unique (cost=15003047.47..15380004.83 rows=4263 width=4) > -> Sort (cost=15003047.47..15191526.15 rows=75391472 width=4) > Sort Key: datestamp > -> Seq Scan on vals v (cost=0.00..1531261.72 > rows=75391472 width=4) The databases estimates seem consistent with yours, so why is it doing this? Could you provide an EXPLAIN ANALYSE? It shows the actual numbers next to the estimates, although I figure that query might take a while... Pg estimates the costs quite high too. It's almost as if there isn't an index on that column and it has no other way then doing a sequential scan... Could you show us the table definition and its indexes? What version of Pg is this? It may be that your index on vals.datestamp doesn't fit into memory; what are the relevant configuration parameters for your database? Regards, Alban Hertroys -- If you can't see the forest for the trees, cut the trees and you'll see there is no forest. !DSPAM:737,47f9b995927662100729983!
On Mon, Apr 7, 2008 at 2:05 AM, Alban Hertroys
<dalroi@solfertje.student.utwente.nl> wrote:
> On Apr 7, 2008, at 1:32 AM, David Wilson wrote:
>
> >
>
> The databases estimates seem consistent with yours, so why is it doing
> this? Could you provide an EXPLAIN ANALYSE? It shows the actual numbers next
> to the estimates, although I figure that query might take a while...
explain analyze select distinct datestamp from vals;
QUERY
PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=15003047.47..15380004.83 rows=4263 width=4) (actual
time=649599.159..721671.595 rows=4252 loops=1)
-> Sort (cost=15003047.47..15191526.15 rows=75391472 width=4)
(actual time=649599.157..694392.602 rows=75391476 loops=1)
Sort Key: datestamp
Sort Method: external merge Disk: 1178592kB
-> Seq Scan on vals (cost=0.00..1531261.72 rows=75391472
width=4) (actual time=9.104..93130.468 rows=75391476 loops=1)
Total runtime: 722379.434 ms
(There were a couple other very long-running, disk-intensive queries
going on in the background of this, so that runtime is a little
inflated, but the values should still all be relevant.)
> Pg estimates the costs quite high too. It's almost as if there isn't an
> index on that column and it has no other way then doing a sequential scan...
> Could you show us the table definition and its indexes? What version of Pg
> is this?
Pg is 8.3.1
Table definition:
CREATE TABLE vals (
sid integer NOT NULL,
eid integer NOT NULL,
datestamp integer NOT NULL,
val_dur integer NOT NULL,
acc real NOT NULL,
yld real NOT NULL,
rt real NOT NULL,
ydev real NOT NULL,
vydev real NOT NULL,
adev real NOT NULL,
achange real NOT NULL,
ychange real NOT NULL,
arsi real NOT NULL,
yrsi real NOT NULL,
UNIQUE (sid,eid,val_dur,datestamp),
FOREIGN KEY (sid,eid,datestamp) REFERENCES preds
(sid,eid,datestamp) ON DELETE CASCADE
);
create index val_datestamp_idx on vals(datestamp);
create index val_evaluator_idx on vals(eid);
create index val_search_key on vals(val_dur,eid,datestamp);
create index val_vd_idx on vals(val_dur,datestamp);
(The various indices are for a variety of common queries into the table)
> It may be that your index on vals.datestamp doesn't fit into memory; what
> are the relevant configuration parameters for your database?
That's a very good question. I recently had to rebuild this particular
database and haven't played with the configuration parameters as much
as I'd like- what parameters would be most relevant here? I hadn't
realized that an index needed to fit into memory.
pg_total_relation_size('vals') - pg_relation_size('vals') gives 11gb.
All indexed columns are integers. My guess is that this means that
it's likely the index doesn't fit into memory.
--
- David T. Wilson
Princeton Satellite Systems
david.t.wilson@gmail.com
On Apr 7, 2008, at 9:47 AM, David Wilson wrote: > On Mon, Apr 7, 2008 at 2:05 AM, Alban Hertroys > <dalroi@solfertje.student.utwente.nl> wrote: >> The databases estimates seem consistent with yours, so why is it >> doing >> this? Could you provide an EXPLAIN ANALYSE? It shows the actual >> numbers next >> to the estimates, although I figure that query might take a while... > > explain analyze select distinct datestamp from vals; > QUERY > PLAN > ---------------------------------------------------------------------- > ------------------------------------------------------------------- > Unique (cost=15003047.47..15380004.83 rows=4263 width=4) (actual > time=649599.159..721671.595 rows=4252 loops=1) > -> Sort (cost=15003047.47..15191526.15 rows=75391472 width=4) > (actual time=649599.157..694392.602 rows=75391476 loops=1) > Sort Key: datestamp > Sort Method: external merge Disk: 1178592kB > -> Seq Scan on vals (cost=0.00..1531261.72 rows=75391472 > width=4) (actual time=9.104..93130.468 rows=75391476 loops=1) > Total runtime: 722379.434 ms Wow, great estimates! The planner obviously knows how your data is structured. So much for the bad planner estimation scenario... I haven't seen this "external merge Disk"-sort method before, maybe it's new in 8.3, but it doesn't look promising for query performance. Considering it's using 1.1GB it seems the planner may have chosen for the least memory exhaustive method; I have to admit I don't know the planner in that much detail. Take this with a grain of salt, but my guess is that as the index is even bigger, the planner figures this approach would involve the least disk i/o and will therefore be faster. Have you tried this query with enable_seqscan=off? If my guess is right (and the planners, in that case) it'd be even slower. Something that might help you, but I'm not sure whether it might hurt the performance of other queries, is to cluster that table on val_datestamp_idx. That way the records are already (mostly) sorted on disk in the order of the datestamps, which seems to be the brunt of above query plan. >> Pg estimates the costs quite high too. It's almost as if there >> isn't an >> index on that column and it has no other way then doing a >> sequential scan... >> Could you show us the table definition and its indexes? What >> version of Pg >> is this? > > Pg is 8.3.1 > > Table definition: > CREATE TABLE vals ( > sid integer NOT NULL, > eid integer NOT NULL, > datestamp integer NOT NULL, > val_dur integer NOT NULL, > acc real NOT NULL, > yld real NOT NULL, > rt real NOT NULL, > ydev real NOT NULL, > vydev real NOT NULL, > adev real NOT NULL, > achange real NOT NULL, > ychange real NOT NULL, > arsi real NOT NULL, > yrsi real NOT NULL, > UNIQUE (sid,eid,val_dur,datestamp), > FOREIGN KEY (sid,eid,datestamp) REFERENCES preds > (sid,eid,datestamp) ON DELETE CASCADE > ); > create index val_datestamp_idx on vals(datestamp); > create index val_evaluator_idx on vals(eid); > create index val_search_key on vals(val_dur,eid,datestamp); > create index val_vd_idx on vals(val_dur,datestamp); There seems to be quite a bit of overlap in your index definitions. From my experience this can confuse the planner. I suggest you combine them, but not knowing your data... Maybe rewriting your UNIQUE constraint to (val_dur, datestamp, eid, sid) would be enough to replace all those other indexes. If not, it's probably better to have one index per column, so that the planner is free to combine them as it sees fit. That'd result in a bitmap index scan, btw. > (The various indices are for a variety of common queries into the > table) > >> It may be that your index on vals.datestamp doesn't fit into >> memory; what >> are the relevant configuration parameters for your database? > > That's a very good question. I recently had to rebuild this particular > database and haven't played with the configuration parameters as much > as I'd like- what parameters would be most relevant here? I hadn't > realized that an index needed to fit into memory. Well, it doesn't _need_ to fit into memory, but if the database needs to fetch different parts of it from disk or swap, the costs of using the index will sear up. Especially random access would be bad. Anything that fits entirely into memory will be faster than having to fetch it from disk, as long as it doesn't mean other things will have to come from disk instead. I'm not a postgresql tuning expert (I know my way around though), other people can explain you way better than I can. Bruce Momjian for example: http://www.linuxjournal.com/article/4791 > pg_total_relation_size('vals') - pg_relation_size('vals') gives 11gb. > All indexed columns are integers. My guess is that this means that > it's likely the index doesn't fit into memory. That calculation doesn't look familiar to me, I'm more used to: select pg_size_pretty(pg_relation_size('...')); You can put the name of any relation in there, be it tables, indexes, etc. 11GB is pretty large for an index on an integer column, especially with only 75M rows: that's 146 bytes/row in your index. Maybe your index got bloated somehow? I think it should be about a tenth of that. Regards, Alban Hertroys -- If you can't see the forest for the trees, cut the trees and you'll see there is no forest. !DSPAM:737,47fa5cf0927661607113844!
On Mon, 7 Apr 2008 19:42:02 +0200 Alban Hertroys <dalroi@solfertje.student.utwente.nl> wrote: > > explain analyze select distinct datestamp from vals; > > QUERY > > PLAN > > ---------------------------------------------------------------------- > > ------------------------------------------------------------------- > > Unique (cost=15003047.47..15380004.83 rows=4263 width=4) (actual > > time=649599.159..721671.595 rows=4252 loops=1) > > -> Sort (cost=15003047.47..15191526.15 rows=75391472 width=4) > > (actual time=649599.157..694392.602 rows=75391476 loops=1) > > Sort Key: datestamp > > Sort Method: external merge Disk: 1178592kB > > -> Seq Scan on vals (cost=0.00..1531261.72 rows=75391472 > > width=4) (actual time=9.104..93130.468 rows=75391476 loops=1) > > Total runtime: 722379.434 ms > > Wow, great estimates! The planner obviously knows how your data is > structured. So much for the bad planner estimation scenario... > > I haven't seen this "external merge Disk"-sort method before, maybe > it's new in 8.3, but it doesn't look promising for query I have to double check but I think that means he overflowed his work mem and is sorting on disk. Try increasing workmem for the query. Joshua D. Drake -- The PostgreSQL Company since 1997: http://www.commandprompt.com/ PostgreSQL Community Conference: http://www.postgresqlconference.org/ United States PostgreSQL Association: http://www.postgresql.us/ Donate to the PostgreSQL Project: http://www.postgresql.org/about/donate
On Mon, Apr 7, 2008 at 1:42 PM, Alban Hertroys
<dalroi@solfertje.student.utwente.nl> wrote:
>
> Have you tried this query with enable_seqscan=off? If my guess is right
> (and the planners, in that case) it'd be even slower.
set enable_seqscan=off;
explain select distinct datestamp from vals;
QUERY PLAN
----------------------------------------------------------------------------------------------
Unique (cost=115003047.47..115380004.83 rows=4263 width=4)
-> Sort (cost=115003047.47..115191526.15 rows=75391472 width=4)
Sort Key: datestamp
-> Seq Scan on vals (cost=100000000.00..101531261.72
rows=75391472 width=4)
It appears to be doing a sequential scan regardless of the set, as if
it doesn't believe it can use the index for some reason
>
> Something that might help you, but I'm not sure whether it might hurt the
> performance of other queries, is to cluster that table on val_datestamp_idx.
> That way the records are already (mostly) sorted on disk in the order of the
> datestamps, which seems to be the brunt of above query plan.
That's a good thought. I'll give that a try this evening when the DB
has some downtime and see what happens.
>
> There seems to be quite a bit of overlap in your index definitions. From my
> experience this can confuse the planner.
>
> I suggest you combine them, but not knowing your data... Maybe rewriting
> your UNIQUE constraint to (val_dur, datestamp, eid, sid) would be enough to
> replace all those other indexes.
> If not, it's probably better to have one index per column, so that the
> planner is free to combine them as it sees fit. That'd result in a bitmap
> index scan, btw.
I can take a look at the other indices again, but those are all in
place for specific other queries that generally involve some set of
a=1, b=2, c=3, datestamp>5 type of where-clause and were created
specifically in response to sequential scans showing up in other
queries (and had the proper effect of fixing them!)
>
> I'm not a postgresql tuning expert (I know my way around though), other
> people can explain you way better than I can. Bruce Momjian for example:
> http://www.linuxjournal.com/article/4791
I'll take a look at that, thanks.
> That calculation doesn't look familiar to me, I'm more used to:
> select pg_size_pretty(pg_relation_size('...'));
>
> You can put the name of any relation in there, be it tables, indexes, etc.
>
> 11GB is pretty large for an index on an integer column, especially with
> only 75M rows: that's 146 bytes/row in your index. Maybe your index got
> bloated somehow? I think it should be about a tenth of that.
pg_total_relation_size('..') gives the number of bytes for the table +
all associated indices; pg_relation_size('..') gives for just the
table. The difference between the two should be total bytes take up by
the 5 total indices (11 total index cols), giving a
back-of-the-envelope estimation of 1gb for the size of the datestamp
index. I am fairly certain that I didn't give pg 1gb to fit the index
in memory, so I'll try upping its total available memory tonight and
see if that doesn't improve things.
I appreciate the responses so far! I'm used to several minutes for
some of the complex queries on this DB, but 12.5 minutes for a select
distinct just seems wrong. :)
--
- David T. Wilson
Princeton Satellite Systems
david.t.wilson@gmail.com
"David Wilson" <david.t.wilson@gmail.com> writes: > I appreciate the responses so far! I'm used to several minutes for > some of the complex queries on this DB, but 12.5 minutes for a select > distinct just seems wrong. :) You could try changing it to the equivalent GROUP BY query. The planner, unfortunately, doesn't know they're equivalent and has two separate sets of plans available. In this case where there are only 4,000 distinct values out of 75M original records you might find a HashAggregate plan, which the planner doesn't know can be used for DISTINCT, best. You might have to raise work_mem before the planner feels a hash will fit. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's RemoteDBA services!
On Mon, Apr 7, 2008 at 7:57 PM, Gregory Stark <stark@enterprisedb.com> wrote: > > You could try changing it to the equivalent GROUP BY query. The planner, > unfortunately, doesn't know they're equivalent and has two separate sets of > plans available. In this case where there are only 4,000 distinct values out > of 75M original records you might find a HashAggregate plan, which the planner > doesn't know can be used for DISTINCT, best. You might have to raise work_mem > before the planner feels a hash will fit. > > -- > Gregory Stark > EnterpriseDB http://www.enterprisedb.com > Ask me about EnterpriseDB's RemoteDBA services! > Progress! explain analyze select datestamp from vals group by datestamp; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------ HashAggregate (cost=1719740.40..1719783.03 rows=4263 width=4) (actual time=120192.018..120193.930 rows=4252 loops=1) -> Seq Scan on vals (cost=0.00..1531261.72 rows=75391472 width=4) (actual time=17.441..66807.429 rows=75391476 loops=1) Total runtime: 120195.144 ms Compared with: explain analyze select distinct datestamp from vals; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------- Unique (cost=15003047.47..15380004.83 rows=4263 width=4) (actual time=649599.159..721671.595 rows=4252 loops=1) -> Sort (cost=15003047.47..15191526.15 rows=75391472 width=4) (actual time=649599.157..694392.602 rows=75391476 loops=1) Sort Key: datestamp Sort Method: external merge Disk: 1178592kB -> Seq Scan on vals (cost=0.00..1531261.72 rows=75391472 width=4) (actual time=9.104..93130.468 rows=75391476 loops=1) Total runtime: 722379.434 ms Still doing the sequential scan on the table, but at least it's avoiding the expensive disk merge sort. It still seems as if I ought to be able to coax it into using an index for this type of query, though- especially since it's using one on the other table. Is there perhaps some way to reformulate the index in such a way as to make it more useful to the planner? -- - David T. Wilson Princeton Satellite Systems david.t.wilson@gmail.com
David Wilson escribió: > explain analyze select datestamp from vals group by datestamp; > QUERY > PLAN > ------------------------------------------------------------------------------------------------------------------------------------ > HashAggregate (cost=1719740.40..1719783.03 rows=4263 width=4) > (actual time=120192.018..120193.930 rows=4252 loops=1) > -> Seq Scan on vals (cost=0.00..1531261.72 rows=75391472 width=4) > (actual time=17.441..66807.429 rows=75391476 loops=1) > Total runtime: 120195.144 ms > Still doing the sequential scan on the table, but at least it's > avoiding the expensive disk merge sort. It still seems as if I ought > to be able to coax it into using an index for this type of query, > though- especially since it's using one on the other table. Is there > perhaps some way to reformulate the index in such a way as to make it > more useful to the planner? Hmm, why do you think an indexscan would be faster? Since there's no sort step involved, a seqscan as input for the HashAggregate is actually better than an indexscan, because there's no need for the index entries at all. If you want to test, try SET enable_seqscan TO 0 and then rerun the explain analyze. My bet is that it will use the index, and it will take longer. -- Alvaro Herrera http://www.CommandPrompt.com/ The PostgreSQL Company - Command Prompt, Inc.
> Still doing the sequential scan on the table, but at least it's
> avoiding the expensive disk merge sort. It still seems as if I ought
> to be able to coax it into using an index for this type of query,
> though- especially since it's using one on the other table. Is there
> perhaps some way to reformulate the index in such a way as to make it
> more useful to the planner?
You're asking postgres to examine EVERY visible row (hence the sequential scan makes good sense), and tell you what
fieldvalues there are.
You may be able to make use of an index by rearranging your query to generate a series between your min & max values,
testingwhether each value is in your table.
You've got 4252 distinct values, but what is the range of max - min? Say it's 5000 values, you'd do 5000 lookups via an
index,unless postgres thought that the number of index based lookups where going to be more expensive than reading the
entiretable.
Regards,
Stephen Denne.
Disclaimer:
At the Datamail Group we value team commitment, respect, achievement, customer focus, and courage. This email with any
attachmentsis confidential and may be subject to legal privilege. If it is not intended for you please advise by reply
immediately,destroy it and do not copy, disclose or use it in any way.
__________________________________________________________________
This email has been scanned by the DMZGlobal Business Quality
Electronic Messaging Suite.
Please see http://www.dmzglobal.com/dmzmessaging.htm for details.
__________________________________________________________________
"David Wilson" <david.t.wilson@gmail.com> writes:
> It appears to be doing a sequential scan regardless of the set, as if
> it doesn't believe it can use the index for some reason
More likely, it's getting a cost estimate for the indexscan that's so
bad that it even exceeds the 100000000-unit thumb on the scales that's
inserted by enable_seqscan=off.
You could try setting enable_sort=off also, which'd give you another
100000000 worth of thumb on the scales. And if that doesn't help,
reduce random_page_cost to 1 or even less.
What I think you'll find, though, is that once you do force an indexscan
to be picked it'll be slower. Full-table index scans are typically
worse than seqscan+sort, unintuitive though that may sound.
regards, tom lane
Tom Lane escribió: > What I think you'll find, though, is that once you do force an indexscan > to be picked it'll be slower. Full-table index scans are typically > worse than seqscan+sort, unintuitive though that may sound. Hmm, should we switch the CLUSTER code to do that? -- Alvaro Herrera http://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support
Alvaro Herrera <alvherre@commandprompt.com> writes:
> Tom Lane escribi�:
>> What I think you'll find, though, is that once you do force an indexscan
>> to be picked it'll be slower. Full-table index scans are typically
>> worse than seqscan+sort, unintuitive though that may sound.
> Hmm, should we switch the CLUSTER code to do that?
It's been suggested before, but I'm not sure. The case where an
indexscan can win is where the table is roughly in index order already.
So if you think about periodic CLUSTER to maintain table ordering,
I suspect you'd want the indexscan implementation for all but maybe
the first time.
regards, tom lane
Alban Hertroys wrote
> Something that might help you, but I'm not sure whether it
> might hurt
> the performance of other queries, is to cluster that table on
> val_datestamp_idx. That way the records are already (mostly) sorted
> on disk in the order of the datestamps, which seems to be the brunt
> of above query plan.
I've a question about this suggestion, in relation to what the cost estimation calculation does, or could possibly do:
If there are 4000 distinct values in the index, found randomly amongst 75 million rows, then you might be able to check
thevisibility of all those index values through reading a smaller number of disk pages than if the table was clustered
bythat index.
As an example, say there are 50 rows per page, at a minimum you could be very lucky and determine that they where all
visiblethrough reading only 80 data pages. More likely you'd be able to determine that through a few hundred pages. If
thetable was clustered by an index on that field, you'd have to read 4000 pages.
Is this question completely unrelated to PostgreSQL implementation reality, or something worth considering?
Regards,
Stephen Denne.
Disclaimer:
At the Datamail Group we value team commitment, respect, achievement, customer focus, and courage. This email with any
attachmentsis confidential and may be subject to legal privilege. If it is not intended for you please advise by reply
immediately,destroy it and do not copy, disclose or use it in any way.
__________________________________________________________________
This email has been scanned by the DMZGlobal Business Quality
Electronic Messaging Suite.
Please see http://www.dmzglobal.com/dmzmessaging.htm for details.
__________________________________________________________________
On Sun, Apr 06, 2008 at 07:32:58PM -0400, David Wilson wrote:
> I have a reasonably large table (~75m rows,~18gb) called "vals". It
> includes an integer datestamp column with approximately 4000 unique
> entries across the rows; there is a normal btree index on the
> datestamp column. When I attempt something like "select distinct
> datestamp from vals", however, explain tells me it's doing a
> sequential scan:
I'm a bit late to the party, but someone had a similar problem a while
back and solved it with an SRF as follows (pseudo-code):
BEGIN
curr := (SELECT field FROM table ORDER BY field LIMIT 1 )
RETURN NEXT curr;
WHILE( curr )
curr := (SELECT field FROM table WHERE field > curr ORDER BY field LIMIT 1 )
RETURN NEXT curr;
END
END
If you have 5000 unique values it will do 5000 index lookup which would
be bad except it's better than 75 million rows as is in your case.
Whether it's faster is something you'll have to test, but it's another
approach to the problem.
Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> Please line up in a tree and maintain the heap invariant while
> boarding. Thank you for flying nlogn airlines.
Attachment
On Mon, Apr 7, 2008 at 9:11 PM, Stephen Denne
<Stephen.Denne@datamail.co.nz> wrote:
>
> You may be able to make use of an index by rearranging your query to generate a series between your min & max
values,testing whether each value is in your table.
>
> You've got 4252 distinct values, but what is the range of max - min? Say it's 5000 values, you'd do 5000 lookups via
anindex, unless postgres thought that the number of index based lookups where going to be more expensive than reading
theentire table.
Upon further investigation, the above works very well:
explain analyze select ds from (select generate_series((select
datestamp from vals order by datestamp asc limit 1), (select datestamp
from vals order by datestamp desc limit 1), 86400) as ds) series where
exists (select datestamp from vals where datestamp=ds);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Subquery Scan series (cost=4.89..8.90 rows=1 width=4) (actual
time=0.080..25264.239 rows=4252 loops=1)
Filter: (subplan)
-> Result (cost=4.89..4.90 rows=1 width=0) (actual
time=0.051..7.491 rows=6163 loops=1)
InitPlan
-> Limit (cost=0.00..2.45 rows=1 width=4) (actual
time=0.023..0.024 rows=1 loops=1)
-> Index Scan using val_datestamp_idx on vals
(cost=0.00..184401441.14 rows=75391472 width=4) (actual
time=0.021..0.021 rows=1 loops=1)
-> Limit (cost=0.00..2.45 rows=1 width=4) (actual
time=0.020..0.020 rows=1 loops=1)
-> Index Scan Backward using val_datestamp_idx on
validations (cost=0.00..184401441.14 rows=75391472 width=4) (actual
time=0.018..0.018 rows=1 loops=1)
SubPlan
-> Index Scan using val_datestamp_idx on validations
(cost=0.00..70453.21 rows=17685 width=4) (actual time=4.096..4.096
rows=1 loops=6163)
Index Cond: (datestamp = $0)
Total runtime: 25267.033 ms
(12 rows)
The series generates all the possible datestamps + about 40% extra.
What's particularly interesting here to me is that it at least seems
like this validates my original assumption that if the planner could
be coaxed into using the index it would be faster- or am I missing
something? This query, at 25 seconds, was certainly much faster than
even the GROUP BY version that ran in 120 seconds.
As before, thanks for all of the information and ideas. Down from 722
seconds to 25 seconds is a hefty improvement.
--
- David T. Wilson
Princeton Satellite Systems
david.t.wilson@gmail.com
"Tom Lane" <tgl@sss.pgh.pa.us> writes: > Alvaro Herrera <alvherre@commandprompt.com> writes: >> Tom Lane escribió: >>> What I think you'll find, though, is that once you do force an indexscan >>> to be picked it'll be slower. Full-table index scans are typically >>> worse than seqscan+sort, unintuitive though that may sound. The original poster's implicit expectation is that an index scan would be faster because it shouldn't have to visit every tuple. Once it's found a tuple with a particular value it should be able to use the index to skip to the next key value. I thought our DISTINCT index scan does do that but it still has to read the index leaf pages sequentially. It doesn't back-track up the tree structure and refind the next key. >> Hmm, should we switch the CLUSTER code to do that? > > It's been suggested before, but I'm not sure. The case where an > indexscan can win is where the table is roughly in index order already. > So if you think about periodic CLUSTER to maintain table ordering, > I suspect you'd want the indexscan implementation for all but maybe > the first time. I think we would push a query through the planner to choose the best plan based on the statistics. I'm not sure how this would play with the visibility rules -- iirc not all scan types can be used with all visibility modes. And also I'm not sure how Heikki's MVCC-safe cluster would work if it's not sure what order it's scanning the heap. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's Slony Replication support!
Gregory Stark escribió: > I thought our DISTINCT index scan does do that but it still has to read the > index leaf pages sequentially. It doesn't back-track up the tree structure and > refind the next key. The way to back-track is to start the scan over from the root page down, keeping a stack of parent pages as you go down (mainly because we need to lock them in order, topmost first). So it's not a particularly cheap operation. I'm not sure the situation with thousands of equal keys is common enough to warrant adding all the code that would be needed to implement the kind of "distinct scan" that you suggest, even though it certainly is a nice idea. -- Alvaro Herrera http://www.CommandPrompt.com/ The PostgreSQL Company - Command Prompt, Inc.