pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedcount(*), EXISTS, indexes
14+ messages / 4 participants
[nested] [flat]
* count(*), EXISTS, indexes
@ 2003-04-11 20:39 Itai Zukerman <zukerman@math-hat.com>
0 siblings, 3 replies; 14+ messages in thread
From: Itai Zukerman @ 2003-04-11 20:39 UTC (permalink / raw)
To: pgsql-sql
Define:
CREATE TABLE A (x int PRIMARY KEY, real v);
CREATE TABLE B (x int);
I'd like to calculate:
SELECT sum(v) FROM A WHERE EXISTS (SELECT 1 FROM B WHERE A.x=B.x);
...but then it won't use the primary key index on A.x.
It *will* use the index with:
SELECT sum(A.v) FROM A,B WHERE A.x=B.x;
...but that's not the same thing. This is soooo close:
SELECT count(DISTINCT A.x) FROM A,B WHERE A.x=B.x;
Am I going to have to write a plpgsql function for this?
PS. B is relatively small, a few thousand rows, while A has well over
500,000 rows. The DISTINCT A.x should be about 10,000-50,000.
--
Itai Zukerman <http://www.math-hat.com/~zukerman/;
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 20:53 Josh Berkus <josh@agliodbs.com>
parent: Itai Zukerman <zukerman@math-hat.com>
2 siblings, 1 reply; 14+ messages in thread
From: Josh Berkus @ 2003-04-11 20:53 UTC (permalink / raw)
To: Itai Zukerman <zukerman@math-hat.com>; pgsql-sql
Itai,
Interesting. Can you post your Postges version, and EXPLAIN ANALYZE for each
of those queries?
--
-Josh Berkus
Aglio Database Solutions
San Francisco
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 21:06 Itai Zukerman <zukerman@math-hat.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 14+ messages in thread
From: Itai Zukerman @ 2003-04-11 21:06 UTC (permalink / raw)
To: josh@agliodbs.com; +Cc: pgsql-sql
> Interesting. Can you post your Postges version, and EXPLAIN ANALYZE for each
> of those queries?
Sure.
Here's what I want:
# explain select sum(weight) from rprofile rp where exists (select 1 from rcount_prof rcp where rcp.profile ~<= rp.profile and ~rcp.psig ~<= rp.psig and rcp.filter='{734,1944}');
QUERY PLAN
----------------------------------------------------------------------------------------------------
Aggregate (cost=1544943.75..1544943.75 rows=1 width=4)
-> Seq Scan on rprofile rp (cost=0.00..1544255.00 rows=275500 width=4)
Filter: (subplan)
SubPlan
-> Seq Scan on rcount_prof rcp (cost=0.00..2.70 rows=1 width=0)
Filter: ((profile ~<= $0) AND ((~ psig) ~<= $1) AND (filter = '{734,1944}'::text))
Here's a version that uses the index, but over-counts:
# explain analyze select sum(weight) from rprofile rp, rcount_prof rcp where rcp.profile ~<= rp.profile and ~rcp.psig ~<= rp.psig and rcp.filter='{734,1944}';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=2245.07..2245.07 rows=1 width=1001) (actual time=1183.53..1183.53 rows=1 loops=1)
-> Nested Loop (cost=0.00..2245.06 rows=1 width=1001) (actual time=0.44..1156.98 rows=23338 loops=1)
Join Filter: ("outer".profile ~<= "inner".profile)
-> Seq Scan on rcount_prof rcp (cost=0.00..2.44 rows=1 width=287) (actual time=0.08..0.17 rows=1 loops=1)
Filter: (filter = '{734,1944}'::text)
-> Index Scan using rprofile_profile_idx on rprofile rp (cost=0.00..2232.98 rows=551 width=714) (actual time=0.25..1083.15 rows=23385 loops=1)
Index Cond: ((~ "outer".psig) ~<= rp.psig)
Total runtime: 1183.67 msec
$ psql --version
psql (PostgreSQL) 7.3.2
Running on RedHat.
(It takes a long time to run the first select, so I left off the
analyze.)
--
Itai Zukerman <http://www.math-hat.com/~zukerman/;
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 21:10 Tom Lane <tgl@sss.pgh.pa.us>
parent: Itai Zukerman <zukerman@math-hat.com>
2 siblings, 1 reply; 14+ messages in thread
From: Tom Lane @ 2003-04-11 21:10 UTC (permalink / raw)
To: Itai Zukerman <zukerman@math-hat.com>; +Cc: pgsql-sql
Itai Zukerman <zukerman@math-hat.com> writes:
> Define:
> CREATE TABLE A (x int PRIMARY KEY, real v);
> CREATE TABLE B (x int);
> I'd like to calculate:
> SELECT sum(v) FROM A WHERE EXISTS (SELECT 1 FROM B WHERE A.x=B.x);
> ...but then it won't use the primary key index on A.x.
In CVS tip (7.4-to-be) I think
SELECT sum(v) FROM A WHERE A.x IN (SELECT B.x FROM B);
would probably work well. In current releases I think all you can do is
add an index to B.x and settle for the EXISTS() approach.
> PS. B is relatively small, a few thousand rows, while A has well over
> 500,000 rows. The DISTINCT A.x should be about 10,000-50,000.
BTW, how can a PRIMARY KEY column have fewer DISTINCT values than there
are rows?
regards, tom lane
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 21:22 Itai Zukerman <zukerman@math-hat.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 14+ messages in thread
From: Itai Zukerman @ 2003-04-11 21:22 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-sql
>> Define:
>> CREATE TABLE A (x int PRIMARY KEY, real v);
>> CREATE TABLE B (x int);
>
>> I'd like to calculate:
>> SELECT sum(v) FROM A WHERE EXISTS (SELECT 1 FROM B WHERE A.x=B.x);
>> ...but then it won't use the primary key index on A.x.
>
> In CVS tip (7.4-to-be) I think
>
> SELECT sum(v) FROM A WHERE A.x IN (SELECT B.x FROM B);
Oops. I guess I should've changed the example to "WHERE A.x>=B.x"
since that's what I'm really doing. Oh, well, my goof.
> would probably work well. In current releases I think all you can do is
> add an index to B.x and settle for the EXISTS() approach.
I don't think indexing B will help speed-wise if it still does the seq
scan through A.
>> PS. B is relatively small, a few thousand rows, while A has well over
>> 500,000 rows. The DISTINCT A.x should be about 10,000-50,000.
>
> BTW, how can a PRIMARY KEY column have fewer DISTINCT values than there
> are rows?
Oh, I just meant, "the DISTINCT A.x that are returned by:
SELECT DISTINCT A.x FROM A,B WHERE A.x=B.x
". Sorry for my lack of clarity...
--
Itai Zukerman <http://www.math-hat.com/~zukerman/;
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 21:32 Itai Zukerman <zukerman@math-hat.com>
parent: Itai Zukerman <zukerman@math-hat.com>
2 siblings, 1 reply; 14+ messages in thread
From: Itai Zukerman @ 2003-04-11 21:32 UTC (permalink / raw)
To: pgsql-sql
> CREATE TABLE A (x int PRIMARY KEY, real v);
> CREATE TABLE B (x int);
>
> I'd like to calculate:
>
> SELECT sum(v) FROM A WHERE EXISTS (SELECT 1 FROM B WHERE A.x=B.x);
This seems to be a reasonably-performing workaround:
SELECT DISTINCT x INTO TEMP C FROM A,B WHERE A.x=B.x;
SELECT sum(v) FROM A,C WHERE A.x=C.x;
--
Itai Zukerman <http://www.math-hat.com/~zukerman/;
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 21:42 Josh Berkus <josh@agliodbs.com>
parent: Itai Zukerman <zukerman@math-hat.com>
0 siblings, 1 reply; 14+ messages in thread
From: Josh Berkus @ 2003-04-11 21:42 UTC (permalink / raw)
To: Itai Zukerman <zukerman@math-hat.com>; +Cc: pgsql-sql
Itai,
> # explain select sum(weight) from rprofile rp where exists (select 1 from
rcount_prof rcp where rcp.profile ~<= rp.profile and ~rcp.psig ~<= rp.psig
and rcp.filter='{734,1944}');
I'm not familiar with the "~" that you have in the query. What are those for?
Do you have an index on rcp.profile, rcp.psig, rcp.filter?
--
-Josh Berkus
Aglio Database Solutions
San Francisco
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 22:02 Itai Zukerman <zukerman@math-hat.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 14+ messages in thread
From: Itai Zukerman @ 2003-04-11 22:02 UTC (permalink / raw)
To: josh@agliodbs.com; +Cc: pgsql-sql
>> # explain select sum(weight) from rprofile rp where exists (select 1 from
> rcount_prof rcp where rcp.profile ~<= rp.profile and ~rcp.psig ~<= rp.psig
> and rcp.filter='{734,1944}');
>
> I'm not familiar with the "~" that you have in the query. What are those for?
They are my own operators and functions. profile is a integer array
and the ~'s are subset operators. psig is a bit signature, "~" is
complement, and the ~ operators again are subset operators.
> Do you have an index on rcp.profile, rcp.psig, rcp.filter?
Yes, yes, and yes. ATM, though, there are only about 50 rows in
rcount_prof. The vast majority of time is spent scanning the
600,000-row rprofile table.
--
Itai Zukerman <http://www.math-hat.com/~zukerman/;
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 22:11 Tom Lane <tgl@sss.pgh.pa.us>
parent: Itai Zukerman <zukerman@math-hat.com>
0 siblings, 0 replies; 14+ messages in thread
From: Tom Lane @ 2003-04-11 22:11 UTC (permalink / raw)
To: Itai Zukerman <zukerman@math-hat.com>; +Cc: pgsql-sql
Itai Zukerman <zukerman@math-hat.com> writes:
>>> I'd like to calculate:
>>> SELECT sum(v) FROM A WHERE EXISTS (SELECT 1 FROM B WHERE A.x=B.x);
>>> ...but then it won't use the primary key index on A.x.
>>
>> In CVS tip (7.4-to-be) I think
>> SELECT sum(v) FROM A WHERE A.x IN (SELECT B.x FROM B);
> Oops. I guess I should've changed the example to "WHERE A.x>=B.x"
> since that's what I'm really doing. Oh, well, my goof.
Anything else you didn't bother to mention? Because in that case I
think your query reduces to
SELECT sum(v) FROM A WHERE A.x >= (SELECT min(x) FROM B);
which ought to run reasonably well (I'm sure it'll still want to
do a seqscan --- but not a nested loop).
regards, tom lane
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 22:12 Stephan Szabo <sszabo@megazone23.bigpanda.com>
parent: Itai Zukerman <zukerman@math-hat.com>
0 siblings, 1 reply; 14+ messages in thread
From: Stephan Szabo @ 2003-04-11 22:12 UTC (permalink / raw)
To: Itai Zukerman <zukerman@math-hat.com>; +Cc: pgsql-sql
On Fri, 11 Apr 2003, Itai Zukerman wrote:
> > CREATE TABLE A (x int PRIMARY KEY, real v);
> > CREATE TABLE B (x int);
> >
> > I'd like to calculate:
> >
> > SELECT sum(v) FROM A WHERE EXISTS (SELECT 1 FROM B WHERE A.x=B.x);
>
> This seems to be a reasonably-performing workaround:
>
> SELECT DISTINCT x INTO TEMP C FROM A,B WHERE A.x=B.x;
> SELECT sum(v) FROM A,C WHERE A.x=C.x;
Hmm, given that, would something like:
select sum(v) from
(select distinct on(x) x,v from a,b where a.x=b.x) as foo;
work?
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 22:18 Itai Zukerman <zukerman@math-hat.com>
parent: Stephan Szabo <sszabo@megazone23.bigpanda.com>
0 siblings, 0 replies; 14+ messages in thread
From: Itai Zukerman @ 2003-04-11 22:18 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone23.bigpanda.com>; +Cc: pgsql-sql
>> > CREATE TABLE A (x int PRIMARY KEY, real v);
>> > CREATE TABLE B (x int);
>> >
>> > SELECT sum(v) FROM A WHERE EXISTS (SELECT 1 FROM B WHERE A.x=B.x);
>>
>> This seems to be a reasonably-performing workaround:
>>
>> SELECT DISTINCT x INTO TEMP C FROM A,B WHERE A.x=B.x;
>> SELECT sum(v) FROM A,C WHERE A.x=C.x;
>
> Hmm, given that, would something like:
>
> select sum(v) from
> (select distinct on(x) x,v from a,b where a.x=b.x) as foo;
Excellent. Thanks!
--
Itai Zukerman <http://www.math-hat.com/~zukerman/;
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-11 22:36 Josh Berkus <josh@agliodbs.com>
parent: Itai Zukerman <zukerman@math-hat.com>
0 siblings, 2 replies; 14+ messages in thread
From: Josh Berkus @ 2003-04-11 22:36 UTC (permalink / raw)
To: Itai Zukerman <zukerman@math-hat.com>; +Cc: pgsql-sql
Itai,
> They are my own operators and functions. profile is a integer array
> and the ~'s are subset operators. psig is a bit signature, "~" is
> complement, and the ~ operators again are subset operators.
You're going to have to work on your question-posting skills.
Your query problem is that basically you have custom operators which the
planner doesn't know how to evaluate the return results on correctly. This
is a radically different situation from how you presented it in your first
posting.
This explains why the planner thinks that the exists clause will return
255,000 rows instead of the handful it actually does return. I'd suggest
re-building the query in several different syntaxes, until you find the one
the planner gets right.
Or build your own custom index types to take advantage of your custom
operators. B-tree indexes are optimized for =, LIKE, <, and > queries; I
don't think they know what to do with "~<="
At least, I think so. I'm not much of an expert on custom operators.
> > Do you have an index on rcp.profile, rcp.psig, rcp.filter?
>
> Yes, yes, and yes. ATM, though, there are only about 50 rows in
> rcount_prof. The vast majority of time is spent scanning the
> 600,000-row rprofile table.
Um, three seperate indexes on those three columns is not the same as a single
index on all three columns.
I was basically fishing for the reason why the planner got the row count so
radically wrong; now I think I know the reason ....
--
-Josh Berkus
Aglio Database Solutions
San Francisco
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-12 00:00 Tom Lane <tgl@sss.pgh.pa.us>
parent: Josh Berkus <josh@agliodbs.com>
1 sibling, 0 replies; 14+ messages in thread
From: Tom Lane @ 2003-04-12 00:00 UTC (permalink / raw)
To: josh@agliodbs.com; +Cc: Itai Zukerman <zukerman@math-hat.com>; pgsql-sql
Josh Berkus <josh@agliodbs.com> writes:
> Your query problem is that basically you have custom operators which the
> planner doesn't know how to evaluate the return results on correctly. This
> is a radically different situation from how you presented it in your first
> posting.
> This explains why the planner thinks that the exists clause will return
> 255,000 rows instead of the handful it actually does return. I'd suggest
> re-building the query in several different syntaxes, until you find the one
> the planner gets right.
Or more likely to work: build some custom selectivity estimation
functions to attach to the custom operators.
> Or build your own custom index types to take advantage of your custom
> operators. B-tree indexes are optimized for =, LIKE, <, and > queries; I
> don't think they know what to do with "~<="
They certainly don't. Possibly GIST could be taught what to do with
such things, but it won't happen by magic.
regards, tom lane
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: count(*), EXISTS, indexes
@ 2003-04-12 04:01 Itai Zukerman <zukerman@math-hat.com>
parent: Josh Berkus <josh@agliodbs.com>
1 sibling, 0 replies; 14+ messages in thread
From: Itai Zukerman @ 2003-04-12 04:01 UTC (permalink / raw)
To: josh@agliodbs.com; +Cc: pgsql-sql
>> They are my own operators and functions. profile is a integer array
>> and the ~'s are subset operators. psig is a bit signature, "~" is
>> complement, and the ~ operators again are subset operators.
>
> You're going to have to work on your question-posting skills.
*blush*, sorry.
> This explains why the planner thinks that the exists clause will return
> 255,000 rows instead of the handful it actually does return.
Actually:
# explain select sum(weight) from rprofile rp where exists (select 1 from rcount_prof rcp where rcp.profile ~<= rp.profile and ~rcp.psig ~<= rp.psig and rcp.filter='{734,1944}');
QUERY PLAN
----------------------------------------------------------------------------------------------------
Aggregate (cost=1544943.75..1544943.75 rows=1 width=4)
-> Seq Scan on rprofile rp (cost=0.00..1544255.00 rows=275500 width=4)
Filter: (subplan)
SubPlan
-> Seq Scan on rcount_prof rcp (cost=0.00..2.70 rows=1 width=0)
Filter: ((profile ~<= $0) AND ((~ psig) ~<= $1) AND (filter = '{734,1944}'::text))
I sort-of don't know what I'm doing reading these query plans, but I
think the estimates are more-or-less right: few rows from rcount_prof,
many rows from rprofile. 275,500 may be a bit high (it's actually
around 24,000 in this case), but def. within an order of magnitude.
> Or build your own custom index types to take advantage of your custom
> operators. B-tree indexes are optimized for =, LIKE, <, and > queries; I
> don't think they know what to do with "~<="
I created GiST indexes for the ~ operators (but, no, I haven't tuned
the selectivity estimation functions). The problem was, the query
wasn't using the index on rprofile. Stephan Szabo's suggestion worked
beautifully, though:
dl=# EXPLAIN ANALYZE
dl-# SELECT sum(weight)
dl-# FROM (SELECT DISTINCT ON(rp.rid) rp.rid, rp.weight
dl(# FROM rprofile rp, rcount_prof rcp
dl(# WHERE rcp.profile ~<= rp.profile
dl(# AND ~rcp.psig ~<= rp.psig
dl(# AND rcp.filter='{734,1944}') AS FOO;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=2245.08..2245.08 rows=1 width=1026) (actual time=954.45..954.45 rows=1 loops=1)
-> Subquery Scan foo (cost=2245.07..2245.08 rows=1 width=1026) (actual time=824.85..935.71 rows=23619 loops=1)
-> Unique (cost=2245.07..2245.08 rows=1 width=1026) (actual time=824.85..898.24 rows=23619 loops=1)
-> Sort (cost=2245.07..2245.08 rows=1 width=1026) (actual time=824.84..840.52 rows=23619 loops=1)
Sort Key: rp.rid
-> Nested Loop (cost=0.00..2245.06 rows=1 width=1026) (actual time=0.28..520.41 rows=23619 loops=1)
Join Filter: ("outer".profile ~<= "inner".profile)
-> Seq Scan on rcount_prof rcp (cost=0.00..2.44 rows=1 width=287) (actual time=0.06..0.33 rows=1 loops=1)
Filter: (filter = '{734,1944}'::text)
-> Index Scan using rprofile_profile_idx on rprofile rp (cost=0.00..2232.98 rows=551 width=739) (actual time=0.14..453.11 rows=23666 loops=1)
Index Cond: ((~ "outer".psig) ~<= rp.psig)
Total runtime: 958.62 msec
The row estimates are way off, though. My fault...
--
Itai Zukerman <http://www.math-hat.com/~zukerman/;
^ permalink raw reply [nested|flat] 14+ messages in thread
end of thread, other threads:[~2003-04-12 04:01 UTC | newest]
Thread overview: 14+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2003-04-11 20:39 count(*), EXISTS, indexes Itai Zukerman <zukerman@math-hat.com>
2003-04-11 20:53 ` Josh Berkus <josh@agliodbs.com>
2003-04-11 21:06 ` Itai Zukerman <zukerman@math-hat.com>
2003-04-11 21:42 ` Josh Berkus <josh@agliodbs.com>
2003-04-11 22:02 ` Itai Zukerman <zukerman@math-hat.com>
2003-04-11 22:36 ` Josh Berkus <josh@agliodbs.com>
2003-04-12 00:00 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-04-12 04:01 ` Itai Zukerman <zukerman@math-hat.com>
2003-04-11 21:10 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-04-11 21:22 ` Itai Zukerman <zukerman@math-hat.com>
2003-04-11 22:11 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-04-11 21:32 ` Itai Zukerman <zukerman@math-hat.com>
2003-04-11 22:12 ` Stephan Szabo <sszabo@megazone23.bigpanda.com>
2003-04-11 22:18 ` Itai Zukerman <zukerman@math-hat.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