From: Roy Lyseng Date: April 14 2011 11:56am Subject: bzr commit into mysql-trunk branch (roy.lyseng:3363) Bug#11822517 List-Archive: http://lists.mysql.com/commits/135435 X-Bug: 11822517 Message-Id: <20110414115646.DF96E1F4@tyr67.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============7606504617746422640==" --===============7606504617746422640== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #At file:///home/rl136806/mysql/repo/mysql-work5/ based on revid:roy.lyseng@stripped 3363 Roy Lyseng 2011-04-14 Bug#11822517: Refactor call interface of choose_plan() Part 2 - Change meaning of greedy_search() argument 'remaining_tables'. The purpose of this patch is to make the interface of greedy_search() and related functions simpler. It is also a preparatory step for a simpler test for dependencies when doing semi-join materialization together with outer join (WL#5561). The meaning of the argument remaining_tables to greedy_search() is changed: Before this patch, it meant all tables not yet added to the current join plan, regardless of whether the tables were to be optimized or not. After the patch, it means all tables remaining to be added, but not including tables that will not be optimized. The difference is important when making a plan for a materialized semi-join nest. Before, remaining_tables included also the tables belonging to the query, but not part of the semi-join nest being optimized. This makes for simpler implementation of best_extension_by_limited_search() and easier maintenance. However, best_access_path() requires that information about all tables not yet added to the plan be available. We implement this by adding a member variable excluded_tables in the Optimize_table_order class, which contains the set of all tables in the query block that are not to be optimized in the current operation. Notice that excluded_tables is passed to best_access_path() only where it can be non-empty. sql/sql_select.cc New member variable excluded_tables is added to Optimize_table_order. In choose_table_order(), join_tables is calculated as the set of tables to be optimized. In best_extension_by_limited_search(), use of allowed_tables is eliminated, and logic has been slightly simplified. modified: sql/sql_select.cc === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2011-04-14 10:56:57 +0000 +++ b/sql/sql_select.cc 2011-04-14 11:54:52 +0000 @@ -284,7 +284,10 @@ public: join->tables - join->const_tables)), prune_level(thd->variables.optimizer_prune_level), thd(thd), join(join), - cur_embedding_map(0) + cur_embedding_map(0), + excluded_tables(sjm_nest ? + join->all_table_map & ~sjm_nest->sj_inner_tables : + 0) { this->join->emb_sjm_nest= sjm_nest; } @@ -312,6 +315,15 @@ private: */ nested_join_map cur_embedding_map; /** + When calculating a plan for a materialized semi-join nest, + best_access_plan() needs to know not only the remaining tables within the + semi-join nest, but also all tables outside of this nest, because there may + be key references between the semi-join nest and the outside tables + that should not be considered when materializing the semi-join nest. + @c excluded_tables tracks these tables. + */ + const table_map excluded_tables; + /** @todo: Add remaining Join optimization state members here, ie emb_sjm_nest, positions, cur_sj_inner_tables. This is not yet possible because (some of them) are accessed through @@ -7017,6 +7029,12 @@ public: semijoin nest and those outside of it. The way to control this is to add the set of outside tables to the @c remaining_tables argument. + @todo: Add this function to class Optimize_table_order. When this is done, + best_access_path() will have access to the excluded_tables member, and + there will no longer be a need to pass that set of tables as part of + remaining_tables. Notice also that excluded_tables can be non-empty only + at those places where it is actually passed as argument. + @param join pointer to the structure providing all context info for the query @param s the table to be joined by the function @@ -7032,9 +7050,6 @@ public: @param[out] pos Table access plan @param[out] loose_scan_pos Table plan that uses loosescan, or set cost to DBL_MAX if not possible. - - @return - None */ static void @@ -7653,7 +7668,7 @@ bool Optimize_table_order::choose_table_ tables from this semi-join as first */ jtab_sort_func= join_tab_cmp_embedded_first; - join_tables= join->all_table_map & ~join->const_table_map; + join_tables= join->emb_sjm_nest->sj_inner_tables; } else { @@ -7888,7 +7903,8 @@ void Optimize_table_order::optimize_stra DBUG_ASSERT(!check_interleaving_with_nj(s)); /* Find the best access method from 's' to the current partial plan */ POSITION loose_scan_pos; - best_access_path(join, s, join_tables, idx, FALSE, record_count, + best_access_path(join, s, excluded_tables | join_tables, + idx, FALSE, record_count, join->positions + idx, &loose_scan_pos); /* compute the cost of the new plan extended with 's' */ @@ -8079,10 +8095,7 @@ bool Optimize_table_order::greedy_search DBUG_ENTER("Optimize_table_order::greedy_search"); /* Number of tables that we are optimizing */ - const uint n_tables= my_count_bits(remaining_tables & - (join->emb_sjm_nest? - join->emb_sjm_nest->sj_inner_tables : - ~(table_map)0)); + const uint n_tables= my_count_bits(remaining_tables); /* Number of tables remaining to be optimized */ uint size_remain= n_tables; @@ -8334,10 +8347,6 @@ bool Optimize_table_order::best_extensio DBUG_EXECUTE("opt", print_plan(join, idx, record_count, read_time, read_time, "part_plan");); - - table_map allowed_tables= ~(table_map)0; - if (join->emb_sjm_nest) - allowed_tables= join->emb_sjm_nest->sj_inner_tables; /* No need to call advance_sj_state() when 1) there are no semijoin nests or @@ -8364,7 +8373,6 @@ bool Optimize_table_order::best_extensio swap_variables(JOIN_TAB*, join->best_ref[idx], *pos); if ((remaining_tables & real_table_bit) && - (allowed_tables & real_table_bit) && !(remaining_tables & s->dependent) && (!idx || !check_interleaving_with_nj(s))) { @@ -8373,7 +8381,7 @@ bool Optimize_table_order::best_extensio /* Find the best access method from 's' to the current partial plan */ POSITION loose_scan_pos; - best_access_path(join, s, remaining_tables, + best_access_path(join, s, excluded_tables | remaining_tables, idx, false, record_count, position, &loose_scan_pos); @@ -8445,8 +8453,7 @@ bool Optimize_table_order::best_extensio } } - if ((current_search_depth > 1) && - (remaining_tables & ~real_table_bit) & allowed_tables ) + if ((current_search_depth > 1) && (remaining_tables & ~real_table_bit)) { /* Explore more best extensions of plan */ if (best_extension_by_limited_search(remaining_tables & ~real_table_bit, --===============7606504617746422640== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/roy.lyseng@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: roy.lyseng@stripped # target_branch: file:///home/rl136806/mysql/repo/mysql-work5/ # testament_sha1: a73340eb23ce7edd5a4551e4a647d6ec59f0fee8 # timestamp: 2011-04-14 13:56:46 +0200 # base_revision_id: roy.lyseng@stripped\ # 7cpa16h9ahahbcn1 # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWYKd8rgAAxR/gFAQYABZ9/// +2XcgL////VgCSMwTb60VTt7x3W2zdtFbY0Ar2N1QkkTEaCMJPVT8TIaU/U2p6mp6mQ0eptQbUNB 6QGgmgAiaCaTRoZA0BoAADQNANNCak9T0FJp5J+qe1T8qek02po9NNQNANGgaABKepCBTKeo9TbS Q9IDQaAAyAAAAc0yMhkwQ0YTBGmjRiBpkyMAAQSJCaCaT0TExNR6ENE8FGjR6nqAAaG1EAWgLGV/ U/RTuvg50Pj9yz31jej5bW2ePyccOMJ3dl542x651/A+DyueWGi2DB5QnOhHFgnNwv2qo5DbYx6H U8v5fKx8nXU30Qx3gCehKX8YRwws9VXS3HZkzMCl8RToq7NWkxEu4NWZIPFULZvBiFc5rzNgxSDI 1T0X9dnDhhtwcZFxx8lMzp2CVYhr3qFYXOveNUmLS12ZFwrykTa1JUiYQklFFWDNRxIFgkDo6LSk MkCnCjSDi4qDjWgRo/a6TuL06KXhAzMTZlUzPI1yMYEedP66tDeccx0A3lUL0tR3K14k8yxIQOqz c+qCBwLahmgbRZm4Ceb1lZX4koeZi4qaFmx0V6xz23qGGIiRlEXrStjZ4z1mBO7kOdhsXOpVE1Q3 Xirjsj5xDPjR1pymId5tDQqKCXZpXTDBoo0+DPFUlBHKNfkvx77eHBFKDh6p6EoRowAJS44v6CwM BrO3ytsKJokoaN22dTtU7Nvndti5nbYGgp8sJsPr2H9iOHsCJacxx3iZ/UitjLsCb11ZJl6Yv0OD 0WqxbfeADiIRIhu1iSu699NIJsR0tb/hwlYZ+QsIEOWHjdMmTgRB6YBmD75RiHRJxXHN1Qwq0LAu 3KxqEsg8ffkMGJghEDGg38cREBfhR3xhCWqem/IPIkIcx3Tw1Xik+QV8K8vbT13y5xqYqRFscZbj QT0oLkW/huCE9MdRnYEpgw9Napolo5qWmgEA96oKv2vHEpiomdxSe1dQqDQQB6AnUvDSzpTka8KA ASBCw1vqCNg5cFHJkPQahr6R0tbS2q2DQrFsDTOIo7pS6L3g4IjjEf2CxKzfX9JeLdJ1dVEU3m9A 7VgKwGzcrQR++WzBQG7WBqkINryTLJF5oT2G3wr9zO+sTKOhvWWuK5PvitwZbiGQsimc8zVSHJyH PazAsjG2obD8oh4hsVjqElLbHeI71DQCUGwBd8LX4JSthFSWjpYNnoHspGmZBGEQIRPh7x9ItUeO mrZ2kW/ozY85RfZrRAvyNsyUI3ltZ7JK5B/PWyT2j73p/taxshVNiY8+HhAg0fQYIjGOpODWhmMb ZI4dkE45LwrjoklNDLCpLSlDSc1g492lP3hHadt14uk8+8y0gkY2j+Qu8pjeClQXLsmHWGQee5Bi wriZ0O9H5P6mG23KwaJY0W14mAW5ls0zFurJDWR/siVzLMZtl1BUcSUzGQSQ5OnFaLpzjz4TJKah huF24dA36RSsCwDkKIxFd7IyP9GoedZsSSHN3OB5lAS+XU9SNGTGm47ftLEZeIVJIpkwVeMtYiPl igIkrZ0aOl1cFED/AIDzAVog2WBn2H2B2EgtLzpN9p3UsBtOkQ3ugDqYcOznx051LnJOpis3IWG4 7fDJEJEem8GETyzsCqnkQppPOKseCNoS3PIqmwZSOllBTUCd6vQSPM7BsJC5XBQhiJMifjFi1ud6 Fv5vRm7IPZj3dvLt9rjMXgxZVbNOVwTFt6tdLQtxrics1OeMFbIobXnmTX6tLC0MNuZWuFDapVev Z86fAb7yukt3NZ7nEtQa5PQQ47VsJKNBuDIduJt4rwipXFRUevExRuHozvV3TOWoaRbFGcLNRjat zs4liOR2esvS4vnYjQ0ZTgSjCHpYXKbJXgP9haqcYX2B6awO9rFrL7e5YMkcDhtI68SXWb1Fq3v4 9eVd0IqM7pdsSOoU0LjnFCQVT7UM04uOS5ZLs5ugbBpsa5jsCDoDMH9yuqk5hCPNjabEcvHvY5ED TGE2qjumdW4RPekxqvSg87X5a+tVp3+Zvuq9/JcjmdFKxUiCYDMmD4NgaIUJao184OMdk7tRbSOx 80oSyQbB9DwPfxcOrSGtYHC8NbCsWScwQ7u+ZkzUzypEosmHIjtSquPOhc+lb8a2hyNQPfHiXIPN bw0g9wSCsqXJVNdXvKkairsSIhsVgVRCEFYvnmLkVbGjSy93Ylc0weYFvjbB8Ej0pHkrUFwZ1qIB jkjCEsSTfDIhJrWwOnD3XVKJX2l9ZqX3R/Ksk1UirKCSUigTBrBCYvLS2bcGYkiAlSg8jPJDGUCj ENIYFhYcIJIJJlBGt+rq5K1q7jwIIJzhRjA2Tc002txC5hanIYGTIYPXz7p45CUS2gFNYLALxpS9 dhap2B6i+bYa86zOT8kiQV2hM9bDiUB36jJA/oJXHRmVmXy8dCRvNz27lgF9OiGmBqRYTyPVkWBY OxLTm4Snff5rBFCmnOlfIrYm22nyOElezgLZNJa52JSQ4TiB/9bLoUI9zPjEEzSWjaxnx5eMipYh o14o5fv0TwvD9z+Bx4bAzLDM2xsdTBtk5jaqyKKJCK1aUiatWtO3Q4LrqAcjCNBB6BhIU3GGBEQa BTGFQ7nq8gWiRcyB60GWagYJQbe0b+JYlpGI5QODgO+MnOcMbDMzKEQwEAx50G/VbdLZeZ2aWuJ2 UJZ76XXGGEOFVvMJmZmhfSsCNHgC0kVRPebDSgioosDAiMQsFK4zdFzGJShbe7mdi8Mo2cOVUTRz tCMhqbS8aaFycpcBNaWP2eArjcwXc6ZBfSxQ11mQ9PlptHkMenIFyP0sdMyz9SYcX0WspaKe1NW6 CdDeKJLT4DDSO002wxbPIhHHXVJaRVis1T05ltFLPYYfBIdpFzkVruLjzmkRs2CVuRxLQ/8XckU4 UJCCnfK4 --===============7606504617746422640==--