Thread: Query optimization problem
<div class="moz-text-flowed" lang="x-unicode" style="font-family: -moz-fixed; font-size: 13px;"><b>i wrote to <br /> <aclass="moz-txt-link-abbreviated" href="mailto:pgsql-bugs@postgresql.org">pgsql-bugs@postgresql.org</a><br /> they tellme write to<br /> <a class="moz-txt-link-abbreviated" href="mailto:pgsql-performance@postgresql.org">pgsql-performance@postgresql.org</a><br/> they tell me write here</b><br /> <br /><b>I don`t whant know how optimize query myself (i know it), and i think it must do planner.</b><br /><br /> Ihave a query: <br /><br /> SELECT d1.ID, d2.ID <br /> FROM DocPrimary d1 <br /> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID<br /> WHERE (d1.ID=234409763) or (d2.ID=234409763) <br /><br /> i think what QO(Query Optimizer) can makeit faster (now it seq scan and on <br /> million records works 7 sec) <br /> This Query very fast (use indexes) and easymake from first query<br /><br /> SELECT d1.ID, d2.ID <br /> FROM DocPrimary d1 <br /> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID<br /> WHERE (d2.BasedOn=234409763) or (d2.ID=234409763) <br /><br /> Next plans created on table withoutmillion rows data don`t look at exec time<br /><br /> ---------------------- <br /> Slow Query <br /> ----------------------<br /> test=# EXPLAIN (ANALYZE on, VERBOSE on, COSTS on, BUFFERS off )SELECT d1.ID, <br /> d2.ID<br /> test-# FROM DocPrimary d1 <br /> test-# JOIN DocPrimary d2 ON d2.BasedOn=d1.ID <br /> test-# WHERE (d1.ID=234409763)or (d2.ID=234409763); <br /> QUERY PLAN <br /> ------------------------------------------------------------------------------------------------------------------------ <br/> Hash Join (cost=58.15..132.35 rows=2 width=8) (actual time=0.007..0.007 <br /> rows=0 loops=1) <br /> Output:d1.id, d2.id <br /> Hash Cond: (d2.basedon = d1.id) <br /> Join Filter: ((d1.id = 234409763) OR (d2.id =234409763)) <br /> -> Seq Scan on public.docprimary d2 (cost=0.00..31.40 rows=2140 <br /> width=8) (actual time=0.002..0.002rows=0 loops=1) <br /> Output: d2.id, d2.basedon <br /> -> Hash (cost=31.40..31.40rows=2140 width=4) (never executed) <br /> Output: d1.id <br /> -> Seq Scanon public.docprimary d1 (cost=0.00..31.40 rows=2140 <br /> width=4) (never executed) <br /> Output:d1.id <br /><br /> ------------------ <br /> Fast Query <br /> ------------------ <br /> test=# EXPLAIN (ANALYZEon, VERBOSE on, COSTS on, BUFFERS off )SELECT d1.ID, <br /> d2.ID <br /> test-# FROM DocPrimary d1 <br /> test-# JOIN DocPrimary d2 ON d2.BasedOn=d1.ID <br /> test-# WHERE (d2.BasedOn=234409763) or (d2.ID=234409763); <br /> QUERY PLAN <br /> --------------------------------------------------------------------------------------------------------------------------------- <br/> Nested Loop (cost=8.60..58.67 rows=12 width=8) (actual time=0.026..0.026 <br /> rows=0 loops=1) <br /> Output:d1.id, d2.id <br /> -> Bitmap Heap Scan on public.docprimary d2 (cost=8.60..19.31 rows=12 <br /> width=8)(actual time=0.023..0.023 rows=0 loops=1) <br /> Output: d2.id, d2.basedon <br /> RecheckCond: ((d2.basedon = 234409763) OR (d2.id = 234409763)) <br /> -> BitmapOr (cost=8.60..8.60 rows=12width=0) (actual <br /> time=0.018..0.018 rows=0 loops=1) <br /> -> Bitmap Index Scan on basedon_idx (cost=0.00..4.33 <br /> rows=11 width=0) (actual time=0.008..0.008 rows=0 loops=1) <br /> Index Cond: (d2.basedon = 234409763) <br /> -> Bitmap Index Scan on id_pk (cost=0.00..4.26rows=1 <br /> width=0) (actual time=0.003..0.003 rows=0 loops=1) <br /> Index Cond:(d2.id = 234409763) <br /> -> Index Scan using id_pk on public.docprimary d1 (cost=0.00..3.27 <br /> rows=1width=4) (never executed) <br /> Output: d1.id, d1.basedon <br /> Index Cond: (d1.id = d2.basedon)<br /><br /><br /> -------------------------------------------- <br /> PGver: PostgreSQL 9.0b x86 <br /> OS: Win7x64 <br /><br /> --------------------- <br /> Create table query: <br /> --------------------- <br /><br /> CREATE TABLEdocprimary <br /> ( <br /> id integer NOT NULL, <br /> basedon integer, <br /> CONSTRAINT id_pk PRIMARY KEY (id)<br /> ); <br /> CREATE INDEX basedon_idx <br /> ON docprimary <br /> USING btree <br /> (basedon); <br /><br /></div><preclass="moz-signature" cols="72">-- С уважением, Зотов Роман Владимирович руководитель Отдела инструментария ЗАО "НПО Консультант" г.Иваново, ул. Палехская, д. 10 тел./факс: (4932) 41-01-21 mailto: <a class="moz-txt-link-abbreviated" href="mailto:zotov@oe-it.ru">zotov@oe-it.ru</a></pre>
On Tue, Jul 20, 2010 at 1:57 AM, Zotov <zotov@oe-it.ru> wrote: > i wrote to > pgsql-bugs@postgresql.org > they tell me write to > pgsql-performance@postgresql.org > they tell me write here > > I don`t whant know how optimize query myself (i know it), and i think it > must do planner. According to the EXPLAIN ANALYZE output, your "slow" query is executing in 0.007 ms, and your "fast" query is executing in 0.026 ms (i.e. not as quickly as the slow query). Since you mention that it takes 7 s further down, I suspect this is not the real EXPLAIN ANALYZE output on the real data that you're having a problem with. You might have better luck if you post the actual EXPLAIN ANALYZE output here. Incidentally, sorry for not responding sooner to your private email - I was on vacation last week. But please do keep all replies on-list so that everyone can comment. All that having been said, I think the issue here is that the query planner isn't inferring that d1.ID=<some constant> implies d2.ID=<some constant>, even though there's a join clause d1.ID=d2.ID. I'm not really sure why it isn't doing that... I suspect Tom Lane is the only person who can comment intelligently on that, and he's away this week (but if anyone else has an idea, feel free to jump in...). -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise Postgres Company
Robert Haas <robertmhaas@gmail.com> writes: > All that having been said, I think the issue here is that the query > planner isn't inferring that d1.ID=<some constant> implies d2.ID=<some > constant>, even though there's a join clause d1.ID=d2.ID. I think that's what the Equivalence Classes are for. Or at least that's what they do in my head, not forcibly in the code. The specific diff between the two queries is : JOIN DocPrimary d2 ON d2.BasedOn=d1.ID - WHERE (d1.ID=234409763) or (d2.ID=234409763) + WHERE (d2.BasedOn=234409763) or (d2.ID=234409763) So the OP would appreciate that the planner is able to consider applying the restriction on d2.BasedOn rather than d1.ID given that d2.BasedOn is the same thing as d1.ID, from the JOIN. I have no idea if Equivalence Classes are where to look for this, and if they're meant to extend up to there, and if that's something possible or wise to implement, though. Regards, -- dim
On Tue, Jul 20, 2010 at 11:23 AM, Dimitri Fontaine <dfontaine@hi-media.com> wrote: > Robert Haas <robertmhaas@gmail.com> writes: >> All that having been said, I think the issue here is that the query >> planner isn't inferring that d1.ID=<some constant> implies d2.ID=<some >> constant>, even though there's a join clause d1.ID=d2.ID. > > I think that's what the Equivalence Classes are for. Or at least that's > what they do in my head, not forcibly in the code. > > The specific diff between the two queries is : > > JOIN DocPrimary d2 ON d2.BasedOn=d1.ID > - WHERE (d1.ID=234409763) or (d2.ID=234409763) > + WHERE (d2.BasedOn=234409763) or (d2.ID=234409763) > > So the OP would appreciate that the planner is able to consider applying > the restriction on d2.BasedOn rather than d1.ID given that d2.BasedOn is > the same thing as d1.ID, from the JOIN. > > I have no idea if Equivalence Classes are where to look for this, and if > they're meant to extend up to there, and if that's something possible or > wise to implement, though. I was thinking of the equivalence class machinery as well. I think the OR clause may be the problem. If you just had d1.ID=constant, I think it would infer that d1.ID, d2.BasedOn, and the constant formed an equivalence class. But here you obviously can't smash the constant into the equivalence class, and I think the planner's not smart enough to consider other ways of applying an equivalent qual. In fact, I have some recollection that Tom has explicitly rejected adding support for this in the past, on the grounds that the computation would be too expensive for the number of queries it would help. Still, it seems to keep coming up. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise Postgres Company
Robert Haas <robertmhaas@gmail.com> writes: > On Tue, Jul 20, 2010 at 11:23 AM, Dimitri Fontaine > <dfontaine@hi-media.com> wrote: >> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID >> - WHERE (d1.ID=234409763) or (d2.ID=234409763) >> + WHERE (d2.BasedOn=234409763) or (d2.ID=234409763) > > I was thinking of the equivalence class machinery as well. I think > the OR clause may be the problem. If you just had d1.ID=constant, I > think it would infer that d1.ID, d2.BasedOn, and the constant formed > an equivalence class. But here you obviously can't smash the constant > into the equivalence class, and I think the planner's not smart enough > to consider other ways of applying an equivalent qual. In fact, I > have some recollection that Tom has explicitly rejected adding support > for this in the past, on the grounds that the computation would be too > expensive for the number of queries it would help. Still, it seems to > keep coming up. Well what I'm thinking now could have nothing to do with how the code works. I'd have to check, but well, it's easier to write this mail and get the chance to have you wonder :) So, the JOIN condition teaches us that d2.BasedOn=d1.ID, and the OP would want the planner to derive that (d1.ID=234409763) is the same thing as (d2.BasedOn=234409763). I guess it would make sense to produce plans with both the writings and pick one based on the costs. Now, does it make sense to generate this many more plans to analyze in the general case, I have no idea about. But given only one join and only one WHERE clause where the Equivalent applies… Regards, -- dim
On Tue, Jul 20, 2010 at 3:33 PM, Dimitri Fontaine <dfontaine@hi-media.com> wrote: > Robert Haas <robertmhaas@gmail.com> writes: >> On Tue, Jul 20, 2010 at 11:23 AM, Dimitri Fontaine >> <dfontaine@hi-media.com> wrote: >>> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID >>> - WHERE (d1.ID=234409763) or (d2.ID=234409763) >>> + WHERE (d2.BasedOn=234409763) or (d2.ID=234409763) >> >> I was thinking of the equivalence class machinery as well. I think >> the OR clause may be the problem. If you just had d1.ID=constant, I >> think it would infer that d1.ID, d2.BasedOn, and the constant formed >> an equivalence class. But here you obviously can't smash the constant >> into the equivalence class, and I think the planner's not smart enough >> to consider other ways of applying an equivalent qual. In fact, I >> have some recollection that Tom has explicitly rejected adding support >> for this in the past, on the grounds that the computation would be too >> expensive for the number of queries it would help. Still, it seems to >> keep coming up. > > Well what I'm thinking now could have nothing to do with how the code > works. I'd have to check, but well, it's easier to write this mail and > get the chance to have you wonder :) > > So, the JOIN condition teaches us that d2.BasedOn=d1.ID, and the OP > would want the planner to derive that (d1.ID=234409763) is the same > thing as (d2.BasedOn=234409763). I guess it would make sense to produce > plans with both the writings and pick one based on the costs. > > Now, does it make sense to generate this many more plans to analyze in > the general case, I have no idea about. But given only one join and only > one WHERE clause where the Equivalent applies… It seems like deciding which rel to apply the filter condition to would be a fairly expensive optimization. Perhaps we could recognize the special case where substituting another member of the equivalence class allows the qual to be pushed down where it otherwise couldn't be. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise Postgres Company
On Tue, Jul 20, 2010 at 09:57:06AM +0400, Zotov wrote: > SELECT d1.ID, d2.ID > FROM DocPrimary d1 > JOIN DocPrimary d2 ON d2.BasedOn=d1.ID > WHERE (d1.ID=234409763) or (d2.ID=234409763) You could try rewriting it to: SELECT d1.ID, d2.ID FROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.ID WHERE d1.ID=234409763 UNION SELECTd1.ID, d2.ID FROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.ID WHERE d2.ID=234409763 This should have the same semantics as the original query. I don't believe PG knows how to do a rewrite like this at the moment. -- Sam http://samason.me.uk/
20.07.2010 18:31, Robert Haas: <blockquote cite="mid:AANLkTi=S6GjWxeSnoHOeL4ciBA2LcbR6eEZAyEUMFGLM@mail.gmail.com" type="cite"><prewrap="">According to the EXPLAIN ANALYZE output, your "slow" query is executing in 0.007 ms, and your "fast" query is executing in 0.026 ms (i.e. not as quickly as the slow query). Since you mention that it takes 7 s further down, I suspect this is not the real EXPLAIN ANALYZE output on the real data that you're having a problem with. You might have better luck if you post the actual EXPLAIN ANALYZE output here. Incidentally, sorry for not responding sooner to your private email - I was on vacation last week. But please do keep all replies on-list so that everyone can comment. All that having been said, I think the issue here is that the query planner isn't inferring that d1.ID=<some constant> implies d2.ID=<some constant>, even though there's a join clause d1.ID=d2.ID. I'm not really sure why it isn't doing that... I suspect Tom Lane is the only person who can comment intelligently on that, and he's away this week (but if anyone else has an idea, feel free to jump in...). </pre></blockquote> Yes, I have a mistake when EXPLAIN ANALYZEwithout data.. It create another plan, because seq scan were faster. Now I send results on real data (1 million rows)<br/><br /><b>Slow Query:</b><br /> -------------------------------------------------<br /> test=# EXPLAIN (ANALYZEon, VERBOSE on, COSTS on, BUFFERS off )SELECT d1.ID, d2.ID<br /> test-# FROM DocPrimary d1<br /> test-# JOIN DocPrimaryd2 ON d2.BasedOn=d1.ID<br /> test-# WHERE (d1.ID=234409763<br /> test(# ) OR (d2.ID=234409763);<br /> QUERY PLAN<br /> ----------------------------------------------------------------------------------------------------------------------------------------------------------<br /> Merge Join (cost=2222.72..53967.30 rows=1 width=8) (actual time=6697.847..6697.847 rows=0 loops=1)<br /> Output: d1.id,d2.id<br /> Merge Cond: (d1.id = d2.basedon)<br /> Join Filter: ((d1.id = 234409763) OR (d2.id = 234409763))<br/> -> Index Scan using id_pk on public.docprimary d1 (cost=0.00..37224.48 rows=1076842 width=4) (actualtime=0.016..3184.474 rows=1076795 loops=1)<br /> Output: d1.id, d1.basedon<br /> -> Index Scan usingbasedon_idx on public.docprimary d2 (cost=0.00..46245.14 rows=1076842 width=8) (actual time=0.011..1861.570 rows=235362loops=1)<br /> Output: d2.id, d2.basedon<br /> Total runtime: 6697.968 ms<br /> (9 rows)<br /> -----------------------------------------------<br/><br /><b>Fast Query:</b><br /> ----------------------------------------------<br/> test=# EXPLAIN (ANALYZE on, VERBOSE on, COSTS on, BUFFERS off )SELECTd1.ID, d2.ID<br /> test-# FROM DocPrimary d1<br /> test-# JOIN DocPrimary d2 ON d2.BasedOn=d1.ID<br /> test-# WHERE(d1.ID=234409763 and d2.BasedOn=234409763<br /> test(# ) OR (d2.ID=234409763);<br /> QUERY PLAN<br /> ---------------------------------------------------------------------------------------------------------------------------------<br /> Nested Loop (cost=9.01..422.70 rows=1 width=8) (actual time=0.145..0.145 rows=0 loops=1)<br /> Output: d1.id, d2.id<br/> Join Filter: (((d1.id = 234409763) AND (d2.basedon = 234409763)) OR (d2.id = 234409763))<br /> -> BitmapHeap Scan on public.docprimary d2 (cost=9.01..136.90 rows=34 width=8) (actual time=0.141..0.141 rows=0 loops=1)<br/> Output: d2.id, d2.basedon<br /> Recheck Cond: ((d2.basedon = 234409763) OR (d2.id = 234409763))<br/> -> BitmapOr (cost=9.01..9.01 rows=34 width=0) (actual time=0.136..0.136 rows=0 loops=1)<br/> -> Bitmap Index Scan on basedon_idx (cost=0.00..4.62 rows=33 width=0) (actual time=0.078..0.078rows=0 loops=1)<br /> Index Cond: (d2.basedon = 234409763)<br /> -> Bitmap Index Scan on id_pk (cost=0.00..4.38 rows=1 width=0) (actual time=0.051..0.051 rows=0 loops=1)<br /> Index Cond: (d2.id = 234409763)<br /> -> Index Scan using id_pk on public.docprimary d1 (cost=0.00..8.39rows=1 width=4) (never executed)<br /> Output: d1.id, d1.basedon<br /> Index Cond: (d1.id= d2.basedon)<br /> Total runtime: 0.233 ms<br /> (15 rows)<br /> ------------------------------------------<br /><br/> I use another fast query:<br /> SELECT d1.ID, d2.ID<br /> FROM DocPrimary d1<br /> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID<br/> WHERE (<b>d1.ID=234409763 and d2.BasedOn=234409763</b>) OR (d2.ID=234409763)<br /><br /> Bolded partof query was d2.BasedOn=234409763 I replace it because it can help find way to optimize it automaticaly<br /><br /> Sosorry, but i can`t give programmer to do something in Postgres, because<br /> we don`t use it now as supported DB, we thinkabout it and do some tests. <br /> It`s very hard and slow task (support another DB, now we use FireBird, and plan useanother DB, and look for Postgres and MSSQL, maybe support it both as free and commercial DB solution)<br /> And in ourdepartment only 4 (with me) programmers who can programm on "System Level", and only one of us (doesn`t me) know C/C++<br /> We all programming on Delphi... If we choose Postgres as free DB platform then I can think about give programmersfor Postgress development.<br /><br /> In so large letters my English stay more bad :)<br /><br /><br /><br />
Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Jul 20, 2010 at 11:23 AM, Dimitri Fontaine
> <dfontaine@hi-media.com> wrote:
>> The specific diff between the two queries is :
>>
>> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID
>> - WHERE (d1.ID=234409763) or (d2.ID=234409763)
>> + WHERE (d2.BasedOn=234409763) or (d2.ID=234409763)
>>
>> So the OP would appreciate that the planner is able to consider applying
>> the restriction on d2.BasedOn rather than d1.ID given that d2.BasedOn is
>> the same thing as d1.ID, from the JOIN.
>>
>> I have no idea if Equivalence Classes are where to look for this, and if
>> they're meant to extend up to there, and if that's something possible or
>> wise to implement, though.
> I was thinking of the equivalence class machinery as well. I think
> the OR clause may be the problem. If you just had d1.ID=constant, I
> think it would infer that d1.ID, d2.BasedOn, and the constant formed
> an equivalence class.
Right. Because of the OR, it is *not* possible to conclude that
d2.basedon is always equal to 234409763, which is the implication of
putting them into an equivalence class.
In the example, we do have d1.id and d2.basedon grouped in an
equivalence class. So in principle you could substitute d1.id into the
WHERE clause in place of d2.basedon, once you'd checked that it was
being used with an operator that's compatible with the specific
equivalence class (ie it's in one of the eclass's opfamilies, I think).
The problem is to recognize that such a rewrite would be a win --- it
could just as easily be a big loss.
Even if we understood how to direct the rewriting process, I'm really
dubious that it would win often enough to justify the added planning
time. The particular problem here seems narrow enough that solving it
on the client side is probably a whole lot easier and cheaper than
trying to get the planner to do it.
regards, tom lane
Tom Lane <tgl@sss.pgh.pa.us> writes: > In the example, we do have d1.id and d2.basedon grouped in an > equivalence class. So in principle you could substitute d1.id into the > WHERE clause in place of d2.basedon, once you'd checked that it was > being used with an operator that's compatible with the specific > equivalence class (ie it's in one of the eclass's opfamilies, I think). > The problem is to recognize that such a rewrite would be a win --- it > could just as easily be a big loss. Ok, that was my feeling too. > Even if we understood how to direct the rewriting process, I'm really > dubious that it would win often enough to justify the added planning > time. The particular problem here seems narrow enough that solving it > on the client side is probably a whole lot easier and cheaper than > trying to get the planner to do it. My overly naive uneducated idea here would be to produce both the plans and let the planner evaluate their respective costs. Maybe that's what you mean here by "how to direct the rewriting process". Then we don't want to generate too many useless plans when you have lots of eclass around. This brings back the idea of pondering somehow the optimiser effort pushed into "solving" a query plan. Like in gcc we can use different effort targets and we don't know for sure before hand if -O3 will produce faster code than -O2, all we know is that it will try harder. Is it possible to imagine having a plan_eclass_permutations default to false that would activate the discussed behavior here? Ok, I'm not sure what form should take such a setting, but clearly, there's a need to be able to impact the optimiser effort. Regards, -- dim
On Wed, Jul 28, 2010 at 3:45 AM, Dimitri Fontaine <dfontaine@hi-media.com> wrote: >> Even if we understood how to direct the rewriting process, I'm really >> dubious that it would win often enough to justify the added planning >> time. The particular problem here seems narrow enough that solving it >> on the client side is probably a whole lot easier and cheaper than >> trying to get the planner to do it. > > My overly naive uneducated idea here would be to produce both the plans > and let the planner evaluate their respective costs. Maybe that's what > you mean here by "how to direct the rewriting process". Then we don't > want to generate too many useless plans when you have lots of eclass > around. The way the planner is set up, you'd have to plan with qual A, then repeat the entire process with qual B, and then just for good measure repeat the process with both quals A and B. ISTM you'd triple the planning time if there were even just one case of this in a particular query. If you have different ways of generating the same output for a given rel, you can just throw them all into a bucket and let the planner work it out. But here you want to have different paths for the same relation that generate *different output*, and the planner doesn't understand that concept. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise Postgres Company
Robert Haas <robertmhaas@gmail.com> writes: > But here you want to have different paths for > the same relation that generate *different output*, and the planner > doesn't understand that concept. Sorry? I though what Equivalence Class provides is the "proving" that using this qualification or another will *not* affect the output. -- dim
On Wed, Jul 28, 2010 at 6:55 AM, Dimitri Fontaine <dfontaine@hi-media.com> wrote: > Robert Haas <robertmhaas@gmail.com> writes: >> But here you want to have different paths for >> the same relation that generate *different output*, and the planner >> doesn't understand that concept. > > Sorry? I though what Equivalence Class provides is the "proving" that > using this qualification or another will *not* affect the output. In a query like... SELECT d1.ID, d2.IDFROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.IDWHERE (d1.ID=234409763) or (d2.ID=234409763) ...you're going to scan d1, scan d2, and then join the results. The scan of d1 is going to produce different results depending on whether you evaluate or not d1.ID=234409763, and the scan of d2 is going to produce different results depending on whether or not you evaluate d2.BasedOn=234409763. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise Postgres Company
Robert Haas wrote: > On Wed, Jul 28, 2010 at 6:55 AM, Dimitri Fontaine > <dfontaine@hi-media.com> wrote: > >> Robert Haas <robertmhaas@gmail.com> writes: >> >>> But here you want to have different paths for >>> the same relation that generate *different output*, and the planner >>> doesn't understand that concept. >>> >> Sorry? I though what Equivalence Class provides is the "proving" that >> using this qualification or another will *not* affect the output. >> > > In a query like... > > SELECT d1.ID, d2.ID > FROM DocPrimary d1 > JOIN DocPrimary d2 ON d2.BasedOn=d1.ID > WHERE (d1.ID=234409763) or (d2.ID=234409763) > > ...you're going to scan d1, scan d2, and then join the results. The > scan of d1 is going to produce different results depending on whether > you evaluate or not d1.ID=234409763, and the scan of d2 is going to > produce different results depending on whether or not you evaluate > d2.BasedOn=234409763. > Wouldn't it be relatively easy, to rewrite the filter expression by adding expressions, instead of replacing constants, in the disjunctive case, so the example at hand would become: WHERE (d1.ID=234409763) or (d2.ID=234409763) AND (d2.BasedOnID=234409763) or (d2.ID=234409763) regards, Yeb Havinga
On Wed, Jul 28, 2010 at 7:24 AM, Yeb Havinga <yebhavinga@gmail.com> wrote: >>> Sorry? I though what Equivalence Class provides is the "proving" that >>> using this qualification or another will *not* affect the output. >> >> In a query like... >> >> SELECT d1.ID, d2.ID >> FROM DocPrimary d1 >> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID >> WHERE (d1.ID=234409763) or (d2.ID=234409763) >> >> ...you're going to scan d1, scan d2, and then join the results. The >> scan of d1 is going to produce different results depending on whether >> you evaluate or not d1.ID=234409763, and the scan of d2 is going to >> produce different results depending on whether or not you evaluate >> d2.BasedOn=234409763. > > Wouldn't it be relatively easy, to rewrite the filter expression by adding > expressions, instead of replacing constants, in the disjunctive case, so the > example at hand would become: > > WHERE (d1.ID=234409763) or (d2.ID=234409763) > AND (d2.BasedOnID=234409763) or (d2.ID=234409763) Yeah, that could be done, but it's not necessarily a win from a performance standpoint. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise Postgres Company
Robert Haas <robertmhaas@gmail.com> writes: > SELECT d1.ID, d2.ID > FROM DocPrimary d1 > JOIN DocPrimary d2 ON d2.BasedOn=d1.ID > WHERE (d1.ID=234409763) or (d2.ID=234409763) > > ...you're going to scan d1, scan d2, and then join the results. The > scan of d1 is going to produce different results depending on whether > you evaluate or not d1.ID=234409763, and the scan of d2 is going to > produce different results depending on whether or not you evaluate > d2.BasedOn=234409763. Well I just realised you can't use d2.BasedOn in scanning d1 here. I don't know what exactly I had in mind previously, but in any case, sorry for the noise. I hope the optimiser effort control still hold water nonetheless… -- dim
Robert Haas wrote: > On Wed, Jul 28, 2010 at 7:24 AM, Yeb Havinga <yebhavinga@gmail.com> wrote: > >>>> Sorry? I though what Equivalence Class provides is the "proving" that >>>> using this qualification or another will *not* affect the output. >>>> >>> In a query like... >>> >>> SELECT d1.ID, d2.ID >>> FROM DocPrimary d1 >>> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID >>> WHERE (d1.ID=234409763) or (d2.ID=234409763) >>> >>> ...you're going to scan d1, scan d2, and then join the results. The >>> scan of d1 is going to produce different results depending on whether >>> you evaluate or not d1.ID=234409763, and the scan of d2 is going to >>> produce different results depending on whether or not you evaluate >>> d2.BasedOn=234409763. >>> >> Wouldn't it be relatively easy, to rewrite the filter expression by adding >> expressions, instead of replacing constants, in the disjunctive case, so the >> example at hand would become: >> >> WHERE (d1.ID=234409763) or (d2.ID=234409763) >> AND (d2.BasedOnID=234409763) or (d2.ID=234409763) >> > > Yeah, that could be done, but it's not necessarily a win from a > performance standpoint. > Not necessarily a win, but on the test case no significant increase in planning time. It somehow feels like a good idea to give the planner as much information as possible, i.e. for each rel as much baserestrictinfo's. I earlier forgot parentheses, the correct query is SELECT d1.ID, d2.IDFROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.ID WHERE ((d1.ID=234409763) or (d2.ID=234409763))AND((d2.BasedOn=234409763) or (d2.ID=234409763)); by doing this in the rewrite step, triple planning would be avoided. I suspect that a copyObject of the expression + expression tree mutator call time during rewrite is negligible compared to plan time, assuming this is minimal, in this particulare case there doesn't seem to be much planning time between the three variants. I ran the script below a number of times, the third time is the one with expanded expression: Time: 0.820 ms Time: 0.859 ms Time: 0.877 ms --- Time: 0.617 ms Time: 0.662 ms Time: 0.737 ms --- Time: 0.817 ms Time: 0.766 ms Time: 0.826 ms --- Time: 0.638 ms Time: 0.700 ms Time: 0.706 ms --- Time: 0.463 ms Time: 0.847 ms Time: 0.793 ms --- Time: 0.629 ms Time: 0.671 ms Time: 0.703 ms this was the script (on the relation and index supplied by the OP) -- warm catalog explain SELECT d1.ID, d2.IDFROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.ID WHERE (d1.ID=234409763) or (d2.ID=234409763); \timing explain SELECT d1.ID, d2.IDFROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.ID WHERE (d1.ID=234409763) or (d2.ID=234409763); explain SELECT d1.ID, d2.IDFROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.ID WHERE (d2.BasedOn=234409763) or (d2.ID=234409763); explain SELECT d1.ID, d2.IDFROM DocPrimary d1 JOIN DocPrimary d2 ON d2.BasedOn=d1.ID WHERE ((d1.ID=234409763) or (d2.ID=234409763))AND((d2.BasedOn=234409763) or (d2.ID=234409763));
Yeb Havinga <yebhavinga@gmail.com> writes:
> Robert Haas wrote:
>> On Wed, Jul 28, 2010 at 7:24 AM, Yeb Havinga <yebhavinga@gmail.com> wrote:
>>> Wouldn't it be relatively easy, to rewrite the filter expression by adding
>>> expressions, instead of replacing constants, in the disjunctive case, so the
>>> example at hand would become:
>>>
>>> WHERE (d1.ID=234409763) or (d2.ID=234409763)
>>> AND (d2.BasedOnID=234409763) or (d2.ID=234409763)
>> Yeah, that could be done, but it's not necessarily a win from a
>> performance standpoint.
> Not necessarily a win, but on the test case no significant increase in
> planning time.
The problem is that it could cost you a lot in execution time, because
of the useless extra filter conditions that will be applied. The
planner isn't going to notice that those conditions are redundant.
An even worse problem is that because it doesn't know that, it's going
to underestimate the combined selectivity of the two WHERE conditions,
resulting in drastic underestimates of the numbers of rows emitted,
possibly resulting in horribly bad plan choices that kill whatever
performance improvement you got at the bottom level.
What the EquivalenceClass machinery actually buys us is the ability to
deal with a set of partially-redundant possible filter conditions and
apply only enough of them to get a correct plan. As an example, if the
query has A=B and B=C, we could deduce A=C, but we don't want to apply
all three equality conditions at runtime. Instead we put all three
variables into an EC, and then there is logic to determine which of the
equality clauses implied by the EC should actually get applied where.
This avoids both the useless-checks-at-runtime problem and the problem
of wrong selectivity estimates.
To do something like this without generating stupid plans, we'd need
some sort of generalized EC mechanism that could figure out which
variants of the clause made the most sense in different contexts.
Or maybe something else entirely --- but just generating a lot of
variants of a clause and throwing them all into the existing mechanism
is not workable.
regards, tom lane
27.07.2010 21:37, Tom Lane пишет:<br /><blockquote cite="mid:9993.1280252222@sss.pgh.pa.us" type="cite"><pre
wrap="">Right. Because of the OR, it is *not* possible to conclude that
d2.basedon is always equal to 234409763, which is the implication of
putting them into an equivalence class.
In the example, we do have d1.id and d2.basedon grouped in an
equivalence class. So in principle you could substitute d1.id into the
WHERE clause in place of d2.basedon, once you'd checked that it was
being used with an operator that's compatible with the specific
equivalence class (ie it's in one of the eclass's opfamilies, I think).
The problem is to recognize that such a rewrite would be a win --- it
could just as easily be a big loss.
Even if we understood how to direct the rewriting process, I'm really
dubious that it would win often enough to justify the added planning
time. The particular problem here seems narrow enough that solving it
on the client side is probably a whole lot easier and cheaper than
trying to get the planner to do it.
regards, tom lane </pre></blockquote> So sorry, Tom. As I can understand you. You wouldn`t do something about
it.I think, what this problem can show class of optimization problems.<br /> This query:<br /><b>SLOW</b><br /><br />
SELECTd1.ID, d2.ID<br /> FROM DocPrimary d1<br /> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID<br /> WHERE
(<b>d1.ID=234409763</b>and <b>d2.BasedOn=d1.id</b><br /> ) OR (d2.ID=234409763);<br /><br /><b>FAST</b><br /><br />
SELECTd1.ID, d2.ID<br /> FROM DocPrimary d1<br /> JOIN DocPrimary d2 ON d2.BasedOn=d1.ID<br /> WHERE
(<b>d1.ID=234409763</b>and <b>d2.BasedOn=234409763</b><br /> ) OR (d2.ID=234409763);<br /><br /> If i use constant
obvious,it works use fast plan. I think query optimizer can do this.<br /> I hope you do something to make this query
faster/<br/> Thank You.<br /><br /><pre class="moz-signature" cols="72">--
С уважением,
Зотов Роман Владимирович
руководитель Отдела инструментария
ЗАО "НПО Консультант"
г.Иваново, ул. Палехская, д. 10
тел./факс: (4932) 41-01-21
mailto: <a class="moz-txt-link-abbreviated" href="mailto:zotov@oe-it.ru">zotov@oe-it.ru</a></pre>