
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.



Wed, 20 Aug 2003 09:27:34 -0700 (PDT)
Stephan Szabo <sszabo@megazone.bigpanda.com>
Re: "SELECT IN" Still Broken in 7.4b
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



Wed, 20 Aug 2003 10:45:37 -0600 (CST)
Mike Winter <mike.winter@frontlogic.com>
Re: "SELECT IN" Still Broken in 7.4b
> 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.
Wed, 20 Aug 2003 17:09:46 +0000
Rod Taylor <rbt@rbt.ca>
Re: "SELECT IN" Still Broken in 7.4b

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.




Wed, 20 Aug 2003 10:41:09 -0700 (PDT)
Stephan Szabo <sszabo@megazone.bigpanda.com>
Re: "SELECT IN" Still Broken in 7.4b
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.
Wed, 20 Aug 2003 20:41:32 +0000
Rod Taylor <rbt@rbt.ca>
Re: "SELECT IN" Still Broken in 7.4b

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



Wed, 20 Aug 2003 14:55:17 -0700 (PDT)
Stephan Szabo <sszabo@megazone.bigpanda.com>
Re: "SELECT IN" Still Broken in 7.4b
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

Thu, 21 Aug 2003 11:38:41 +0400 (MSD)
Oleg Bartunov <oleg@sai.msu.su>
Re: "SELECT IN" Still Broken in 7.4b
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


Thu, 21 Aug 2003 12:05:14 +0200
Dani Oderbolz <oderbolz@ecologic.de>
Re: "SELECT IN" Still Broken in 7.4b
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.



Thu, 21 Aug 2003 10:28:53 -0700 (PDT)
Stephan Szabo <sszabo@megazone.bigpanda.com>
Re: "SELECT IN" Still Broken in 7.4b
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

Thu, 21 Aug 2003 16:42:20 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 

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.


Thu, 21 Aug 2003 14:07:08 -0700 (PDT)
Stephan Szabo <sszabo@megazone.bigpanda.com>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 
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

Thu, 21 Aug 2003 23:18:04 +0200
Manfred Koizar <mkoi-pg@aon.at>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 
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


Thu, 21 Aug 2003 14:19:47 -0700
Josh Berkus <josh@agliodbs.com>
Re: [SQL] "SELECT IN" Still Broken in 7.4b
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

Thu, 21 Aug 2003 17:46:03 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 
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


Thu, 21 Aug 2003 15:01:46 -0700
Joe Conway <mail@joeconway.com>
Re: [SQL] "SELECT IN" Still Broken in 7.4b
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

Thu, 21 Aug 2003 18:17:55 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 
> 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


Fri, 22 Aug 2003 09:40:45 +0800
"Christopher Kings-Lynne" <chriskl@familyhealth.com.au>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 
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.


Fri, 22 Aug 2003 20:41:25 +0530
"Shridhar Daithankar" <shridhar_daithankar@persistent.co.in>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 

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


22 Aug 2003 11:28:55 -0400
Greg Stark <gsstark@mit.edu>
Re: [SQL] "SELECT IN" Still Broken in 7.4b
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?


Fri, 22 Aug 2003 08:47:30 -0700 (PDT)
Stephan Szabo <sszabo@megazone.bigpanda.com>
Re: [SQL] "SELECT IN" Still Broken in 7.4b
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

Sun, 24 Aug 2003 17:37:14 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: [SQL] "SELECT IN" Still Broken in 7.4b 