Обсуждение: b1 OR b2 <-> ( CASE WHEN b1 THE true ELSE b2 END ): performance bottleneck on logical OR
b1 OR b2 <-> ( CASE WHEN b1 THE true ELSE b2 END ): performance bottleneck on logical OR
От
Cédric Dufour
Дата:
Testing and optimizing queries on large tables (1mio rows), I used two different ways to obtain a logical OR expression: 1. exp1 OR exp2 2. ( CASE WHEN exp1 THE true ELSE exp2 END ) And 2. proved to be twice quicker as 1. in the ideal case where exp1 is always true !!! This tends to prove that the normal OR expression evaluates both left and right expression, though evaluating the right expression is useless provided the left expression is true. This also leads to some programming complication, as for example when writing triggers: IF ( ( TG_OP = 'INSERT' ) OR ( ( TG_OP = 'UPDATE' ) AND ( old.X != new.X ) ) ) THEN -- Do actions depending on field X when inserted or when **changed** (thus avoiding useless action if field X didn't change) END IF; According to high-level programming language, one would expect this IF-THEN expression to work... but it doesn't, because if ( TG_OP = 'INSERT' ) is true, the right part of the OR expression still gets evaluated and an error is raised, since 'old' variable is not defined for INSERT action. This sounds rather trivial, but shouldn't the query optimizer somehow avoid this un-necessary evaluation (and behave just as C, Java or other programming language do) ? Cédric Dufour
=?iso-8859-1?Q?C=E9dric_Dufour?= <cedric.dufour@freesurf.ch> writes: > This tends to prove that the normal OR expression evaluates both left and > right expression, though evaluating the right expression is useless provided > the left expression is true. It proves no such thing. How about showing us what you actually did, rather than jumping to (incorrect) conclusions? regards, tom lane
=?iso-8859-1?Q?C=E9dric_Dufour?= <cedric.dufour@freesurf.ch> writes: > Regarding the trigger problem, it is exactly as I have described it in the > first place: > IF ( ( TG_OP = 'INSERT' ) OR ( ( TG_OP = 'UPDATE' ) AND ( old.X != > new.X ) ) ) THEN > -- Do actions depending on field X when inserted or when **changed** (thus > avoiding useless action if field X didn't change) > END IF; > --> Error on **insert**: 'record old is unassigned yet'. Am I wrong assuming > that even though the ( TG_OP = 'INSERT' ) is true and ( TG_OP = 'UPDATE' ) > is false, ( old.X != new.X ) seems to be evaluated ? ( which causes the > error ) It wouldn't get evaluated if TG_OP = 'INSERT' ... but plpgsql has to insert all the parameters of the IF expression before it passes the IF expression off to the main executor. So you're bombing out at the parameter-interpretation stage. I think you'll have to divide this into two plpgsql IF statements. > FROM > owner > INNER JOIN > folder > ON ( folder.PK = folder.FK_owner ) Surely that join condition is wrong. > WHERE > owner.admin_bool OR > ( > folder.enabled_bool > AND ( ( folder.enable_date IS NULL ) OR ( folder.enable_date <= > CURRENT_TIMESTAMP ) ) > AND ( ( folder.Disable_date IS NULL ) OR ( folder.disable_date > > CURRENT_TIMESTAMP ) ) > item.enabled_bool > AND ( ( item.enable_date IS NULL ) OR ( item.enable_date <= > CURRENT_TIMESTAMP ) ) > AND ( ( item.disable_date IS NULL ) OR ( item.disable_date > > CURRENT_TIMESTAMP ) ) > ) I'm having a hard time making sense of this, since both your examples contain the same typo --- I imagine there's an AND or OR before item.enabled_bool, but it's hard to guess which. However, I suspect the issue is that the planner tries to flatten the above WHERE into conjunctive normal form, which is normally a good optimization strategy but perhaps doesn't work real well on this case. Still that could only affect the boolean-expression evaluation time, and it's hard to believe that that's a large fraction of the total join time. What does EXPLAIN ANALYZE say about the plans for these queries? And could we see them in typo-free form? regards, tom lane
=?iso-8859-1?Q?C=E9dric_Dufour?= <cedric.dufour@freesurf.ch> writes: > It appears that in the ( CASE WHEN ... THEN true ELSE ... END ) case, the > planner uses a 'hash' join that is achieved much quicker > than the related 'nest loop' it chooses in the ( ... OR ... ) case. I'd like to see more details. What is evidently happening is that the planner takes your given condition, which is an OR/AND of conditions on Session, Owner, and both, and rewrites it into a CNF (AND/OR) form in which some of the conjuncts are on only Session or only Owner. These conjuncts can then be pushed down to the individual table scans rather than applied at the level of the join. Now as far as I can see, this pushing-down is a good thing and should always happen. The difficulty seems to be that the planner mis-estimates the selectivity of the pushed-down condition and deduces a too-small output row count, causing a change in a higher plan level from hash join to nestloop. Unfortunately you didn't show the whole plan, and it looks like the error is in the part you didn't show. 7.3 development sources would be more useful for investigating this than prior releases, since the current EXPLAIN code shows the conditions being tested at each plan node, not only the node type. Would you be interested in trying your example on a development system, or sending me enough data to let me reproduce the example here? regards, tom lane
Re: b1 OR b2 <-> ( CASE WHEN b1 THE true ELSE b2 END ): performance bottleneck on logical OR
От
Cédric Dufour
Дата:
Regarding the trigger problem, it is exactly as I have described it in the first place: IF ( ( TG_OP = 'INSERT' ) OR ( ( TG_OP = 'UPDATE' ) AND ( old.X != new.X ) ) ) THEN -- Do actions depending on field X when inserted or when **changed** (thus avoiding useless action if field X didn't change) END IF; --> Error on **insert**: 'record old is unassigned yet'. Am I wrong assuming that even though the ( TG_OP = 'INSERT' ) is true and ( TG_OP = 'UPDATE' ) is false, ( old.X != new.X ) seems to be evaluated ? ( which causes the error ) As for what I actually did, it looks like (it is a query that simulate permissions management, much the same as on a file system): ***** * 1 * ***** SELECT ( CASE WHEN owner.admin_bool THEN true ELSE COALESCE( item_token.permit_bool, folder_token.permit_bool, owner.permit_bool ) END ) AS permit_bool FROM owner INNER JOIN folder ON ( folder.PK = folder.FK_owner ) LEFT JOIN folder_token ON ( folder.PK = folder_token.PK ) INNER JOIN item ON ( folder.PK = item.FK_folder ) LEFT JOIN item_token ON ( item.PK = item_token.PK ) WHERE ( CASE WHEN owner.admin_bool THEN true ELSE ( folder.enabled_bool AND ( ( folder.enable_date IS NULL ) OR ( folder.enable_date <= CURRENT_TIMESTAMP ) ) AND ( ( folder.Disable_date IS NULL ) OR ( folder.disable_date > CURRENT_TIMESTAMP ) ) item.enabled_bool AND ( ( item.enable_date IS NULL ) OR ( item.enable_date <= CURRENT_TIMESTAMP ) ) AND ( ( item.disable_date IS NULL ) OR ( item.disable_date > CURRENT_TIMESTAMP ) ) END ) ***** * 2 * ***** SELECT ( owner.admin_bool OR COALESCE( item_token.permit_bool, folder_token.permit_bool, owner.permit_bool ) ) AS permit_bool FROM owner INNER JOIN folder ON ( folder.PK = folder.FK_owner ) LEFT JOIN folder_token ON ( folder.PK = folder_token.PK ) INNER JOIN item ON ( folder.PK = item.FK_folder ) LEFT JOIN item_token ON ( item.PK = item_token.PK ) WHERE owner.admin_bool OR ( folder.enabled_bool AND ( ( folder.enable_date IS NULL ) OR ( folder.enable_date <= CURRENT_TIMESTAMP ) ) AND ( ( folder.Disable_date IS NULL ) OR ( folder.disable_date > CURRENT_TIMESTAMP ) ) item.enabled_bool AND ( ( item.enable_date IS NULL ) OR ( item.enable_date <= CURRENT_TIMESTAMP ) ) AND ( ( item.disable_date IS NULL ) OR ( item.disable_date > CURRENT_TIMESTAMP ) ) ) owner is 100 rows, folder is 10'000 rows, item is 1'000'000 rows no indexes on the columns involved in the boolean expressions In the case where 'owner.admin_bool' is always true, *1* executed 2 to 3 times faster as *2* (after launching a new connection for each scenario - in order to have a "clean" backend process - and running the query several times for each scenario - no changes on the data - and taking the average runtime value, once it is stable ). Am I missing something ? Regards, Cedric Dufour > -----Original Message----- > From: Tom Lane [mailto:tgl@sss.pgh.pa.us] > Sent: Friday, August 02, 2002 21:40 > To: Cédric Dufour > Cc: pgsql-general@postgresql.org > Subject: Re: [GENERAL] b1 OR b2 <-> ( CASE WHEN b1 THE true ELSE b2 END > ): performance bottleneck on logical OR > > > =?iso-8859-1?Q?C=E9dric_Dufour?= <cedric.dufour@freesurf.ch> writes: > > This tends to prove that the normal OR expression evaluates > both left and > > right expression, though evaluating the right expression is > useless provided > > the left expression is true. > > It proves no such thing. How about showing us what you actually did, > rather than jumping to (incorrect) conclusions? > > regards, tom lane >
Re: b1 OR b2 <-> ( CASE WHEN b1 THE true ELSE b2 END ): performance bottleneck on logical OR
От
Cédric Dufour
Дата:
OK, TOM, SORRY FOR THE **INCORRECT** CONCLUSIONS ! I tried to reproduce the problem with a simpler scenario than the one that actually made me investigate the matter (the 'explain analyze' output being more than 500 lines long...)... but the problem didn't re-occur. So I tried to understand where the execution plan changed and why (comparing 2000 lines of 'explain analyze' output from my initial scenario). Here is what I got: 1. this delay (I won't call it a problem anylonger) occurs only when NESTLOOP and MERGEJOIN have been disabled **AND** 2. the FROM clause from one of the base view is changed **FROM** FROM tb_Login AS Login_default, vw_Session AS Session INNER JOIN tb_Owner AS Owner ON ( CASE WHEN ( Session.Admin_flag AND ( ( Session.FK_Owner = 0 ) OR ( Session.FK_Owner = Owner.PK ) ) ) THEN true ELSE ( ( ( Session.FK_Owner_screen = Owner.PK ) OR ( ( Session.FK_Owner_screen = 0 ) AND Owner.Share_flag ) ) AND ( Owner.Enable_flag AND ( ( Owner.Enable_date IS NULL ) OR ( Owner.Enable_date <= CURRENT_TIMESTAMP ) ) AND ( ( Owner.Disable_date IS NULL ) OR ( Owner.Disable_date > CURRENT_TIMESTAMP ) ) ) ) END ) LEFT JOIN vw_Owner_prv AS Owner_prv ON ( Owner.PK = Owner_prv.FK_Owner ) LEFT JOIN vw_Owner_loc AS Owner_loc ON ( Owner.PK = Owner_loc.FK_Owner ) WHERE ( Login_default.PK = 0 ) ** TO ** FROM tb_Login AS Login_default, vw_Session AS Session INNER JOIN tb_Owner AS Owner ** ON ( ( Session.Admin_flag AND ( ( Session.FK_Owner = 0 ) OR ( Session.FK_Owner = Owner.PK ) ) ) OR ** ( ** ( ( Session.FK_Owner_screen = Owner.PK ) OR ( ( Session.FK_Owner_screen = 0 ) AND Owner.Share_flag ) ) ** AND ** ( Owner.Enable_flag AND ( ( Owner.Enable_date IS NULL ) OR ( Owner.Enable_date <= CURRENT_TIMESTAMP ) ) AND ( ( Owner.Disable_date IS NULL ) OR ( Owner.Disable_date > CURRENT_TIMESTAMP ) ) ) ** ) ) LEFT JOIN vw_Owner_prv AS Owner_prv ON ( Owner.PK = Owner_prv.FK_Owner ) LEFT JOIN vw_Owner_loc AS Owner_loc ON ( Owner.PK = Owner_loc.FK_Owner ) WHERE ( Login_default.PK = 0 ) Causing the execution plan to been altered **FROM** Limit (cost=800023564.12..800155912.10 rows=100 width=7915) (actual time=3039.00..3148.00 rows=100 loops=1) -> Hash Join (cost=800023564.12..803266109.18 rows=2450 width=7915) (actual time=3039.00..3148.00 rows=101 loops=1) -> Hash Join (cost=700023184.11..703265708.65 rows=2450 width=7879) (actual time=3031.00..3125.00 rows=101 loops=1) -> Hash Join (cost=600022804.96..603265316.19 rows=2450 width=7843) (actual time=3022.00..3097.00 rows=101 loops=1) -> Hash Join (cost=500022424.95..503264643.05 rows=35000 width=7286) (actual time=3013.00..3071.00 rows=101 loops=1) -> Hash Join (cost=400022045.81..403258826.37 rows=1000006 width=6729) (actual time=2997.00..3033.00 rows=101 loops=1) -> Hash Join (cost=400021945.70..403253725.96 rows=1000006 width=6720) (actual time=2995.00..3023.00 rows=101 loops=1) -> Hash Join (cost=400021845.59..403248625.76 rows=1000006 width=4890) (actual time=2993.00..3014.00 rows=101 loops=1) -> Seq Scan on tb_item item (cost=0.00..34708.06 rows=1000006 width=2727) (actual time=921.00..928.00 rows=526 loops=1) -> Hash (cost=400019143.59..400019143.59 rows=10001 width=2163) (actual time=2068.00..2068.00 rows=0 loops=1) -> Hash Join (cost=400000925.60..400019143.59 rows=10001 width=2163) (actual time=909.00..1996.00 rows=10001 loops=1) ********** -> Hash Join (cost=200000562.91..200016130.63 rows=10001 width=1940) (actual time=892.00..1641.00 rows=10001 loops=1) -> Hash Join (cost=200000462.80..200015980.14 rows=10001 width=1931) (actual time=890.00..1433.00 rows=10001 loops=1) -> Hash Join (cost=200000362.69..200015829.97 rows=10001 width=1133) (actual time=888.00..1210.00 rows=10001 loops=1) -> Seq Scan on tb_folder folder (cost=0.00..12817.01 rows=10001 width=1062) (actual time=872.00..957.00 rows=10001 loops=1) -> Hash (cost=200000360.19..200000360.19 rows=1000 width=71) (actual time=16.00..16.00 rows=0 loops=1) -> Nested Loop (cost=200000250.23..200000360.19 rows=1000 width=71) (actual time=15.00..16.00 rows=101 loops=1) -> Index Scan using pk_login on tb_login login_default (cost=0.00..4.82 rows=1 width=8) (actual time=0.00..0.00 rows=1 loops=1) -> Materialize (cost=100000345.37..100000345.37 rows=1000 width=63) (actual time=15.00..15.00 rows=101 loops=1) and so on... ** TO ** Limit (cost=1024749076.40..1024788787.84 rows=1 width=7915) (actual time=18387.00..18490.00 rows=100 loops=1) -> Hash Join (cost=1024749076.40..1024788787.84 rows=1 width=7915) (actual time=18386.00..18489.00 rows=101 loops=1) -> Hash Join (cost=924748696.39..924788407.83 rows=1 width=7879) (actual time=18377.00..18458.00 rows=101 loops=1) -> Hash Join (cost=824748317.24..824788028.67 rows=1 width=7843) (actual time=18369.00..18421.00 rows=101 loops=1) -> Hash Join (cost=724747937.23..724787648.65 rows=1 width=7286) (actual time=18361.00..18397.00 rows=101 loops=1) -> Hash Join (cost=624747558.08..624787269.30 rows=38 width=6729) (actual time=18353.00..18382.00 rows=101 loops=1) -> Hash Join (cost=624747457.98..624787169.01 rows=38 width=4899) (actual time=18350.00..18372.00 rows=101 loops=1) -> Hash Join (cost=624747357.87..624787068.71 rows=38 width=4890) (actual time=18348.00..18365.00 rows=101 loops=1) -> Seq Scan on tb_item item (cost=0.00..34708.06 rows=1000006 width=2727) (actual time=912.00..915.00 rows=101 loops=1) -> Hash (cost=624747357.87..624747357.87 rows=1 width=2163) (actual time=17436.00..17436.00 rows=0 loops=1) -> Hash Join (cost=624734464.94..624747357.87 rows=1 width=2163) (actual time=909.00..17359.00 rows=10001 loops=1) *********** -> Nested Loop (cost=424734074.85..424746967.77 rows=1 width=1940) (actual time=892.00..16318.00 rows=10001 loops=1) -> Hash Join (cost=324733999.82..324746867.61 rows=1 width=1142) (actual time=889.00..2391.00 rows=10001 loops=1) -> Hash Join (cost=324733899.71..324746767.50 rows=1 width=1133) (actual time=887.00..1859.00 rows=10001 loops=1) -> Seq Scan on tb_folder folder (cost=0.00..12817.01 rows=10001 width=1062) (actual time=871.00..1209.00 rows=10001 loops=1) -> Hash (cost=324733899.71..324733899.71 rows=1 width=71) (actual time=16.00..16.00 rows=0 loops=1) -> Nested Loop (cost=324733759.85..324733899.71 rows=1 width=71) (actual time=16.00..16.00 rows=101 loops=1) -> Index Scan using pk_login on tb_login login_default (cost=0.00..4.82 rows=1 width=8) (actual time=0.00..0.00 rows=1 loops=1) -> Materialize (cost=224733894.88..224733894.88 rows=1 width=63) (actual time=16.00..16.00 rows=101 loops=1) and so on... So, to put it bluntly, this is just the result of my messing up with the planner and some fancy querying ! It appears that in the ( CASE WHEN ... THEN true ELSE ... END ) case, the planner uses a 'hash' join that is achieved much quicker than the related 'nest loop' it chooses in the ( ... OR ... ) case. My mis-understanding... Regards, Cedric Dufour > -----Original Message----- > From: Tom Lane [mailto:tgl@sss.pgh.pa.us] > Sent: Saturday, August 03, 2002 1:41 > To: Cédric Dufour > Cc: pgsql-general@postgresql.org > Subject: Re: [GENERAL] b1 OR b2 <-> ( CASE WHEN b1 THE true ELSE b2 END > ): performance bottleneck on logical OR > > > =?iso-8859-1?Q?C=E9dric_Dufour?= <cedric.dufour@freesurf.ch> writes: > > Regarding the trigger problem, it is exactly as I have > described it in the > > first place: > > > IF ( ( TG_OP = 'INSERT' ) OR ( ( TG_OP = 'UPDATE' ) AND ( old.X != > > new.X ) ) ) THEN > > -- Do actions depending on field X when inserted or when > **changed** (thus > > avoiding useless action if field X didn't change) > > END IF; > > > --> Error on **insert**: 'record old is unassigned yet'. Am I > wrong assuming > > that even though the ( TG_OP = 'INSERT' ) is true and ( TG_OP = > 'UPDATE' ) > > is false, ( old.X != new.X ) seems to be evaluated ? ( which causes the > > error ) > > It wouldn't get evaluated if TG_OP = 'INSERT' ... but plpgsql has to > insert all the parameters of the IF expression before it passes the IF > expression off to the main executor. So you're bombing out at the > parameter-interpretation stage. I think you'll have to divide this into > two plpgsql IF statements. > > > FROM > > owner > > INNER JOIN > > folder > > ON ( folder.PK = folder.FK_owner ) > > Surely that join condition is wrong. > > > WHERE > > owner.admin_bool OR > > ( > > folder.enabled_bool > > AND ( ( folder.enable_date IS NULL ) OR ( > folder.enable_date <= > > CURRENT_TIMESTAMP ) ) > > AND ( ( folder.Disable_date IS NULL ) OR ( > folder.disable_date > > > CURRENT_TIMESTAMP ) ) > > item.enabled_bool > > AND ( ( item.enable_date IS NULL ) OR ( item.enable_date <= > > CURRENT_TIMESTAMP ) ) > > AND ( ( item.disable_date IS NULL ) OR ( item.disable_date > > > CURRENT_TIMESTAMP ) ) > > ) > > I'm having a hard time making sense of this, since both your examples > contain the same typo --- I imagine there's an AND or OR before > item.enabled_bool, but it's hard to guess which. > > However, I suspect the issue is that the planner tries to flatten the > above WHERE into conjunctive normal form, which is normally a good > optimization strategy but perhaps doesn't work real well on this case. > Still that could only affect the boolean-expression evaluation time, > and it's hard to believe that that's a large fraction of the total > join time. > > What does EXPLAIN ANALYZE say about the plans for these queries? > And could we see them in typo-free form? > > regards, tom lane >