[Maria-developers] MDEV-9712 Performance degradation of nested NULLIF
Hello Sergei, Please have a look into a draft fix for MDEV-9712. The problem happens because in 10.1 execution time for various recursive stages (like walk, update_used_table and propagate_equal_fields) in NULLIF is O(recursion_level^2), because complexity is doubled on every recursion level when we copy args[0] to args[2]. This fix simplifies some stages to make them faster. It reduced execution time from 144 seconds to 12 seconds. The idea is just not to iterate through args[2] when it's just a copy of args[0] in these stages: - Item_func_nullif::walk - Item_func_nullif::update_used_tables I'm not fully sure that skipping args[2] is always correct though. For some transformers it may not be correct. <offtopic> Btw, walk() can be called from the partitioning code when arg_count is still 2 rather than 3. Looks suspicious. Perhaps there is a hidden bug behind that. </offtopic> The remaining heavy piece of the code is: Item* propagate_equal_fields(THD *thd, const Context &ctx, COND_EQUAL *cond) { Context cmpctx(ANY_SUBST, cmp.compare_type(), cmp.compare_collation()); args[0]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[0]); args[1]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[1]); args[2]->propagate_equal_fields_and_change_item_tree(thd, Context_identity(), cond, &args[2]); return this; } We cannot use the same approach here, because args[0] and args[2] are propagated with a different context (ANY_SUBST vs IDENTITY_SUBST). Not sure what to do with this. Perhaps, data types could have an extra attribute to tell that ANY_SUBST and IDENITTY_SUBST are equal. So, for example, for non-ZEROFILL integers, ANY_SUBST and IDENTITY_SUBST do the same thing and thus propagation could be done one time only. But this would be a partial solution, for a limited number of data types. Another option is to leave propagation as is. Another option is do nothing at all. If we rewrite the reported query as CASE, it will look heavy indeed. So it's Ok to expect heavy execution complexity. Thanks.
Hi, Alexander! The approach is fine. Two comments below:
The remaining heavy piece of the code is:
Item* propagate_equal_fields(THD *thd, const Context &ctx, COND_EQUAL *cond) { Context cmpctx(ANY_SUBST, cmp.compare_type(), cmp.compare_collation()); args[0]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[0]); args[1]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[1]); args[2]->propagate_equal_fields_and_change_item_tree(thd, Context_identity(), cond, &args[2]); return this; }
We cannot use the same approach here, because args[0] and args[2] are propagated with a different context (ANY_SUBST vs IDENTITY_SUBST).
An idea: Item *old= args[0]; args[0]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[0]); if (args[0] != old) args[2]->propagate_equal_fields_and_change_item_tree(thd, Context_identity(), cond, &args[2]); First substitution uses more relaxed rules, so, supposedly, if it did not substitute anything, than a stricter IDENTITY_SUBST ssubstitution won't substitute anything either.
@@ -2513,7 +2530,14 @@ void Item_func_nullif::update_used_tables() } else { - Item_func::update_used_tables(); + /* + No needs to iterate through args[2] when it's just a copy of args[0]. + See MDEV-9712 Performance degradation of nested NULLIF + */ + DBUG_ASSERT(arg_count == 3); + used_tables_and_const_cache_init(); + used_tables_and_const_cache_update_and_join(args[0] == args[2] ? 2 : 3, + args);
here, you can unconditionally run used_tables_and_const_cache_update_and_join(2, args); because even if args[2] differs from args[0], it cannot use more tables, so for the purpose of this method, it's redundant.
} }
Regards, Sergei Chief Architect MariaDB and security@mariadb.org
Hi Sergei, Thanks for the review! On 04/27/2016 06:24 PM, Sergei Golubchik wrote:
Hi, Alexander!
The approach is fine. Two comments below:
The remaining heavy piece of the code is:
Item* propagate_equal_fields(THD *thd, const Context &ctx, COND_EQUAL *cond) { Context cmpctx(ANY_SUBST, cmp.compare_type(), cmp.compare_collation()); args[0]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[0]); args[1]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[1]); args[2]->propagate_equal_fields_and_change_item_tree(thd, Context_identity(), cond, &args[2]); return this; }
We cannot use the same approach here, because args[0] and args[2] are propagated with a different context (ANY_SUBST vs IDENTITY_SUBST).
An idea:
Item *old= args[0]; args[0]->propagate_equal_fields_and_change_item_tree(thd, cmpctx, cond, &args[0]); if (args[0] != old) args[2]->propagate_equal_fields_and_change_item_tree(thd, Context_identity(), cond, &args[2]);
First substitution uses more relaxed rules, so, supposedly, if it did not substitute anything, than a stricter IDENTITY_SUBST ssubstitution won't substitute anything either.
Looks like a very good solution. This reduced execution time for the reported query back to 0.0 seconds again :) Brilliant!
@@ -2513,7 +2530,14 @@ void Item_func_nullif::update_used_tables() } else { - Item_func::update_used_tables(); + /* + No needs to iterate through args[2] when it's just a copy of args[0]. + See MDEV-9712 Performance degradation of nested NULLIF + */ + DBUG_ASSERT(arg_count == 3); + used_tables_and_const_cache_init(); + used_tables_and_const_cache_update_and_join(args[0] == args[2] ? 2 : 3, + args);
here, you can unconditionally run
used_tables_and_const_cache_update_and_join(2, args);
because even if args[2] differs from args[0], it cannot use more tables, so for the purpose of this method, it's redundant.
I'm not sure. After equal const propagation, update_used_tables() is called again 2 times in this script: DROP TABLE IF EXISTS t1; CREATE TABLE t1 (a BINARY(1)); INSERT INTO t1 VALUES ('a'),('b'); SELECT * FROM t1 WHERE NULLIF(a,'a') IS NULL AND a='a'; <offtopic> Btw, update_used_tables() is called: - 3 times before propagate_equal_fields() - 2 times after propagate_equal_fields() Perhaps we should generally try to reduce the amount of update_used_tables(). </offtopic> When update_used_tables() is called after propagate_equal_fields(), args[0] can already be a constant, while args[2] can still point to the original expression involving tables. So args[2] can have more tables, it seems. Can you clarify please?
} }
Regards, Sergei Chief Architect MariaDB and security@mariadb.org
Hi, Alexander! On May 04, Alexander Barkov wrote:
@@ -2513,7 +2530,14 @@ void Item_func_nullif::update_used_tables() } else { - Item_func::update_used_tables(); + /* + No needs to iterate through args[2] when it's just a copy of args[0]. + See MDEV-9712 Performance degradation of nested NULLIF + */ + DBUG_ASSERT(arg_count == 3); + used_tables_and_const_cache_init(); + used_tables_and_const_cache_update_and_join(args[0] == args[2] ? 2 : 3, + args);
here, you can unconditionally run
used_tables_and_const_cache_update_and_join(2, args);
because even if args[2] differs from args[0], it cannot use more tables, so for the purpose of this method, it's redundant.
I'm not sure.
After equal const propagation, update_used_tables() is called again 2 times in this script:
DROP TABLE IF EXISTS t1; CREATE TABLE t1 (a BINARY(1)); INSERT INTO t1 VALUES ('a'),('b'); SELECT * FROM t1 WHERE NULLIF(a,'a') IS NULL AND a='a';
<offtopic> Btw, update_used_tables() is called: - 3 times before propagate_equal_fields() - 2 times after propagate_equal_fields() Perhaps we should generally try to reduce the amount of update_used_tables(). </offtopic>
Perhaps. We're in general walking the tree too much, I think.
When update_used_tables() is called after propagate_equal_fields(), args[0] can already be a constant, while args[2] can still point to the original expression involving tables.
So args[2] can have more tables, it seems.
Can you clarify please?
Then I was wrong :) I thought it'll be just a cast or charset convertion on top of args[0] (or the other way around), and forgot about constant substitution. Regards, Sergei Chief Architect MariaDB and security@mariadb.org
participants (2)
-
Alexander Barkov -
Sergei Golubchik