pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: "SELECT IN" Still Broken in 7.4b
30+ messages / 13 participants
[nested] [flat]
* Re: "SELECT IN" Still Broken in 7.4b
@ 2003-08-20 16:27 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2 siblings, 1 reply; 30+ messages in thread
From: Stephan Szabo @ 2003-08-20 16:27 UTC (permalink / raw)
To: Mike Winter <mike.winter@frontlogic.com>; +Cc: pgsql-sql
On Wed, 20 Aug 2003, Mike Winter wrote:
> I'm sure many on this list are sick of hearing about this problem, but it
> was on the fix list for 7.4, but doesn't appear to have been changed.
IN (subselect) was changed for 7.4 (although I'm not sure of the list
mentions the difference). I don't know of any major changes to IN
(valuelist) though.
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
@ 2003-08-20 16:45 ` Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
0 siblings, 1 reply; 30+ messages in thread
From: Mike Winter @ 2003-08-20 16:45 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone.bigpanda.com>; +Cc: pgsql-sql
On Wed, 20 Aug 2003, Stephan Szabo wrote:
>
> On Wed, 20 Aug 2003, Mike Winter wrote:
>
> > I'm sure many on this list are sick of hearing about this problem, but it
> > was on the fix list for 7.4, but doesn't appear to have been changed.
>
> IN (subselect) was changed for 7.4 (although I'm not sure of the list
> mentions the difference). I don't know of any major changes to IN
> (valuelist) though.
Thanks, Stephan. I was really hoping that the IN(valuelist) was going to
be changed at the same time, because it really is unusable for anything
over a couple of thousand values.
--
_______________________________________________________________________
Front Logic Inc. Tel: 306.653.2725 x14
226 Pacific Ave or 1.800.521.4510 x14
Saskatoon, SK Fax: 306.653.0972
S7K 1N9 Canada Cell: 306.717.2550
http://www.frontlogic.com mike.winter@frontlogic.com
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
@ 2003-08-20 17:09 ` Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
0 siblings, 1 reply; 30+ messages in thread
From: Rod Taylor @ 2003-08-20 17:09 UTC (permalink / raw)
To: Mike Winter <mike.winter@frontlogic.com>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; pgsql-sql
> Thanks, Stephan. I was really hoping that the IN(valuelist) was going to
> be changed at the same time, because it really is unusable for anything
> over a couple of thousand values.
Changed to do what?
I suppose that the ability to combine several index scans via a bitmap
would help to linearize those, but that is far from an IN(valuelist)
specific enhancement.
Attachments:
signature.asc (application/pgp-signature, 186B) download
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
@ 2003-08-20 17:41 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-21 07:38 ` Re: "SELECT IN" Still Broken in 7.4b Oleg Bartunov <oleg@sai.msu.su>
0 siblings, 2 replies; 30+ messages in thread
From: Stephan Szabo @ 2003-08-20 17:41 UTC (permalink / raw)
To: Rod Taylor <rbt@rbt.ca>; +Cc: Mike Winter <mike.winter@frontlogic.com>; pgsql-sql
On Wed, 20 Aug 2003, Rod Taylor wrote:
> > Thanks, Stephan. I was really hoping that the IN(valuelist) was going to
> > be changed at the same time, because it really is unusable for anything
> > over a couple of thousand values.
>
> Changed to do what?
One possibility might be to act as if the valuelist was a table and do the
IN as if it were that way, rather than treating it as a set of ORs. That
would be basically like doing the temporary table solution, but without
requiring the user to do it.
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
@ 2003-08-20 20:41 ` Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
1 sibling, 1 reply; 30+ messages in thread
From: Rod Taylor @ 2003-08-20 20:41 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone.bigpanda.com>; +Cc: Mike Winter <mike.winter@frontlogic.com>; pgsql-sql
On Wed, 2003-08-20 at 17:41, Stephan Szabo wrote:
> On Wed, 20 Aug 2003, Rod Taylor wrote:
>
> > > Thanks, Stephan. I was really hoping that the IN(valuelist) was going to
> > > be changed at the same time, because it really is unusable for anything
> > > over a couple of thousand values.
> >
> > Changed to do what?
>
> One possibility might be to act as if the valuelist was a table and do the
> IN as if it were that way, rather than treating it as a set of ORs. That
> would be basically like doing the temporary table solution, but without
> requiring the user to do it.
Is the temp table version any faster? I realize it has a higher limit
to the number of items you can have in the list.
Attachments:
signature.asc (application/pgp-signature, 186B) download
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
@ 2003-08-20 21:55 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
0 siblings, 1 reply; 30+ messages in thread
From: Stephan Szabo @ 2003-08-20 21:55 UTC (permalink / raw)
To: Rod Taylor <rbt@rbt.ca>; +Cc: Mike Winter <mike.winter@frontlogic.com>; pgsql-sql
On Wed, 20 Aug 2003, Rod Taylor wrote:
> On Wed, 2003-08-20 at 17:41, Stephan Szabo wrote:
> > On Wed, 20 Aug 2003, Rod Taylor wrote:
> >
> > > > Thanks, Stephan. I was really hoping that the IN(valuelist) was going to
> > > > be changed at the same time, because it really is unusable for anything
> > > > over a couple of thousand values.
> > >
> > > Changed to do what?
> >
> > One possibility might be to act as if the valuelist was a table and do the
> > IN as if it were that way, rather than treating it as a set of ORs. That
> > would be basically like doing the temporary table solution, but without
> > requiring the user to do it.
>
> Is the temp table version any faster? I realize it has a higher limit
> to the number of items you can have in the list.
Within the scope of the new hashed IN stuff I believe so in at least some
cases. I have a few million row table of integers where searching for
values IN (~10000 values) takes longer than creating the temp table,
copying into it and doing the in subquery. That's not a particularly
meaningful test case, but sending the psql output to /dev/null gives me:
create temp table/copy 10001 entries/select in subquery - .8 sec
select in (value list 9998 entries) - ~ 2min 19 sec
explain select in (value list) - ~ 4.8 sec
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
@ 2003-08-21 10:05 ` Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
0 siblings, 1 reply; 30+ messages in thread
From: Dani Oderbolz @ 2003-08-21 10:05 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone.bigpanda.com>; pgsql-sql
Stephan Szabo wrote:
>On Wed, 20 Aug 2003, Rod Taylor wrote:
>...
>
>
>>Is the temp table version any faster? I realize it has a higher limit
>>to the number of items you can have in the list.
>>
>>
>
>Within the scope of the new hashed IN stuff I believe so in at least some
>cases. I have a few million row table of integers where searching for
>values IN (~10000 values) takes longer than creating the temp table,
>copying into it and doing the in subquery. That's not a particularly
>meaningful test case, but sending the psql output to /dev/null gives me: ...
>
But where do your values come from in the first place?
Couldn't you optimize your model so that you don't have to copy around
such amounts of data?
Regards,
Dani
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
@ 2003-08-21 17:28 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 15:11 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Shridhar Daithankar <shridhar_daithankar@persistent.co.in>
0 siblings, 2 replies; 30+ messages in thread
From: Stephan Szabo @ 2003-08-21 17:28 UTC (permalink / raw)
To: Dani Oderbolz <oderbolz@ecologic.de>; +Cc: pgsql-sql
On Thu, 21 Aug 2003, Dani Oderbolz wrote:
> Stephan Szabo wrote:
>
> >On Wed, 20 Aug 2003, Rod Taylor wrote:
> >...
> >
> >
> >>Is the temp table version any faster? I realize it has a higher limit
> >>to the number of items you can have in the list.
> >>
> >>
> >
> >Within the scope of the new hashed IN stuff I believe so in at least some
> >cases. I have a few million row table of integers where searching for
> >values IN (~10000 values) takes longer than creating the temp table,
> >copying into it and doing the in subquery. That's not a particularly
> >meaningful test case, but sending the psql output to /dev/null gives me: ...
> >
> But where do your values come from in the first place?
> Couldn't you optimize your model so that you don't have to copy around
> such amounts of data?
I wasn't the OP, I was doing a simple test as a comparison between
the two forms of the queries to see if making a temp table and populating
it and then doing the subselect form could ever be faster than the current
conversion for valuelists to a sequence of or conditions. In 7.3, it
probably was not possible for a conversion to in subselect to be faster,
but with the new hash subquery stuff it was worth trying again.
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
@ 2003-08-21 20:42 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 21:07 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 21:18 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Manfred Koizar <mkoi-pg@aon.at>
2003-08-21 21:19 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Josh Berkus <josh@agliodbs.com>
2003-08-21 22:01 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Joe Conway <mail@joeconway.com>
2003-08-22 01:40 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Christopher Kings-Lynne <chriskl@familyhealth.com.au>
1 sibling, 5 replies; 30+ messages in thread
From: Tom Lane @ 2003-08-21 20:42 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone.bigpanda.com>; +Cc: Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgreSQL.org
Stephan Szabo <sszabo@megazone.bigpanda.com> writes:
> Within the scope of the new hashed IN stuff I believe so in at least some
> cases. I have a few million row table of integers where searching for
> values IN (~10000 values) takes longer than creating the temp table,
> copying into it and doing the in subquery.
I did some profiling and soon realized that the main problem is the
executor's trick for not returning the same row multiple times in a
multiple-indexscan plan node. The point is that given
WHERE a = 1 OR b = 1
you could create a plan that first indexscans on a, then indexscans on
b --- but you mustn't return any tuples in the second scan that you
already returned in the first. IndexNext solves this by evaluating the
prior-scan index conditions to see if they are true. Which is okay if
there aren't too many of them. But when you have an N-element IN list
this means you are going to do O(N^2) index expression evaluations.
In the 10000-element IN-list test case, ExecQual gets called almost
50 million times :-(
I'm toying with the notion of ripping out that logic and instead
building an in-memory hashtable of already-returned TIDs. This could
theoretically run out of memory if the multiple indexscan returns enough
tuples, but I think in practice that wouldn't happen because the planner
wouldn't choose an indexscan when very large numbers of tuples are being
selected.
Comments?
regards, tom lane
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-21 21:07 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-24 21:37 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
4 siblings, 1 reply; 30+ messages in thread
From: Stephan Szabo @ 2003-08-21 21:07 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgreSQL.org
On Thu, 21 Aug 2003, Tom Lane wrote:
> Stephan Szabo <sszabo@megazone.bigpanda.com> writes:
> > Within the scope of the new hashed IN stuff I believe so in at least some
> > cases. I have a few million row table of integers where searching for
> > values IN (~10000 values) takes longer than creating the temp table,
> > copying into it and doing the in subquery.
>
> I did some profiling and soon realized that the main problem is the
> executor's trick for not returning the same row multiple times in a
> multiple-indexscan plan node. The point is that given
> WHERE a = 1 OR b = 1
> you could create a plan that first indexscans on a, then indexscans on
> b --- but you mustn't return any tuples in the second scan that you
> already returned in the first. IndexNext solves this by evaluating the
> prior-scan index conditions to see if they are true. Which is okay if
> there aren't too many of them. But when you have an N-element IN list
> this means you are going to do O(N^2) index expression evaluations.
> In the 10000-element IN-list test case, ExecQual gets called almost
> 50 million times :-(
>
> I'm toying with the notion of ripping out that logic and instead
> building an in-memory hashtable of already-returned TIDs. This could
> theoretically run out of memory if the multiple indexscan returns enough
> tuples, but I think in practice that wouldn't happen because the planner
> wouldn't choose an indexscan when very large numbers of tuples are being
> selected.
Well, if you want to be safer, I guess you could (at runtime) decide that
the table's gotten too big and fall back to the old method if you didn't
entirely rip it out. I'm not sure if that'd be too ugly though, but it
would mean that you wouldn't have to worry about it returning too many
tuples.
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 21:07 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
@ 2003-08-24 21:37 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 30+ messages in thread
From: Tom Lane @ 2003-08-24 21:37 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone.bigpanda.com>; +Cc: Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgresql.org
Stephan Szabo <sszabo@megazone.bigpanda.com> writes:
> Well, if you want to be safer, I guess you could (at runtime) decide that
> the table's gotten too big and fall back to the old method if you didn't
> entirely rip it out. I'm not sure if that'd be too ugly though, but it
> would mean that you wouldn't have to worry about it returning too many
> tuples.
I did it this way --- it falls back to the old code if the TID hash
table grows to exceed SortMem. Should be noticeably faster than the
old code for reasonably-sized IN lists.
regards, tom lane
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-21 21:18 ` Manfred Koizar <mkoi-pg@aon.at>
2003-08-21 21:46 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
4 siblings, 1 reply; 30+ messages in thread
From: Manfred Koizar @ 2003-08-21 21:18 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgreSQL.org
On Thu, 21 Aug 2003 16:42:20 -0400, Tom Lane <tgl@sss.pgh.pa.us>
wrote:
>The point is that given
> WHERE a = 1 OR b = 1
>you could create a plan that first indexscans on a, then indexscans on
>b --- but you mustn't return any tuples in the second scan that you
>already returned in the first. IndexNext solves this by evaluating the
>prior-scan index conditions to see if they are true.
WHERE a = 1 OR b = 2
and
WHERE a = 1 OR a = 2
are totally different things. In the latter case you don't have to
check prior conditions because the conditions are mutually exclusive.
Is this reasonably easy to find out at plan creation time?
Yes, I changed your example to make my point clear, because
WHERE a = 1 OR a = 1
has its own set of problems.
Servus
Manfred
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 21:18 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Manfred Koizar <mkoi-pg@aon.at>
@ 2003-08-21 21:46 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 15:28 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Greg Stark <gsstark@mit.edu>
0 siblings, 1 reply; 30+ messages in thread
From: Tom Lane @ 2003-08-21 21:46 UTC (permalink / raw)
To: Manfred Koizar <mkoi-pg@aon.at>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgreSQL.org
Manfred Koizar <mkoi-pg@aon.at> writes:
> WHERE a = 1 OR a = 2
> are totally different things. In the latter case you don't have to
> check prior conditions because the conditions are mutually exclusive.
> Is this reasonably easy to find out at plan creation time?
Yeah, I know, but I see no easy way to verify this (where "easy" means
"doesn't take an unreasonable amount of time"). A naive check would
take O(N^2) time, putting you right back where you started. Even a
smart check would surely take more time per item than one hashtable probe.
I'm also concerned about how much the planner would have to assume about
the semantics of the operators in order to prove the conditions are
mutually exclusive.
Finally, I suspect that once we get rid of the O(N^2) behavior in the
executor, we will find that the next biggest bottleneck is in the
planner; adding more work for it to do per OR-clause item will make
things worse not better.
regards, tom lane
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 21:18 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Manfred Koizar <mkoi-pg@aon.at>
2003-08-21 21:46 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-22 15:28 ` Greg Stark <gsstark@mit.edu>
2003-08-22 15:47 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
0 siblings, 1 reply; 30+ messages in thread
From: Greg Stark @ 2003-08-22 15:28 UTC (permalink / raw)
To: pgsql-hackers@postgresql.org
Tom Lane <tgl@sss.pgh.pa.us> writes:
> Finally, I suspect that once we get rid of the O(N^2) behavior in the
> executor, we will find that the next biggest bottleneck is in the
> planner; adding more work for it to do per OR-clause item will make
> things worse not better.
But time spent in the planner doesn't matter if you're using prepared queries
which is true for OLTP applications where there are very few queries being
executed many many times. I hear web sites are quite popular these days.
I missed the beginning of this thread so I'm not sure if it's relevant. But
wouldn't it be possible to just check if all the clauses and see if they're
using precisely the same index with an equality type operator? That won't
catch things like "a BETWEEN 1 AND 2 OR a BETWEEN 5 AND 6" but it will catch
things like "a IN (1,2,3,4,5,6)". And I don't see how it wouldn't be linear
in the number of clauses.
--
greg
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 21:18 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Manfred Koizar <mkoi-pg@aon.at>
2003-08-21 21:46 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 15:28 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Greg Stark <gsstark@mit.edu>
@ 2003-08-22 15:47 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
0 siblings, 0 replies; 30+ messages in thread
From: Stephan Szabo @ 2003-08-22 15:47 UTC (permalink / raw)
To: Greg Stark <gsstark@mit.edu>; +Cc: pgsql-hackers@postgresql.org
On 22 Aug 2003, Greg Stark wrote:
>
> Tom Lane <tgl@sss.pgh.pa.us> writes:
>
> > Finally, I suspect that once we get rid of the O(N^2) behavior in the
> > executor, we will find that the next biggest bottleneck is in the
> > planner; adding more work for it to do per OR-clause item will make
> > things worse not better.
>
> But time spent in the planner doesn't matter if you're using prepared queries
> which is true for OLTP applications where there are very few queries being
> executed many many times. I hear web sites are quite popular these days.
True, but not every application is such. You still need to balance
planning time with other concerns.
> I missed the beginning of this thread so I'm not sure if it's relevant. But
> wouldn't it be possible to just check if all the clauses and see if they're
> using precisely the same index with an equality type operator? That won't
> catch things like "a BETWEEN 1 AND 2 OR a BETWEEN 5 AND 6" but it will catch
> things like "a IN (1,2,3,4,5,6)". And I don't see how it wouldn't be linear
> in the number of clauses.
But that wouldn't help unless you made sure that what was being compared
was not the same AFAICT (since the point would be to not need to check if
the rows were already returned) since a=1 or a=1 is legal if meaningless.
And that's not necessarily immediately obvious depending on the behavior
of the = operator without trying it, for example does where a='c ' or
a='c' have a redundancy or not?
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-21 21:19 ` Josh Berkus <josh@agliodbs.com>
4 siblings, 0 replies; 30+ messages in thread
From: Josh Berkus @ 2003-08-21 21:19 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; Stephan Szabo <sszabo@megazone.bigpanda.com>; +Cc: Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgresql.org
Tom,
> I'm toying with the notion of ripping out that logic and instead
> building an in-memory hashtable of already-returned TIDs. This could
> theoretically run out of memory if the multiple indexscan returns enough
> tuples, but I think in practice that wouldn't happen because the planner
> wouldn't choose an indexscan when very large numbers of tuples are being
> selected.
Don't forget all of the tyros who tune their queries through "set
enable_seqscan=false". I think we'd need some kind of memory safety valve on
this, like sandboxing it in sort_mem.
--
-Josh Berkus
Aglio Database Solutions
San Francisco
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-21 22:01 ` Joe Conway <mail@joeconway.com>
2003-08-21 22:17 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
4 siblings, 1 reply; 30+ messages in thread
From: Joe Conway @ 2003-08-21 22:01 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgresql.org
Tom Lane wrote:
> I'm toying with the notion of ripping out that logic and instead
> building an in-memory hashtable of already-returned TIDs. This could
> theoretically run out of memory if the multiple indexscan returns enough
> tuples, but I think in practice that wouldn't happen because the planner
> wouldn't choose an indexscan when very large numbers of tuples are being
> selected.
I thought with your recent changes, you could use dynahash, which
already spills to disk instead of consuming all memory?
Joe
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 22:01 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Joe Conway <mail@joeconway.com>
@ 2003-08-21 22:17 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 30+ messages in thread
From: Tom Lane @ 2003-08-21 22:17 UTC (permalink / raw)
To: Joe Conway <mail@joeconway.com>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgresql.org
Joe Conway <mail@joeconway.com> writes:
> Tom Lane wrote:
>> I'm toying with the notion of ripping out that logic and instead
>> building an in-memory hashtable of already-returned TIDs. This could
>> theoretically run out of memory if the multiple indexscan returns enough
>> tuples, but I think in practice that wouldn't happen because the planner
>> wouldn't choose an indexscan when very large numbers of tuples are being
>> selected.
> I thought with your recent changes, you could use dynahash, which
> already spills to disk instead of consuming all memory?
I was going to use dynahash, but it doesn't spill to disk. You're
confusing that with the HashJoin mechanism, which is quite different and
only really useful for joins.
regards, tom lane
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Re: [SQL] "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-22 01:40 ` Christopher Kings-Lynne <chriskl@familyhealth.com.au>
4 siblings, 0 replies; 30+ messages in thread
From: Christopher Kings-Lynne @ 2003-08-22 01:40 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone.bigpanda.com>; Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Dani Oderbolz <oderbolz@ecologic.de>; pgsql-hackers@postgresql.org
> I'm toying with the notion of ripping out that logic and instead
> building an in-memory hashtable of already-returned TIDs. This could
> theoretically run out of memory if the multiple indexscan returns enough
> tuples, but I think in practice that wouldn't happen because the planner
> wouldn't choose an indexscan when very large numbers of tuples are being
> selected.
>
> Comments?
Sounds kind of like a bitmap index almost..
Chris
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: [SQL] "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Re: "SELECT IN" Still Broken in 7.4b Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
@ 2003-08-22 15:11 ` Shridhar Daithankar <shridhar_daithankar@persistent.co.in>
1 sibling, 0 replies; 30+ messages in thread
From: Shridhar Daithankar @ 2003-08-22 15:11 UTC (permalink / raw)
To: pgsql-hackers@postgresql.org
On 21 Aug 2003 at 16:42, Tom Lane wrote:
> Stephan Szabo <sszabo@megazone.bigpanda.com> writes:
> > Within the scope of the new hashed IN stuff I believe so in at least some
> > cases. I have a few million row table of integers where searching for
> > values IN (~10000 values) takes longer than creating the temp table,
> > copying into it and doing the in subquery.
>
> I did some profiling and soon realized that the main problem is the
> executor's trick for not returning the same row multiple times in a
> multiple-indexscan plan node. The point is that given
> WHERE a = 1 OR b = 1
> you could create a plan that first indexscans on a, then indexscans on
> b --- but you mustn't return any tuples in the second scan that you
> already returned in the first. IndexNext solves this by evaluating the
> prior-scan index conditions to see if they are true. Which is okay if
> there aren't too many of them. But when you have an N-element IN list
> this means you are going to do O(N^2) index expression evaluations.
> In the 10000-element IN-list test case, ExecQual gets called almost
> 50 million times :-(
>
> I'm toying with the notion of ripping out that logic and instead
> building an in-memory hashtable of already-returned TIDs. This could
> theoretically run out of memory if the multiple indexscan returns enough
> tuples, but I think in practice that wouldn't happen because the planner
> wouldn't choose an indexscan when very large numbers of tuples are being
> selected.
If I understand it correctly, we are essentially looking at ~10000 individual
index scans, in above example, isn't it? So if planner takes this in account,
it probably would not opt for seq. scan.
Other idea could be, index the in list first and search the index using
locality of values in the in list. If the 10K values in the list are between
10K-20K, they should be pretty easy to locate with single index sweep, assuming
uniform distribution. May be planner could build this IN list index before
drawing plan to determine cardinality and distribution of individual values.
On the least side, it could draw a plan for fetching a tuple range between min
and max of IN values and building in memory hash of these values for
comparison. That's would surely be cheaper than scanning entire table/result
set over ad over
Frankly, I would say a temp table is far better solution..:-)
Just a thought...
Bye
Shridhar
--
Youth doesn't excuse everything. -- Dr. Janice Lester (in Kirk's body),
"Turnabout Intruder", stardate 5928.5.
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 16:27 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Re: "SELECT IN" Still Broken in 7.4b Stephan Szabo <sszabo@megazone.bigpanda.com>
@ 2003-08-21 07:38 ` Oleg Bartunov <oleg@sai.msu.su>
1 sibling, 0 replies; 30+ messages in thread
From: Oleg Bartunov @ 2003-08-21 07:38 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone.bigpanda.com>; +Cc: Rod Taylor <rbt@rbt.ca>; Mike Winter <mike.winter@frontlogic.com>; pgsql-sql
On Wed, 20 Aug 2003, Stephan Szabo wrote:
>
> On Wed, 20 Aug 2003, Rod Taylor wrote:
>
> > > Thanks, Stephan. I was really hoping that the IN(valuelist) was going to
> > > be changed at the same time, because it really is unusable for anything
> > > over a couple of thousand values.
> >
> > Changed to do what?
>
> One possibility might be to act as if the valuelist was a table and do the
> IN as if it were that way, rather than treating it as a set of ORs. That
> would be basically like doing the temporary table solution, but without
> requiring the user to do it.
>
for integers we use contrib/intarray as a workaround. In principle,
it's possible to extend intarray to general array.
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 7: don't forget to increase your free space map settings
>
Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
@ 2003-08-20 17:10 ` Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2 siblings, 1 reply; 30+ messages in thread
From: Rod Taylor @ 2003-08-20 17:10 UTC (permalink / raw)
To: Mike Winter <mike.winter@frontlogic.com>; +Cc: pgsql-sql
Ensure your IN list is unique. You might find better times by through
an indexed temp table.
On Wed, 2003-08-20 at 16:32, Mike Winter wrote:
> I'm sure many on this list are sick of hearing about this problem, but it
> was on the fix list for 7.4, but doesn't appear to have been changed.
>
> You can see one of the many threads on the problem at:
> http://archives.postgresql.org/pgsql-sql/2003-05/msg00352.php
>
> Basically, queries of the form SELECT <rows> FROM <table> WHERE <row> IN
> (<list of values>) take forever for high numbers of rows in the IN clause.
> We've done timing on 7.3 and 7.4b and there is no speed improvement on
> these queries.
>
> Does anyone know what the status of this bug is?
Attachments:
signature.asc (application/pgp-signature, 186B) download
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 17:10 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
@ 2003-08-20 18:51 ` Mike Winter <mike.winter@frontlogic.com>
2003-08-20 19:24 ` Re: "SELECT IN" Still Broken in 7.4b Joe Conway <mail@joeconway.com>
2003-08-20 20:32 ` Re: "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 2 replies; 30+ messages in thread
From: Mike Winter @ 2003-08-20 18:51 UTC (permalink / raw)
To: pgsql-sql
On Wed, 20 Aug 2003, Rod Taylor wrote:
> Ensure your IN list is unique. You might find better times by through
> an indexed temp table.
That is what I ended up doing, but it's not a very elegant solution.
MySQL does queries of this type orders of magnitudes faster than Postgres
on large value lists, although I have no specific algorithmic solutions to
offer for how to make it faster. I don't believe making the IN lists
unique has any affect on performance.
--
_______________________________________________________________________
Front Logic Inc. Tel: 306.653.2725 x14
226 Pacific Ave or 1.800.521.4510 x14
Saskatoon, SK Fax: 306.653.0972
S7K 1N9 Canada Cell: 306.717.2550
http://www.frontlogic.com mike.winter@frontlogic.com
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 17:10 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
@ 2003-08-20 19:24 ` Joe Conway <mail@joeconway.com>
1 sibling, 0 replies; 30+ messages in thread
From: Joe Conway @ 2003-08-20 19:24 UTC (permalink / raw)
To: Mike Winter <mike.winter@frontlogic.com>; +Cc: pgsql-sql
Mike Winter wrote:
> On Wed, 20 Aug 2003, Rod Taylor wrote:
>
>>Ensure your IN list is unique. You might find better times by through
>>an indexed temp table.
>
> That is what I ended up doing, but it's not a very elegant solution.
> MySQL does queries of this type orders of magnitudes faster than Postgres
> on large value lists, although I have no specific algorithmic solutions to
> offer for how to make it faster. I don't believe making the IN lists
> unique has any affect on performance.
>
I have no idea whether it will be better or worse performance, but in
7.4 you could do:
select blah from foo where id = any (ARRAY[list_of_literals]);
Joe
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 17:10 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
@ 2003-08-20 20:32 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 06:32 ` Re: "SELECT IN" Still Broken in 7.4b Bertrand Petit <pgsql-sql@phoe.frmug.org>
1 sibling, 1 reply; 30+ messages in thread
From: Tom Lane @ 2003-08-20 20:32 UTC (permalink / raw)
To: Mike Winter <mike.winter@frontlogic.com>; +Cc: pgsql-sql
Mike Winter <mike.winter@frontlogic.com> writes:
> MySQL does queries of this type orders of magnitudes faster than Postgres
> on large value lists, although I have no specific algorithmic solutions to
> offer for how to make it faster.
How large is "large", and what plan type are you getting (seq scan or
multiple index scan)? Is it possible that the cost comes from planner
overhead and not execution? Checking EXPLAIN ANALYZE reported time
against actual elapsed time (cf psql's \timing option) would tell.
regards, tom lane
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 17:10 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 20:32 ` Re: "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-22 06:32 ` Bertrand Petit <pgsql-sql@phoe.frmug.org>
2003-08-22 12:36 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-22 12:50 ` Re: "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 2 replies; 30+ messages in thread
From: Bertrand Petit @ 2003-08-22 06:32 UTC (permalink / raw)
To: pgsql-sql
On Wed, Aug 20, 2003 at 04:32:19PM -0400, Tom Lane wrote:
>
> against actual elapsed time (cf psql's \timing option) would tell.
What is measured by the \timing option? The figures reported
are slightly larger than those loged when the log_duration parameter
is true.
=> select count(*) from foo;
count
--------
362921
(1 row)
Time: 5500.88 ms
while in syslog, the timing was "LOG: duration: 5.499783 sec". There
is a difference of 1.097 ms.
In both cases what is this duration? Real time or CPU time?
--
%!PS
297.6 420.9 translate 90 rotate 0 setgray gsave 0 1 1{pop 0 180 moveto 100
180 170 100 170 -10 curveto 180 -9 180 -9 190 -10 curveto 190 100 100 180
0 180 curveto fill 180 rotate}for grestore/Bookman-LightItalic findfont
240 scalefont setfont -151.536392 -63.7998886 moveto (bp)show showpage
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 17:10 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 20:32 ` Re: "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 06:32 ` Re: "SELECT IN" Still Broken in 7.4b Bertrand Petit <pgsql-sql@phoe.frmug.org>
@ 2003-08-22 12:36 ` Rod Taylor <rbt@rbt.ca>
1 sibling, 0 replies; 30+ messages in thread
From: Rod Taylor @ 2003-08-22 12:36 UTC (permalink / raw)
To: Bertrand Petit <pgsql-sql@phoe.frmug.org>; +Cc: pgsql-sql
> What is measured by the \timing option? The figures reported
> are slightly larger than those loged when the log_duration parameter
> is true.
The time of the psql client. It will include round trip activity
including network overhead.
Attachments:
signature.asc (application/pgp-signature, 186B) download
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 17:10 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 20:32 ` Re: "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 06:32 ` Re: "SELECT IN" Still Broken in 7.4b Bertrand Petit <pgsql-sql@phoe.frmug.org>
@ 2003-08-22 12:50 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 13:04 ` Re: "SELECT IN" Still Broken in 7.4b Bertrand Petit <pgsql-sql@phoe.frmug.org>
1 sibling, 1 reply; 30+ messages in thread
From: Tom Lane @ 2003-08-22 12:50 UTC (permalink / raw)
To: Bertrand Petit <pgsql-sql@phoe.frmug.org>; +Cc: pgsql-sql
Bertrand Petit <pgsql-sql@phoe.frmug.org> writes:
> On Wed, Aug 20, 2003 at 04:32:19PM -0400, Tom Lane wrote:
>> against actual elapsed time (cf psql's \timing option) would tell.
> What is measured by the \timing option?
Elapsed time ... as seen by the client, of course.
> The figures reported
> are slightly larger than those loged when the log_duration parameter
> is true.
Yeah, that's what I'd expect, especially if there is a network hop
involved.
regards, tom lane
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
2003-08-20 17:10 ` Re: "SELECT IN" Still Broken in 7.4b Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Re: "SELECT IN" Still Broken in 7.4b Mike Winter <mike.winter@frontlogic.com>
2003-08-20 20:32 ` Re: "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 06:32 ` Re: "SELECT IN" Still Broken in 7.4b Bertrand Petit <pgsql-sql@phoe.frmug.org>
2003-08-22 12:50 ` Re: "SELECT IN" Still Broken in 7.4b Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-08-22 13:04 ` Bertrand Petit <pgsql-sql@phoe.frmug.org>
0 siblings, 0 replies; 30+ messages in thread
From: Bertrand Petit @ 2003-08-22 13:04 UTC (permalink / raw)
To: pgsql-sql
On Fri, Aug 22, 2003 at 08:50:15AM -0400, Tom Lane wrote:
> Bertrand Petit <pgsql-sql@phoe.frmug.org> writes:
> > On Wed, Aug 20, 2003 at 04:32:19PM -0400, Tom Lane wrote:
> >> against actual elapsed time (cf psql's \timing option) would tell.
>
> > What is measured by the \timing option?
>
> Elapsed time ... as seen by the client, of course.
Is there a way to obtain the CPU time consumed by a query,
including a breakdown between user- and kernel-land?
--
%!PS
297.6 420.9 translate 90 rotate 0 setgray gsave 0 1 1{pop 0 180 moveto 100
180 170 100 170 -10 curveto 180 -9 180 -9 190 -10 curveto 190 100 100 180
0 180 curveto fill 180 rotate}for grestore/Bookman-LightItalic findfont
240 scalefont setfont -151.536392 -63.7998886 moveto (bp)show showpage
^ permalink raw reply [nested|flat] 30+ messages in thread
* Re: "SELECT IN" Still Broken in 7.4b
@ 2003-08-24 21:38 ` Tom Lane <tgl@sss.pgh.pa.us>
2 siblings, 0 replies; 30+ messages in thread
From: Tom Lane @ 2003-08-24 21:38 UTC (permalink / raw)
To: Mike Winter <mike.winter@frontlogic.com>; +Cc: pgsql-sql
Mike Winter <mike.winter@frontlogic.com> writes:
> Basically, queries of the form SELECT <rows> FROM <table> WHERE <row> IN
> (<list of values>) take forever for high numbers of rows in the IN clause.
> We've done timing on 7.3 and 7.4b and there is no speed improvement on
> these queries.
> Does anyone know what the status of this bug is?
Try it in CVS tip ...
regards, tom lane
^ permalink raw reply [nested|flat] 30+ messages in thread
end of thread, other threads:[~2003-08-24 21:38 UTC | newest]
Thread overview: 30+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2003-08-20 16:27 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 16:45 ` Mike Winter <mike.winter@frontlogic.com>
2003-08-20 17:09 ` Rod Taylor <rbt@rbt.ca>
2003-08-20 17:41 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-20 20:41 ` Rod Taylor <rbt@rbt.ca>
2003-08-20 21:55 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 10:05 ` Dani Oderbolz <oderbolz@ecologic.de>
2003-08-21 17:28 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 20:42 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 21:07 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-24 21:37 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-21 21:18 ` Manfred Koizar <mkoi-pg@aon.at>
2003-08-21 21:46 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 15:28 ` Greg Stark <gsstark@mit.edu>
2003-08-22 15:47 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2003-08-21 21:19 ` Josh Berkus <josh@agliodbs.com>
2003-08-21 22:01 ` Joe Conway <mail@joeconway.com>
2003-08-21 22:17 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 01:40 ` Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2003-08-22 15:11 ` Shridhar Daithankar <shridhar_daithankar@persistent.co.in>
2003-08-21 07:38 ` Oleg Bartunov <oleg@sai.msu.su>
2003-08-20 17:10 ` Rod Taylor <rbt@rbt.ca>
2003-08-20 18:51 ` Mike Winter <mike.winter@frontlogic.com>
2003-08-20 19:24 ` Joe Conway <mail@joeconway.com>
2003-08-20 20:32 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 06:32 ` Bertrand Petit <pgsql-sql@phoe.frmug.org>
2003-08-22 12:36 ` Rod Taylor <rbt@rbt.ca>
2003-08-22 12:50 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-08-22 13:04 ` Bertrand Petit <pgsql-sql@phoe.frmug.org>
2003-08-24 21:38 ` Tom Lane <tgl@sss.pgh.pa.us>
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