- developers - lists.mariadb.org

[Maria-developers] Updated (by Monty): Table elimination (17)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Monty - Thu, 23 Jul 2009, 09:19)=-=- Version updated. --- /tmp/wklog.17.old.24090 2009-07-23 09:19:32.000000000 +0300 +++ /tmp/wklog.17.new.24090 2009-07-23 09:19:32.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-5.1 -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from ------------------------------------------------------------ -=-=(View All Progress Notes, 24 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Monty): Table elimination (17)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Monty - Thu, 23 Jul 2009, 09:19)=-=- Version updated. --- /tmp/wklog.17.old.24090 2009-07-23 09:19:32.000000000 +0300 +++ /tmp/wklog.17.new.24090 2009-07-23 09:19:32.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-5.1 -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from ------------------------------------------------------------ -=-=(View All Progress Notes, 24 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Bug tracker for MariaDB
by Bryan Alsdorf 22 Jul '09

22 Jul '09

Hi, I am in the process of setting up Eventum as the bug tracker at Monty Program AB to track bugs in MariaDB. I would like input on the values we need for the following fields: * Status * Category * Operating Systems Also please suggest any additional fields you think should be in this system. The current fields I have are: * Summary * Severity * Category * Status * Operating System * Description * How to Repeat * Suggested Fix * Product * Product Version * BZR Tree (URL to relevant tree with bug fix or that illustrates the problem) Some of these fields (and my current values for them) are inspired by bugs.mysql.com. However, since we are setting up a brand new system we should try make it fit our needs instead of doing what others are doing. Any suggestions or comments are appreciated, once I finish the initial setup I will get a test site up for everyone to look over. Best Regards, -- Bryan Alsdorf, Lead Web Developer Monty Program, AB. http://askmonty.org

8 15

[Maria-developers] Updated (by Psergey): Add support for google protocol buffers (34)
by worklog-noreply＠askmonty.org 21 Jul '09

21 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add support for google protocol buffers CREATION DATE..: Tue, 21 Jul 2009, 21:11 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 34 (http://askmonty.org/worklog/?tid=34) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Tue, 21 Jul 2009, 21:13)=-=- Low Level Design modified. --- /tmp/wklog.34.old.6462 2009-07-21 21:13:13.000000000 +0300 +++ /tmp/wklog.34.new.6462 2009-07-21 21:13:13.000000000 +0300 @@ -1 +1,4 @@ +* GPB tarball contains a protocol definition for .proto file structure itself + and a parser for text form of .proto file which then exposes the parsed + file via standard GPB message navigation API. -=-=(Psergey - Tue, 21 Jul 2009, 21:12)=-=- High-Level Specification modified. --- /tmp/wklog.34.old.6399 2009-07-21 21:12:23.000000000 +0300 +++ /tmp/wklog.34.new.6399 2009-07-21 21:12:23.000000000 +0300 @@ -1 +1,78 @@ +<contents> +1. GPB Encoding overview +2. GPB in an SQL database +2.1 Informing server about GPB field names and types +2.2 Addressing GPB fields +2.2.1 Option1: SQL Function +2.2.2 Option2: SQL columns +</contents> + + +1. GPB Encoding overview +======================== + +GBB is a compact encoding for structured and typed data. A unit of GPB data +(it is called message) is only partially self-describing: it's possible to +iterate over its parts, but, quoting the spec + +http://code.google.com/apis/protocolbuffers/docs/encoding.html: + " the name and declared type for each field can only be determined on the + decoding end by referencing the message type's definition (i.e. the .proto + file). " + +2. GPB in an SQL database +========================= + +It is possible to store GPB data in MariaDB today - one can declare a binary +blob column and use it to store GPB messages. Storing and retrieving entire +messages will be the only available operations, though, as the server has no +idea about the GPB format. +It is apparent that ability to peek inside GPB data from SQL layer would be of +great advantage: one would be able to +- select only certain fields or parts of GPB messages +- filter records based on the values of GPB fields +- etc +performing such operations at SQL layer will allow to reduce client<->server +traffic right away, and will open path to getting the best possible +performance. + +2.1 Informing server about GPB field names and types +---------------------------------------------------- +User-friendly/meaningful access to GPB fields requires knowledge of GPB field +names and types, which are not available from GPB message itself (see "GPB +encoding overview" section). + +So the first issue to be addressed is to get the server to know the definition +of stored messages. We intend to assume that all records have GPB messages +that conform to a certain single definition, which gives one definition per +GPB field. + +DecisionToMake: How to pass the server the GPB definition? +First idea: add a CREATE TABLE parameter which will specify either the +definition itself or path to .proto file with the definition. + +2.2 Addressing GPB fields +------------------------- +We'll need to provide a way to access GPB fields. This can be complicated as +structures that are encoded in GPB message can be nested and recursive. + +2.2.1 Option1: SQL Function +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Introduce an SQL function GPB_FIELD(path) which will return contents of the +field. +- Return type of the function will be determined from GPB message definition. +- For path, we can use XPath selector (a subset of XPath) syntax. + +(TODO ^ the above needs to be specified in more detail. is the selector as +simple as filesystem path or we allow quantifiers (with predicates?)?) + +2.2.2 Option2: SQL columns +~~~~~~~~~~~~~~~~~~~~~~~~~~ +Make GPB columns to be accessible as SQL columns. +This approach has problems: +- It might be hard to implement code-wise + - (TODO will Virtual columns patch help??) +- It is not clear how to access fields from nested structures. Should we allow + quoted names like `foo/bar[2]/baz' ? + DESCRIPTION: Add support for Google Protocol Buffers (further GPB). It should be possible to have columns that store GPB-encoded data, as well as use SQL constructs to extract parts of GPB data for use in select list, for filtering, and so forth. Any support for indexing GPB data is outside of scope of this WL entry. HIGH-LEVEL SPECIFICATION: <contents> 1. GPB Encoding overview 2. GPB in an SQL database 2.1 Informing server about GPB field names and types 2.2 Addressing GPB fields 2.2.1 Option1: SQL Function 2.2.2 Option2: SQL columns </contents> 1. GPB Encoding overview ======================== GBB is a compact encoding for structured and typed data. A unit of GPB data (it is called message) is only partially self-describing: it's possible to iterate over its parts, but, quoting the spec http://code.google.com/apis/protocolbuffers/docs/encoding.html: " the name and declared type for each field can only be determined on the decoding end by referencing the message type's definition (i.e. the .proto file). " 2. GPB in an SQL database ========================= It is possible to store GPB data in MariaDB today - one can declare a binary blob column and use it to store GPB messages. Storing and retrieving entire messages will be the only available operations, though, as the server has no idea about the GPB format. It is apparent that ability to peek inside GPB data from SQL layer would be of great advantage: one would be able to - select only certain fields or parts of GPB messages - filter records based on the values of GPB fields - etc performing such operations at SQL layer will allow to reduce client<->server traffic right away, and will open path to getting the best possible performance. 2.1 Informing server about GPB field names and types ---------------------------------------------------- User-friendly/meaningful access to GPB fields requires knowledge of GPB field names and types, which are not available from GPB message itself (see "GPB encoding overview" section). So the first issue to be addressed is to get the server to know the definition of stored messages. We intend to assume that all records have GPB messages that conform to a certain single definition, which gives one definition per GPB field. DecisionToMake: How to pass the server the GPB definition? First idea: add a CREATE TABLE parameter which will specify either the definition itself or path to .proto file with the definition. 2.2 Addressing GPB fields ------------------------- We'll need to provide a way to access GPB fields. This can be complicated as structures that are encoded in GPB message can be nested and recursive. 2.2.1 Option1: SQL Function ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Introduce an SQL function GPB_FIELD(path) which will return contents of the field. - Return type of the function will be determined from GPB message definition. - For path, we can use XPath selector (a subset of XPath) syntax. (TODO ^ the above needs to be specified in more detail. is the selector as simple as filesystem path or we allow quantifiers (with predicates?)?) 2.2.2 Option2: SQL columns ~~~~~~~~~~~~~~~~~~~~~~~~~~ Make GPB columns to be accessible as SQL columns. This approach has problems: - It might be hard to implement code-wise - (TODO will Virtual columns patch help??) - It is not clear how to access fields from nested structures. Should we allow quoted names like `foo/bar[2]/baz' ? LOW-LEVEL DESIGN: * GPB tarball contains a protocol definition for .proto file structure itself and a parser for text form of .proto file which then exposes the parsed file via standard GPB message navigation API. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Add support for google protocol buffers (34)
by worklog-noreply＠askmonty.org 21 Jul '09

21 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add support for google protocol buffers CREATION DATE..: Tue, 21 Jul 2009, 21:11 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 34 (http://askmonty.org/worklog/?tid=34) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Tue, 21 Jul 2009, 21:13)=-=- Low Level Design modified. --- /tmp/wklog.34.old.6462 2009-07-21 21:13:13.000000000 +0300 +++ /tmp/wklog.34.new.6462 2009-07-21 21:13:13.000000000 +0300 @@ -1 +1,4 @@ +* GPB tarball contains a protocol definition for .proto file structure itself + and a parser for text form of .proto file which then exposes the parsed + file via standard GPB message navigation API. -=-=(Psergey - Tue, 21 Jul 2009, 21:12)=-=- High-Level Specification modified. --- /tmp/wklog.34.old.6399 2009-07-21 21:12:23.000000000 +0300 +++ /tmp/wklog.34.new.6399 2009-07-21 21:12:23.000000000 +0300 @@ -1 +1,78 @@ +<contents> +1. GPB Encoding overview +2. GPB in an SQL database +2.1 Informing server about GPB field names and types +2.2 Addressing GPB fields +2.2.1 Option1: SQL Function +2.2.2 Option2: SQL columns +</contents> + + +1. GPB Encoding overview +======================== + +GBB is a compact encoding for structured and typed data. A unit of GPB data +(it is called message) is only partially self-describing: it's possible to +iterate over its parts, but, quoting the spec + +http://code.google.com/apis/protocolbuffers/docs/encoding.html: + " the name and declared type for each field can only be determined on the + decoding end by referencing the message type's definition (i.e. the .proto + file). " + +2. GPB in an SQL database +========================= + +It is possible to store GPB data in MariaDB today - one can declare a binary +blob column and use it to store GPB messages. Storing and retrieving entire +messages will be the only available operations, though, as the server has no +idea about the GPB format. +It is apparent that ability to peek inside GPB data from SQL layer would be of +great advantage: one would be able to +- select only certain fields or parts of GPB messages +- filter records based on the values of GPB fields +- etc +performing such operations at SQL layer will allow to reduce client<->server +traffic right away, and will open path to getting the best possible +performance. + +2.1 Informing server about GPB field names and types +---------------------------------------------------- +User-friendly/meaningful access to GPB fields requires knowledge of GPB field +names and types, which are not available from GPB message itself (see "GPB +encoding overview" section). + +So the first issue to be addressed is to get the server to know the definition +of stored messages. We intend to assume that all records have GPB messages +that conform to a certain single definition, which gives one definition per +GPB field. + +DecisionToMake: How to pass the server the GPB definition? +First idea: add a CREATE TABLE parameter which will specify either the +definition itself or path to .proto file with the definition. + +2.2 Addressing GPB fields +------------------------- +We'll need to provide a way to access GPB fields. This can be complicated as +structures that are encoded in GPB message can be nested and recursive. + +2.2.1 Option1: SQL Function +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Introduce an SQL function GPB_FIELD(path) which will return contents of the +field. +- Return type of the function will be determined from GPB message definition. +- For path, we can use XPath selector (a subset of XPath) syntax. + +(TODO ^ the above needs to be specified in more detail. is the selector as +simple as filesystem path or we allow quantifiers (with predicates?)?) + +2.2.2 Option2: SQL columns +~~~~~~~~~~~~~~~~~~~~~~~~~~ +Make GPB columns to be accessible as SQL columns. +This approach has problems: +- It might be hard to implement code-wise + - (TODO will Virtual columns patch help??) +- It is not clear how to access fields from nested structures. Should we allow + quoted names like `foo/bar[2]/baz' ? + DESCRIPTION: Add support for Google Protocol Buffers (further GPB). It should be possible to have columns that store GPB-encoded data, as well as use SQL constructs to extract parts of GPB data for use in select list, for filtering, and so forth. Any support for indexing GPB data is outside of scope of this WL entry. HIGH-LEVEL SPECIFICATION: <contents> 1. GPB Encoding overview 2. GPB in an SQL database 2.1 Informing server about GPB field names and types 2.2 Addressing GPB fields 2.2.1 Option1: SQL Function 2.2.2 Option2: SQL columns </contents> 1. GPB Encoding overview ======================== GBB is a compact encoding for structured and typed data. A unit of GPB data (it is called message) is only partially self-describing: it's possible to iterate over its parts, but, quoting the spec http://code.google.com/apis/protocolbuffers/docs/encoding.html: " the name and declared type for each field can only be determined on the decoding end by referencing the message type's definition (i.e. the .proto file). " 2. GPB in an SQL database ========================= It is possible to store GPB data in MariaDB today - one can declare a binary blob column and use it to store GPB messages. Storing and retrieving entire messages will be the only available operations, though, as the server has no idea about the GPB format. It is apparent that ability to peek inside GPB data from SQL layer would be of great advantage: one would be able to - select only certain fields or parts of GPB messages - filter records based on the values of GPB fields - etc performing such operations at SQL layer will allow to reduce client<->server traffic right away, and will open path to getting the best possible performance. 2.1 Informing server about GPB field names and types ---------------------------------------------------- User-friendly/meaningful access to GPB fields requires knowledge of GPB field names and types, which are not available from GPB message itself (see "GPB encoding overview" section). So the first issue to be addressed is to get the server to know the definition of stored messages. We intend to assume that all records have GPB messages that conform to a certain single definition, which gives one definition per GPB field. DecisionToMake: How to pass the server the GPB definition? First idea: add a CREATE TABLE parameter which will specify either the definition itself or path to .proto file with the definition. 2.2 Addressing GPB fields ------------------------- We'll need to provide a way to access GPB fields. This can be complicated as structures that are encoded in GPB message can be nested and recursive. 2.2.1 Option1: SQL Function ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Introduce an SQL function GPB_FIELD(path) which will return contents of the field. - Return type of the function will be determined from GPB message definition. - For path, we can use XPath selector (a subset of XPath) syntax. (TODO ^ the above needs to be specified in more detail. is the selector as simple as filesystem path or we allow quantifiers (with predicates?)?) 2.2.2 Option2: SQL columns ~~~~~~~~~~~~~~~~~~~~~~~~~~ Make GPB columns to be accessible as SQL columns. This approach has problems: - It might be hard to implement code-wise - (TODO will Virtual columns patch help??) - It is not clear how to access fields from nested structures. Should we allow quoted names like `foo/bar[2]/baz' ? LOW-LEVEL DESIGN: * GPB tarball contains a protocol definition for .proto file structure itself and a parser for text form of .proto file which then exposes the parsed file via standard GPB message navigation API. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Add support for google protocol buffers (34)
by worklog-noreply＠askmonty.org 21 Jul '09

21 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add support for google protocol buffers CREATION DATE..: Tue, 21 Jul 2009, 21:11 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 34 (http://askmonty.org/worklog/?tid=34) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Tue, 21 Jul 2009, 21:12)=-=- High-Level Specification modified. --- /tmp/wklog.34.old.6399 2009-07-21 21:12:23.000000000 +0300 +++ /tmp/wklog.34.new.6399 2009-07-21 21:12:23.000000000 +0300 @@ -1 +1,78 @@ +<contents> +1. GPB Encoding overview +2. GPB in an SQL database +2.1 Informing server about GPB field names and types +2.2 Addressing GPB fields +2.2.1 Option1: SQL Function +2.2.2 Option2: SQL columns +</contents> + + +1. GPB Encoding overview +======================== + +GBB is a compact encoding for structured and typed data. A unit of GPB data +(it is called message) is only partially self-describing: it's possible to +iterate over its parts, but, quoting the spec + +http://code.google.com/apis/protocolbuffers/docs/encoding.html: + " the name and declared type for each field can only be determined on the + decoding end by referencing the message type's definition (i.e. the .proto + file). " + +2. GPB in an SQL database +========================= + +It is possible to store GPB data in MariaDB today - one can declare a binary +blob column and use it to store GPB messages. Storing and retrieving entire +messages will be the only available operations, though, as the server has no +idea about the GPB format. +It is apparent that ability to peek inside GPB data from SQL layer would be of +great advantage: one would be able to +- select only certain fields or parts of GPB messages +- filter records based on the values of GPB fields +- etc +performing such operations at SQL layer will allow to reduce client<->server +traffic right away, and will open path to getting the best possible +performance. + +2.1 Informing server about GPB field names and types +---------------------------------------------------- +User-friendly/meaningful access to GPB fields requires knowledge of GPB field +names and types, which are not available from GPB message itself (see "GPB +encoding overview" section). + +So the first issue to be addressed is to get the server to know the definition +of stored messages. We intend to assume that all records have GPB messages +that conform to a certain single definition, which gives one definition per +GPB field. + +DecisionToMake: How to pass the server the GPB definition? +First idea: add a CREATE TABLE parameter which will specify either the +definition itself or path to .proto file with the definition. + +2.2 Addressing GPB fields +------------------------- +We'll need to provide a way to access GPB fields. This can be complicated as +structures that are encoded in GPB message can be nested and recursive. + +2.2.1 Option1: SQL Function +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Introduce an SQL function GPB_FIELD(path) which will return contents of the +field. +- Return type of the function will be determined from GPB message definition. +- For path, we can use XPath selector (a subset of XPath) syntax. + +(TODO ^ the above needs to be specified in more detail. is the selector as +simple as filesystem path or we allow quantifiers (with predicates?)?) + +2.2.2 Option2: SQL columns +~~~~~~~~~~~~~~~~~~~~~~~~~~ +Make GPB columns to be accessible as SQL columns. +This approach has problems: +- It might be hard to implement code-wise + - (TODO will Virtual columns patch help??) +- It is not clear how to access fields from nested structures. Should we allow + quoted names like `foo/bar[2]/baz' ? + DESCRIPTION: Add support for Google Protocol Buffers (further GPB). It should be possible to have columns that store GPB-encoded data, as well as use SQL constructs to extract parts of GPB data for use in select list, for filtering, and so forth. Any support for indexing GPB data is outside of scope of this WL entry. HIGH-LEVEL SPECIFICATION: <contents> 1. GPB Encoding overview 2. GPB in an SQL database 2.1 Informing server about GPB field names and types 2.2 Addressing GPB fields 2.2.1 Option1: SQL Function 2.2.2 Option2: SQL columns </contents> 1. GPB Encoding overview ======================== GBB is a compact encoding for structured and typed data. A unit of GPB data (it is called message) is only partially self-describing: it's possible to iterate over its parts, but, quoting the spec http://code.google.com/apis/protocolbuffers/docs/encoding.html: " the name and declared type for each field can only be determined on the decoding end by referencing the message type's definition (i.e. the .proto file). " 2. GPB in an SQL database ========================= It is possible to store GPB data in MariaDB today - one can declare a binary blob column and use it to store GPB messages. Storing and retrieving entire messages will be the only available operations, though, as the server has no idea about the GPB format. It is apparent that ability to peek inside GPB data from SQL layer would be of great advantage: one would be able to - select only certain fields or parts of GPB messages - filter records based on the values of GPB fields - etc performing such operations at SQL layer will allow to reduce client<->server traffic right away, and will open path to getting the best possible performance. 2.1 Informing server about GPB field names and types ---------------------------------------------------- User-friendly/meaningful access to GPB fields requires knowledge of GPB field names and types, which are not available from GPB message itself (see "GPB encoding overview" section). So the first issue to be addressed is to get the server to know the definition of stored messages. We intend to assume that all records have GPB messages that conform to a certain single definition, which gives one definition per GPB field. DecisionToMake: How to pass the server the GPB definition? First idea: add a CREATE TABLE parameter which will specify either the definition itself or path to .proto file with the definition. 2.2 Addressing GPB fields ------------------------- We'll need to provide a way to access GPB fields. This can be complicated as structures that are encoded in GPB message can be nested and recursive. 2.2.1 Option1: SQL Function ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Introduce an SQL function GPB_FIELD(path) which will return contents of the field. - Return type of the function will be determined from GPB message definition. - For path, we can use XPath selector (a subset of XPath) syntax. (TODO ^ the above needs to be specified in more detail. is the selector as simple as filesystem path or we allow quantifiers (with predicates?)?) 2.2.2 Option2: SQL columns ~~~~~~~~~~~~~~~~~~~~~~~~~~ Make GPB columns to be accessible as SQL columns. This approach has problems: - It might be hard to implement code-wise - (TODO will Virtual columns patch help??) - It is not clear how to access fields from nested structures. Should we allow quoted names like `foo/bar[2]/baz' ? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Add support for google protocol buffers (34)
by worklog-noreply＠askmonty.org 21 Jul '09

21 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add support for google protocol buffers CREATION DATE..: Tue, 21 Jul 2009, 21:11 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 34 (http://askmonty.org/worklog/?tid=34) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Tue, 21 Jul 2009, 21:12)=-=- High-Level Specification modified. --- /tmp/wklog.34.old.6399 2009-07-21 21:12:23.000000000 +0300 +++ /tmp/wklog.34.new.6399 2009-07-21 21:12:23.000000000 +0300 @@ -1 +1,78 @@ +<contents> +1. GPB Encoding overview +2. GPB in an SQL database +2.1 Informing server about GPB field names and types +2.2 Addressing GPB fields +2.2.1 Option1: SQL Function +2.2.2 Option2: SQL columns +</contents> + + +1. GPB Encoding overview +======================== + +GBB is a compact encoding for structured and typed data. A unit of GPB data +(it is called message) is only partially self-describing: it's possible to +iterate over its parts, but, quoting the spec + +http://code.google.com/apis/protocolbuffers/docs/encoding.html: + " the name and declared type for each field can only be determined on the + decoding end by referencing the message type's definition (i.e. the .proto + file). " + +2. GPB in an SQL database +========================= + +It is possible to store GPB data in MariaDB today - one can declare a binary +blob column and use it to store GPB messages. Storing and retrieving entire +messages will be the only available operations, though, as the server has no +idea about the GPB format. +It is apparent that ability to peek inside GPB data from SQL layer would be of +great advantage: one would be able to +- select only certain fields or parts of GPB messages +- filter records based on the values of GPB fields +- etc +performing such operations at SQL layer will allow to reduce client<->server +traffic right away, and will open path to getting the best possible +performance. + +2.1 Informing server about GPB field names and types +---------------------------------------------------- +User-friendly/meaningful access to GPB fields requires knowledge of GPB field +names and types, which are not available from GPB message itself (see "GPB +encoding overview" section). + +So the first issue to be addressed is to get the server to know the definition +of stored messages. We intend to assume that all records have GPB messages +that conform to a certain single definition, which gives one definition per +GPB field. + +DecisionToMake: How to pass the server the GPB definition? +First idea: add a CREATE TABLE parameter which will specify either the +definition itself or path to .proto file with the definition. + +2.2 Addressing GPB fields +------------------------- +We'll need to provide a way to access GPB fields. This can be complicated as +structures that are encoded in GPB message can be nested and recursive. + +2.2.1 Option1: SQL Function +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Introduce an SQL function GPB_FIELD(path) which will return contents of the +field. +- Return type of the function will be determined from GPB message definition. +- For path, we can use XPath selector (a subset of XPath) syntax. + +(TODO ^ the above needs to be specified in more detail. is the selector as +simple as filesystem path or we allow quantifiers (with predicates?)?) + +2.2.2 Option2: SQL columns +~~~~~~~~~~~~~~~~~~~~~~~~~~ +Make GPB columns to be accessible as SQL columns. +This approach has problems: +- It might be hard to implement code-wise + - (TODO will Virtual columns patch help??) +- It is not clear how to access fields from nested structures. Should we allow + quoted names like `foo/bar[2]/baz' ? + DESCRIPTION: Add support for Google Protocol Buffers (further GPB). It should be possible to have columns that store GPB-encoded data, as well as use SQL constructs to extract parts of GPB data for use in select list, for filtering, and so forth. Any support for indexing GPB data is outside of scope of this WL entry. HIGH-LEVEL SPECIFICATION: <contents> 1. GPB Encoding overview 2. GPB in an SQL database 2.1 Informing server about GPB field names and types 2.2 Addressing GPB fields 2.2.1 Option1: SQL Function 2.2.2 Option2: SQL columns </contents> 1. GPB Encoding overview ======================== GBB is a compact encoding for structured and typed data. A unit of GPB data (it is called message) is only partially self-describing: it's possible to iterate over its parts, but, quoting the spec http://code.google.com/apis/protocolbuffers/docs/encoding.html: " the name and declared type for each field can only be determined on the decoding end by referencing the message type's definition (i.e. the .proto file). " 2. GPB in an SQL database ========================= It is possible to store GPB data in MariaDB today - one can declare a binary blob column and use it to store GPB messages. Storing and retrieving entire messages will be the only available operations, though, as the server has no idea about the GPB format. It is apparent that ability to peek inside GPB data from SQL layer would be of great advantage: one would be able to - select only certain fields or parts of GPB messages - filter records based on the values of GPB fields - etc performing such operations at SQL layer will allow to reduce client<->server traffic right away, and will open path to getting the best possible performance. 2.1 Informing server about GPB field names and types ---------------------------------------------------- User-friendly/meaningful access to GPB fields requires knowledge of GPB field names and types, which are not available from GPB message itself (see "GPB encoding overview" section). So the first issue to be addressed is to get the server to know the definition of stored messages. We intend to assume that all records have GPB messages that conform to a certain single definition, which gives one definition per GPB field. DecisionToMake: How to pass the server the GPB definition? First idea: add a CREATE TABLE parameter which will specify either the definition itself or path to .proto file with the definition. 2.2 Addressing GPB fields ------------------------- We'll need to provide a way to access GPB fields. This can be complicated as structures that are encoded in GPB message can be nested and recursive. 2.2.1 Option1: SQL Function ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Introduce an SQL function GPB_FIELD(path) which will return contents of the field. - Return type of the function will be determined from GPB message definition. - For path, we can use XPath selector (a subset of XPath) syntax. (TODO ^ the above needs to be specified in more detail. is the selector as simple as filesystem path or we allow quantifiers (with predicates?)?) 2.2.2 Option2: SQL columns ~~~~~~~~~~~~~~~~~~~~~~~~~~ Make GPB columns to be accessible as SQL columns. This approach has problems: - It might be hard to implement code-wise - (TODO will Virtual columns patch help??) - It is not clear how to access fields from nested structures. Should we allow quoted names like `foo/bar[2]/baz' ? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Psergey): Add support for google protocol buffers (34)
by worklog-noreply＠askmonty.org 21 Jul '09

21 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add support for google protocol buffers CREATION DATE..: Tue, 21 Jul 2009, 21:11 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 34 (http://askmonty.org/worklog/?tid=34) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Add support for Google Protocol Buffers (further GPB). It should be possible to have columns that store GPB-encoded data, as well as use SQL constructs to extract parts of GPB data for use in select list, for filtering, and so forth. Any support for indexing GPB data is outside of scope of this WL entry. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Psergey): Add support for google protocol buffers (34)
by worklog-noreply＠askmonty.org 21 Jul '09

21 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add support for google protocol buffers CREATION DATE..: Tue, 21 Jul 2009, 21:11 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 34 (http://askmonty.org/worklog/?tid=34) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Add support for Google Protocol Buffers (further GPB). It should be possible to have columns that store GPB-encoded data, as well as use SQL constructs to extract parts of GPB data for use in select list, for filtering, and so forth. Any support for indexing GPB data is outside of scope of this WL entry. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Progress (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 20 Jul '09

20 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates ------------------------------------------------------------ -=-=(View All Progress Notes, 23 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Progress (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 20 Jul '09

20 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates ------------------------------------------------------------ -=-=(View All Progress Notes, 23 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] TYPE= disappears again in MySQL 5.4.4
by Arjen Lentz 17 Jul '09

17 Jul '09

Hi all, Just a heads up, please don't merge in this change from MySQL 5.4.4 See http://openquery.com/blog/type-disappears-mysql-544 for background, also http://bugs.mysql.com/bug.php?id=17501 Sergei Golubchik is still assigned to that bug, btw ;-) Cheers, Arjen. -- Arjen Lentz, Director @ Open Query (http://openquery.com) Exceptional Services for MySQL at a fixed budget. Follow our blog at http://openquery.com/blog/ OurDelta: free enhanced builds for MySQL @ http://ourdelta.org

1 0

[Maria-developers] Updated (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 17 Jul '09

17 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates -=-=(Guest - Wed, 03 Jun 2009, 15:04)=-=- Low Level Design modified. --- /tmp/wklog.17.old.20378 2009-06-03 15:04:54.000000000 +0300 +++ /tmp/wklog.17.new.20378 2009-06-03 15:04:54.000000000 +0300 @@ -135,3 +135,8 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. ------------------------------------------------------------ -=-=(View All Progress Notes, 22 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 17 Jul '09

17 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates -=-=(Guest - Wed, 03 Jun 2009, 15:04)=-=- Low Level Design modified. --- /tmp/wklog.17.old.20378 2009-06-03 15:04:54.000000000 +0300 +++ /tmp/wklog.17.new.20378 2009-06-03 15:04:54.000000000 +0300 @@ -135,3 +135,8 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. ------------------------------------------------------------ -=-=(View All Progress Notes, 22 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 17 Jul '09

17 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: 9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates -=-=(Guest - Wed, 03 Jun 2009, 15:04)=-=- Low Level Design modified. --- /tmp/wklog.17.old.20378 2009-06-03 15:04:54.000000000 +0300 +++ /tmp/wklog.17.new.20378 2009-06-03 15:04:54.000000000 +0300 @@ -135,3 +135,8 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 ------------------------------------------------------------ -=-=(View All Progress Notes, 21 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 17 Jul '09

17 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: 9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates -=-=(Guest - Wed, 03 Jun 2009, 15:04)=-=- Low Level Design modified. --- /tmp/wklog.17.old.20378 2009-06-03 15:04:54.000000000 +0300 +++ /tmp/wklog.17.new.20378 2009-06-03 15:04:54.000000000 +0300 @@ -135,3 +135,8 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 ------------------------------------------------------------ -=-=(View All Progress Notes, 21 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

Re: [Maria-developers] [Merge] lp:~maria-captains/maria/maria-xtradb into lp:maria
by Kristian Nielsen 10 Jul '09

10 Jul '09

Percona <launchpad(a)percona.com> writes: > Percona has proposed merging lp:~maria-captains/maria/maria-xtradb into lp:maria. > > Requested reviews: > Maria-captains (maria-captains) > > Proposal to merge replacement InnoDB->XtraDB Thanks a lot for your efforts in this! I branched the tree and took a look. There are a couple of issues that I think need to be resolved before we can merge it into MariaDB. I have some questions below, but please don't hesitate to ask me for any kind of help needed to move this forward. > === modified file 'storage/innobase/include/sync0rw.h' > --- storage/innobase/include/sync0rw.h 2008-02-19 16:44:09 +0000 > +++ storage/innobase/include/sync0rw.h 2009-03-31 04:19:17 +0000 > +#ifndef INNODB_RW_LOCKS_USE_ATOMICS > +#error INNODB_RW_LOCKS_USE_ATOMICS is not defined. Do you use enough new GCC or compatibles? > +#error Or do you use exact options for CFLAGS? > +#error e.g. (for x86_32): "-m32 -march=i586 -mtune=i686" > +#error e.g. (for Sparc_64): "-m64 -mcpu=v9" > +#error Otherwise, this build may be slower than normal version. > +#endif > + My attempt to build (BUILD/compile-pentium64-max) failed with this error. There were also other build errors (I assume places where the atomics-using code has not been extended with a part that works without the availability of atomics). The reason is that in the MariaDB tree, HAVE_GCC_ATOMIC_BUILTINS is disabled, which caused XtraDB to disable INNODB_RW_LOCKS_USE_ATOMICS, which triggers the above error. I think I understand why this makes sense for Percona, after all using these better synchronisation primitives is part of the reason for using the Percona server in the first place. Can you tell me if Percona has decided not to maintain XtraDB working without the availability of atomic operations? Or if it is just an oversight? I need to discuss with other MariaDB people whether XtraDB for MariaDB should be maintained working without the atomic operations (if so, we should of course be willing to do the work/effort required). So, any thoughts about the best way to deal with this? Should the above #error be removed and XtraDB extended to work without atomics in the MariaDB tree? And is this something Percona wants to do, or should I look into it? Also, Sergei Golubchik told me that HAVE_GCC_ATOMIC_BUILTINS is for my_atomic_ops, and InnoDB/XtraDB shouldn't really be using it. But I need to look more into the code to understand what the problem is, if any. > === added directory 'storage/innobase/mysql-test' > === added directory 'storage/innobase/mysql-test/patches' When I ran the test suite, I got test failures in test main.innodb. I see that the patch contains patches for main MySQL test cases in mysql-test/t/*.test, and also seems to add separate test cases in the storage/innobase/mysql-test/ directory. Do you know what the status is of these test suite modifications? Do the patches need to be applied to the existing test suite, and/or should the extra test cases be used to add to/overwrite the existing tests? We would need to get the test suite to run without problems before merging. Does Percona run the test suite with no failures? Can you suggest which directions I should work in to solve the test failures? Ie. I'm unsure to what extent the extra test cases/patches have already been applied in main MySQL sources, and whether failures are expected or are just due to not being adapted for current MariaDB source changes. Any help with the above would be great. I plan to continue working with you on this so we can get it merged without unnecessary delays. - Kristian.

3 17

[Maria-developers] Storage Engine API changes
by Stewart Smith 08 Jul '09

08 Jul '09

So, I've been making a fair bit of changes around bits of the storage engine API (by all accounts for the better) in Drizzle. The idea being to move the handler to be a cursor on a table, with actions not pertaining that to reside in StorageEngine (e.g. DDL). There's also the (now rather old) change to drop table return code. The next thing that will move into the StorageEngine is metadata handling with the engine being able to be responsible for its own (table) metadata. This is well and truly increasing the differences between MySQL/MariaDB and Drizzle in this area of code - increasing the work needed to port an engine (either way). I would guess it makes little sense for MySQL and MariaDB to diverge here, although I have been (and continue to be) okay with Drizzle diverging. So, is there somebody interested in working with me to have the MySQL/MariaDB API evolve in the same way? -- Stewart Smith

7 14

[Maria-developers] Rev 2819: BUG#31480: Incorrect result for nested subquery when executed via semi join in file:///home/psergey/dev/mysql-next-fix-subq/
by Sergey Petrunya 08 Jul '09

08 Jul '09

At file:///home/psergey/dev/mysql-next-fix-subq/ ------------------------------------------------------------ revno: 2819 revision-id: psergey(a)askmonty.org-20090708174703-dz9uf5b0m6pcvtl6 parent: psergey(a)askmonty.org-20090708095341-9i08n2r8igulpxzz committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: mysql-next-fix-subq timestamp: Wed 2009-07-08 21:47:03 +0400 message: BUG#31480: Incorrect result for nested subquery when executed via semi join Make the fix work with prepared statements: - in previous cset changed calloc to alloc, forgot to add bzero. === modified file 'sql/item_subselect.cc' --- a/sql/item_subselect.cc 2009-07-08 09:53:41 +0000 +++ b/sql/item_subselect.cc 2009-07-08 17:47:03 +0000 @@ -180,10 +180,11 @@ if (!ancestor_used_tables) { set_depth(); - if (!(ancestor_used_tables= - (table_map*)alloc_root(thd->stmt_arena->mem_root, - (1+depth)*sizeof(table_map)))) + size_t size= (1+depth) * sizeof(table_map); + if (!(ancestor_used_tables= (table_map*) + alloc_root(thd->stmt_arena->mem_root, size))) return TRUE; + bzero(ancestor_used_tables, size); furthest_correlated_ancestor= 0; inside_first_fix_fields= TRUE; } @@ -258,7 +259,7 @@ is_correlated= TRUE; furthest_correlated_ancestor= max(furthest_correlated_ancestor, n_levels); if (n_levels > 1) - ancestor_used_tables[n_levels - 2]= dep_map; + ancestor_used_tables[n_levels - 2] |= dep_map; } }

1 0

[Maria-developers] Rev 2727: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim/
by Sergey Petrunya 08 Jul '09

08 Jul '09

At file:///home/psergey/dev/maria-5.1-table-elim/ ------------------------------------------------------------ revno: 2727 revision-id: psergey(a)askmonty.org-20090708171038-9nyc3hcg1o7h8635 parent: psergey(a)askmonty.org-20090630132018-8qwou8bqiq5z1qjg committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Wed 2009-07-08 21:10:38 +0400 message: MWL#17: Table elimination - When collecting Item_subselect::refers_to, put references to the correct subselect entry. === modified file 'sql/sql_lex.cc' --- a/sql/sql_lex.cc 2009-06-22 11:46:31 +0000 +++ b/sql/sql_lex.cc 2009-07-08 17:10:38 +0000 @@ -1780,6 +1780,7 @@ void st_select_lex::mark_as_dependent(st_select_lex *last, Item *dependency) { + SELECT_LEX *next_to_last; /* Mark all selects from resolved to 1 before select where was found table as depended (of select where was found table) @@ -1787,6 +1788,7 @@ for (SELECT_LEX *s= this; s && s != last; s= s->outer_select()) + { if (!(s->uncacheable & UNCACHEABLE_DEPENDENT)) { // Select is dependent of outer select @@ -1802,10 +1804,12 @@ sl->uncacheable|= UNCACHEABLE_UNITED; } } + next_to_last= s; + } is_correlated= TRUE; this->master_unit()->item->is_correlated= TRUE; if (dependency) - this->master_unit()->item->refers_to.push_back(dependency); + next_to_last->master_unit()->item->refers_to.push_back(dependency); } bool st_select_lex_node::set_braces(bool value) { return 1; }

1 0

[Maria-developers] Rev 2818: BUG#31480: Incorrect result for nested subquery when executed via semi join in file:///home/psergey/dev/mysql-next-fix-subq/
by Sergey Petrunya 08 Jul '09

08 Jul '09

At file:///home/psergey/dev/mysql-next-fix-subq/ ------------------------------------------------------------ revno: 2818 revision-id: psergey(a)askmonty.org-20090708095341-9i08n2r8igulpxzz parent: psergey(a)askmonty.org-20090706143329-72s3e73rov2f5tml committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: mysql-next-fix-subq timestamp: Wed 2009-07-08 13:53:41 +0400 message: BUG#31480: Incorrect result for nested subquery when executed via semi join Make the fix work with prepared statements: - collect/save ancestor_used_tables and furthest_correlated_ancestor only at PREPARE phase (at execute() we are unable to tell what table_map the outer reference would tell. since it would be the same anyway, we save it at PREPARE phase) === modified file 'sql/item_subselect.cc' --- a/sql/item_subselect.cc 2009-07-06 14:26:03 +0000 +++ b/sql/item_subselect.cc 2009-07-08 09:53:41 +0000 @@ -39,8 +39,8 @@ Item_subselect::Item_subselect(): Item_result_field(), value_assigned(0), thd(0), substitution(0), engine(0), old_engine(0), used_tables_cache(0), have_to_be_excluded(0), - const_item_cache(1), inside_fix_fields(0), engine_changed(0), changed(0), - is_correlated(FALSE) + const_item_cache(1), inside_first_fix_fields(0), ancestor_used_tables(0), + engine_changed(0), changed(0), is_correlated(FALSE) { with_subselect= 1; reset(); @@ -158,6 +158,7 @@ DBUG_RETURN(RES_OK); } + void Item_subselect::set_depth() { uint n= 0; @@ -166,6 +167,7 @@ this->depth= n - 1; } + bool Item_subselect::fix_fields(THD *thd_param, Item **ref) { char const *save_where= thd_param->where; @@ -175,23 +177,25 @@ DBUG_ASSERT(fixed == 0); engine->set_thd((thd= thd_param)); - if (!inside_fix_fields) + if (!ancestor_used_tables) { set_depth(); - if (!(ancestor_used_tables= (table_map*)thd->calloc((1+depth) * - sizeof(table_map)))) + if (!(ancestor_used_tables= + (table_map*)alloc_root(thd->stmt_arena->mem_root, + (1+depth)*sizeof(table_map)))) return TRUE; furthest_correlated_ancestor= 0; + inside_first_fix_fields= TRUE; } if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res)) return TRUE; - inside_fix_fields++; res= engine->prepare(); - + // all transformation is done (used by prepared statements) changed= 1; + inside_first_fix_fields= FALSE; if (!res) { @@ -220,14 +224,12 @@ if (!(*ref)->fixed) ret= (*ref)->fix_fields(thd, ref); thd->where= save_where; - inside_fix_fields--; return ret; } // Is it one field subselect? if (engine->cols() > max_columns) { my_error(ER_OPERAND_COLUMNS, MYF(0), 1); - inside_fix_fields--; return TRUE; } fix_length_and_dec(); @@ -244,12 +246,23 @@ fixed= 1; err: - inside_fix_fields--; thd->where= save_where; return res; } +void Item_subselect::mark_as_dependent(uint n_levels, table_map dep_map) +{ + if (inside_first_fix_fields) + { + is_correlated= TRUE; + furthest_correlated_ancestor= max(furthest_correlated_ancestor, n_levels); + if (n_levels > 1) + ancestor_used_tables[n_levels - 2]= dep_map; + } +} + + /* Adjust attributes after our parent select has been merged into grandparent === modified file 'sql/item_subselect.h' --- a/sql/item_subselect.h 2009-07-06 07:57:39 +0000 +++ b/sql/item_subselect.h 2009-07-08 09:53:41 +0000 @@ -68,7 +68,7 @@ /* cache of constant state */ bool const_item_cache; - int inside_fix_fields; + int inside_first_fix_fields; public: /* Depth of the subquery predicate. @@ -140,6 +140,7 @@ return null_value; } bool fix_fields(THD *thd, Item **ref); + void mark_as_dependent(uint n_levels, table_map dep_map); void fix_after_pullout(st_select_lex *new_parent, uint parent_tables, Item **ref); virtual bool exec(); === modified file 'sql/sql_lex.cc' --- a/sql/sql_lex.cc 2009-07-06 07:57:39 +0000 +++ b/sql/sql_lex.cc 2009-07-08 09:53:41 +0000 @@ -1929,13 +1929,7 @@ } Item_subselect *subquery_predicate= s->master_unit()->item; if (subquery_predicate) - { - subquery_predicate->is_correlated= TRUE; - subquery_predicate->furthest_correlated_ancestor= - max(subquery_predicate->furthest_correlated_ancestor, n_levels); - if (n_levels > 1) - subquery_predicate->ancestor_used_tables[n_levels - 2]= dep_map; - } + subquery_predicate->mark_as_dependent(n_levels, dep_map); n_levels--; } }

1 0

[Maria-developers] [Merge] lp:~qu1j0t3/maria/solaris10-port into lp:maria
by Toby Thain 07 Jul '09

07 Jul '09

Toby Thain has proposed merging lp:~qu1j0t3/maria/solaris10-port into lp:maria. Requested reviews: Kristian Nielsen (knielsen) Added build scripts for 32 bit x86 architecture on Solaris. Renamed some scripts for consistency. Changed to dynamic linking of libgcc. -- https://code.launchpad.net/~qu1j0t3/maria/solaris10-port/+merge/6999 Your team Maria developers is subscribed to branch lp:maria.

2 4

[Maria-developers] [Branch ~maria-captains/maria/5.1] Rev 2716: Solaris 10 build script fixes by Toby Thain.
by noreply＠launchpad.net 07 Jul '09

07 Jul '09

------------------------------------------------------------ revno: 2716 committer: knielsen(a)knielsen-hq.org branch nick: mariadb-solaris10-port-merge timestamp: Tue 2009-07-07 13:19:24 +0200 message: Solaris 10 build script fixes by Toby Thain. Added build scripts for 32 bit x86 architecture on Solaris. Renamed some scripts for consistency. Changed to dynamic linking of libgcc. removed: BUILD/compile-solaris-amd64-forte-debug added: BUILD/compile-solaris-amd64-debug-forte BUILD/compile-solaris-x86-32 BUILD/compile-solaris-x86-32-debug BUILD/compile-solaris-x86-32-debug-forte BUILD/compile-solaris-x86-forte-32 modified: BUILD/compile-solaris-amd64 BUILD/compile-solaris-amd64-debug === modified file 'BUILD/compile-solaris-amd64' --- BUILD/compile-solaris-amd64 2009-05-09 04:01:53 +0000 +++ BUILD/compile-solaris-amd64 2009-07-07 11:19:24 +0000 @@ -26,7 +26,7 @@ extra_flags="$amd64_cflags -D__sun -m64 -mtune=athlon64" extra_configs="$amd64_configs $max_configs --with-libevent" -LDFLAGS="-lmtmalloc -static-libgcc" +LDFLAGS="-lmtmalloc -R/usr/sfw/lib/64" export LDFLAGS . "$path/FINISH.sh" === modified file 'BUILD/compile-solaris-amd64-debug' --- BUILD/compile-solaris-amd64-debug 2009-05-09 04:01:53 +0000 +++ BUILD/compile-solaris-amd64-debug 2009-07-07 11:19:24 +0000 @@ -5,7 +5,7 @@ extra_flags="$amd64_cflags -D__sun -m64 -mtune=athlon64 $debug_cflags" extra_configs="$amd64_configs $debug_configs $max_configs --with-libevent" -LDFLAGS="-lmtmalloc -static-libgcc" +LDFLAGS="-lmtmalloc -R/usr/sfw/lib/64" export LDFLAGS . "$path/FINISH.sh" === added file 'BUILD/compile-solaris-amd64-debug-forte' --- BUILD/compile-solaris-amd64-debug-forte 1970-01-01 00:00:00 +0000 +++ BUILD/compile-solaris-amd64-debug-forte 2009-07-07 11:19:24 +0000 @@ -0,0 +1,27 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" + +# Take only #define options - the others are gcc specific. +# (real fix is for SETUP.sh not to put gcc specific options in $debug_cflags) +DEFS="" +for F in $debug_cflags ; do + expr "$F" : "^-D" && DEFS="$DEFS $F" +done +debug_cflags="-O0 -g $DEFS" + +extra_flags="-m64 -mt -D_FORTEC_ -xlibmopt -fns=no $debug_cflags" +extra_configs="$max_configs --with-libevent $debug_configs" + +warnings="" +c_warnings="" +cxx_warnings="" +base_cxxflags="-noex" + +CC=cc +CFLAGS="-xstrconst" +CXX=CC +LDFLAGS="-lmtmalloc" + +. "$path/FINISH.sh" === removed file 'BUILD/compile-solaris-amd64-forte-debug' --- BUILD/compile-solaris-amd64-forte-debug 2009-05-09 04:01:53 +0000 +++ BUILD/compile-solaris-amd64-forte-debug 1970-01-01 00:00:00 +0000 @@ -1,27 +0,0 @@ -#!/bin/sh - -path=`dirname $0` -. "$path/SETUP.sh" - -# Take only #define options - the others are gcc specific. -# (real fix is for SETUP.sh not to put gcc specific options in $debug_cflags) -DEFS="" -for F in $debug_cflags ; do - expr "$F" : "^-D" && DEFS="$DEFS $F" -done -debug_cflags="-O0 -g $DEFS" - -extra_flags="-m64 -mt -D_FORTEC_ -xlibmopt -fns=no $debug_cflags" -extra_configs="$max_configs --with-libevent $debug_configs" - -warnings="" -c_warnings="" -cxx_warnings="" -base_cxxflags="-noex" - -CC=cc -CFLAGS="-xstrconst" -CXX=CC -LDFLAGS="-lmtmalloc" - -. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-32' --- BUILD/compile-solaris-x86-32 1970-01-01 00:00:00 +0000 +++ BUILD/compile-solaris-x86-32 2009-07-07 11:19:24 +0000 @@ -0,0 +1,11 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" +extra_flags="-D__sun -m32" +extra_configs="$max_configs --with-libevent" + +LDFLAGS="-lmtmalloc -R/usr/sfw/lib" +export LDFLAGS + +. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-32-debug' --- BUILD/compile-solaris-x86-32-debug 1970-01-01 00:00:00 +0000 +++ BUILD/compile-solaris-x86-32-debug 2009-07-07 11:19:24 +0000 @@ -0,0 +1,11 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" +extra_flags="-D__sun -m32 $debug_cflags" +extra_configs="$max_configs --with-libevent $debug_configs" + +LDFLAGS="-lmtmalloc -R/usr/sfw/lib" +export LDFLAGS + +. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-32-debug-forte' --- BUILD/compile-solaris-x86-32-debug-forte 1970-01-01 00:00:00 +0000 +++ BUILD/compile-solaris-x86-32-debug-forte 2009-07-07 11:19:24 +0000 @@ -0,0 +1,27 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" + +# Take only #define options - the others are gcc specific. +# (real fix is for SETUP.sh not to put gcc specific options in $debug_cflags) +DEFS="" +for F in $debug_cflags ; do + expr "$F" : "^-D" && DEFS="$DEFS $F" +done +debug_cflags="-O0 -g $DEFS" + +extra_flags="-m32 -mt -D_FORTEC_ -xbuiltin=%all -xlibmil -xlibmopt -fns=no -xprefetch=auto -xprefetch_level=3 $debug_cflags" +extra_configs="$max_configs --with-libevent $debug_configs" + +warnings="" +c_warnings="" +cxx_warnings="" +base_cxxflags="-noex" + +CC=cc +CFLAGS="-xstrconst" +CXX=CC +LDFLAGS="-lmtmalloc" + +. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-forte-32' --- BUILD/compile-solaris-x86-forte-32 1970-01-01 00:00:00 +0000 +++ BUILD/compile-solaris-x86-forte-32 2009-07-07 11:19:24 +0000 @@ -0,0 +1,19 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" + +extra_flags="-m32 -mt -D_FORTEC_ -xbuiltin=%all -xlibmil -xlibmopt -fns=no -xprefetch=auto -xprefetch_level=3" +extra_configs="$max_configs --with-libevent" + +warnings="" +c_warnings="" +cxx_warnings="" +base_cxxflags="-noex" + +CC=cc +CFLAGS="-xstrconst" +CXX=CC +LDFLAGS="-lmtmalloc" + +. "$path/FINISH.sh" -- lp:maria https://code.launchpad.net/~maria-captains/maria/5.1 Your team Maria developers is subscribed to branch lp:maria. To unsubscribe from this branch go to https://code.launchpad.net/~maria-captains/maria/5.1/+edit-subscription.

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (knielsen:2716)
by knielsen＠knielsen-hq.org 07 Jul '09

07 Jul '09

#At lp:maria 2716 knielsen(a)knielsen-hq.org 2009-07-07 Solaris 10 build script fixes by Toby Thain. Added build scripts for 32 bit x86 architecture on Solaris. Renamed some scripts for consistency. Changed to dynamic linking of libgcc. removed: BUILD/compile-solaris-amd64-forte-debug added: BUILD/compile-solaris-amd64-debug-forte BUILD/compile-solaris-x86-32 BUILD/compile-solaris-x86-32-debug BUILD/compile-solaris-x86-32-debug-forte BUILD/compile-solaris-x86-forte-32 modified: BUILD/compile-solaris-amd64 BUILD/compile-solaris-amd64-debug per-file messages: BUILD/compile-solaris-amd64 Changed to dynamic linking of libgcc. The -static-libgcc was a legacy of the original build scripts. -R (analogous to -L link time search path) is a Solaris mechanism to ensure a needed lib directory is searched at runtime. In Solaris 10, gcc comes bundled, under /usr/sfw, allowing to use it without creating dependency problems. This allows eg. benefiting from ordinary system patch maintenance. BUILD/compile-solaris-amd64-debug Changed to dynamic linking of libgcc. The -static-libgcc was a legacy of the original build scripts. -R (analogous to -L link time search path) is a Solaris mechanism to ensure a needed lib directory is searched at runtime. In Solaris 10, gcc comes bundled, under /usr/sfw, allowing to use it without creating dependency problems. This allows eg. benefiting from ordinary system patch maintenance. === modified file 'BUILD/compile-solaris-amd64' --- a/BUILD/compile-solaris-amd64 2009-05-09 04:01:53 +0000 +++ b/BUILD/compile-solaris-amd64 2009-07-07 11:19:24 +0000 @@ -26,7 +26,7 @@ path=`dirname $0` extra_flags="$amd64_cflags -D__sun -m64 -mtune=athlon64" extra_configs="$amd64_configs $max_configs --with-libevent" -LDFLAGS="-lmtmalloc -static-libgcc" +LDFLAGS="-lmtmalloc -R/usr/sfw/lib/64" export LDFLAGS . "$path/FINISH.sh" === modified file 'BUILD/compile-solaris-amd64-debug' --- a/BUILD/compile-solaris-amd64-debug 2009-05-09 04:01:53 +0000 +++ b/BUILD/compile-solaris-amd64-debug 2009-07-07 11:19:24 +0000 @@ -5,7 +5,7 @@ path=`dirname $0` extra_flags="$amd64_cflags -D__sun -m64 -mtune=athlon64 $debug_cflags" extra_configs="$amd64_configs $debug_configs $max_configs --with-libevent" -LDFLAGS="-lmtmalloc -static-libgcc" +LDFLAGS="-lmtmalloc -R/usr/sfw/lib/64" export LDFLAGS . "$path/FINISH.sh" === added file 'BUILD/compile-solaris-amd64-debug-forte' --- a/BUILD/compile-solaris-amd64-debug-forte 1970-01-01 00:00:00 +0000 +++ b/BUILD/compile-solaris-amd64-debug-forte 2009-07-07 11:19:24 +0000 @@ -0,0 +1,27 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" + +# Take only #define options - the others are gcc specific. +# (real fix is for SETUP.sh not to put gcc specific options in $debug_cflags) +DEFS="" +for F in $debug_cflags ; do + expr "$F" : "^-D" && DEFS="$DEFS $F" +done +debug_cflags="-O0 -g $DEFS" + +extra_flags="-m64 -mt -D_FORTEC_ -xlibmopt -fns=no $debug_cflags" +extra_configs="$max_configs --with-libevent $debug_configs" + +warnings="" +c_warnings="" +cxx_warnings="" +base_cxxflags="-noex" + +CC=cc +CFLAGS="-xstrconst" +CXX=CC +LDFLAGS="-lmtmalloc" + +. "$path/FINISH.sh" === removed file 'BUILD/compile-solaris-amd64-forte-debug' --- a/BUILD/compile-solaris-amd64-forte-debug 2009-05-09 04:01:53 +0000 +++ b/BUILD/compile-solaris-amd64-forte-debug 1970-01-01 00:00:00 +0000 @@ -1,27 +0,0 @@ -#!/bin/sh - -path=`dirname $0` -. "$path/SETUP.sh" - -# Take only #define options - the others are gcc specific. -# (real fix is for SETUP.sh not to put gcc specific options in $debug_cflags) -DEFS="" -for F in $debug_cflags ; do - expr "$F" : "^-D" && DEFS="$DEFS $F" -done -debug_cflags="-O0 -g $DEFS" - -extra_flags="-m64 -mt -D_FORTEC_ -xlibmopt -fns=no $debug_cflags" -extra_configs="$max_configs --with-libevent $debug_configs" - -warnings="" -c_warnings="" -cxx_warnings="" -base_cxxflags="-noex" - -CC=cc -CFLAGS="-xstrconst" -CXX=CC -LDFLAGS="-lmtmalloc" - -. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-32' --- a/BUILD/compile-solaris-x86-32 1970-01-01 00:00:00 +0000 +++ b/BUILD/compile-solaris-x86-32 2009-07-07 11:19:24 +0000 @@ -0,0 +1,11 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" +extra_flags="-D__sun -m32" +extra_configs="$max_configs --with-libevent" + +LDFLAGS="-lmtmalloc -R/usr/sfw/lib" +export LDFLAGS + +. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-32-debug' --- a/BUILD/compile-solaris-x86-32-debug 1970-01-01 00:00:00 +0000 +++ b/BUILD/compile-solaris-x86-32-debug 2009-07-07 11:19:24 +0000 @@ -0,0 +1,11 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" +extra_flags="-D__sun -m32 $debug_cflags" +extra_configs="$max_configs --with-libevent $debug_configs" + +LDFLAGS="-lmtmalloc -R/usr/sfw/lib" +export LDFLAGS + +. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-32-debug-forte' --- a/BUILD/compile-solaris-x86-32-debug-forte 1970-01-01 00:00:00 +0000 +++ b/BUILD/compile-solaris-x86-32-debug-forte 2009-07-07 11:19:24 +0000 @@ -0,0 +1,27 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" + +# Take only #define options - the others are gcc specific. +# (real fix is for SETUP.sh not to put gcc specific options in $debug_cflags) +DEFS="" +for F in $debug_cflags ; do + expr "$F" : "^-D" && DEFS="$DEFS $F" +done +debug_cflags="-O0 -g $DEFS" + +extra_flags="-m32 -mt -D_FORTEC_ -xbuiltin=%all -xlibmil -xlibmopt -fns=no -xprefetch=auto -xprefetch_level=3 $debug_cflags" +extra_configs="$max_configs --with-libevent $debug_configs" + +warnings="" +c_warnings="" +cxx_warnings="" +base_cxxflags="-noex" + +CC=cc +CFLAGS="-xstrconst" +CXX=CC +LDFLAGS="-lmtmalloc" + +. "$path/FINISH.sh" === added file 'BUILD/compile-solaris-x86-forte-32' --- a/BUILD/compile-solaris-x86-forte-32 1970-01-01 00:00:00 +0000 +++ b/BUILD/compile-solaris-x86-forte-32 2009-07-07 11:19:24 +0000 @@ -0,0 +1,19 @@ +#!/bin/sh + +path=`dirname $0` +. "$path/SETUP.sh" + +extra_flags="-m32 -mt -D_FORTEC_ -xbuiltin=%all -xlibmil -xlibmopt -fns=no -xprefetch=auto -xprefetch_level=3" +extra_configs="$max_configs --with-libevent" + +warnings="" +c_warnings="" +cxx_warnings="" +base_cxxflags="-noex" + +CC=cc +CFLAGS="-xstrconst" +CXX=CC +LDFLAGS="-lmtmalloc" + +. "$path/FINISH.sh"

1 0

[Maria-developers] Rev 2817: BUG#42742: crash in setup_sj_materialization, Copy_field::set in file:///home/psergey/dev/mysql-next-fix-subq/
by Sergey Petrunya 06 Jul '09

06 Jul '09

At file:///home/psergey/dev/mysql-next-fix-subq/ ------------------------------------------------------------ revno: 2817 revision-id: psergey(a)askmonty.org-20090706143329-72s3e73rov2f5tml parent: psergey(a)askmonty.org-20090706142603-z3z8ku4fdah6ntwv committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: mysql-next-fix-subq timestamp: Mon 2009-07-06 18:33:29 +0400 message: BUG#42742: crash in setup_sj_materialization, Copy_field::set - If a semi-join strategy covers certain [first_table; last_table] range in join order, do reset the sj_strategy member for all tables within the range, except the first one. Failure to do so caused EXPLAIN/execution code to try applying two strategies at once which would cause all kinds of undesired effects. === modified file 'mysql-test/r/subselect_sj2.result' --- a/mysql-test/r/subselect_sj2.result 2009-03-21 15:31:38 +0000 +++ b/mysql-test/r/subselect_sj2.result 2009-07-06 14:33:29 +0000 @@ -689,3 +689,19 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables drop table t1, t2; +# +# BUG#42742: crash in setup_sj_materialization, Copy_field::set +# +create table t3 ( c1 year) engine=innodb; +insert into t3 values (2135),(2142); +create table t2 (c1 tinytext,c2 text,c6 timestamp) engine=innodb; +# The following must not crash, EXPLAIN should show one SJ strategy, not a mix: +explain select 1 from t2 where +c2 in (select 1 from t3, t2) and +c1 in (select convert(c6,char(1)) from t2); +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t2 ALL NULL NULL NULL NULL 1 Using where +1 PRIMARY t2 ALL NULL NULL NULL NULL 1 +1 PRIMARY t2 ALL NULL NULL NULL NULL 1 Using where; Using join buffer +1 PRIMARY t3 ALL NULL NULL NULL NULL 2 FirstMatch(t2); Using join buffer +drop table t2, t3; === modified file 'mysql-test/r/subselect_sj2_jcl6.result' --- a/mysql-test/r/subselect_sj2_jcl6.result 2009-06-19 09:12:06 +0000 +++ b/mysql-test/r/subselect_sj2_jcl6.result 2009-07-06 14:33:29 +0000 @@ -693,6 +693,22 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables drop table t1, t2; +# +# BUG#42742: crash in setup_sj_materialization, Copy_field::set +# +create table t3 ( c1 year) engine=innodb; +insert into t3 values (2135),(2142); +create table t2 (c1 tinytext,c2 text,c6 timestamp) engine=innodb; +# The following must not crash, EXPLAIN should show one SJ strategy, not a mix: +explain select 1 from t2 where +c2 in (select 1 from t3, t2) and +c1 in (select convert(c6,char(1)) from t2); +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t2 ALL NULL NULL NULL NULL 1 Using where +1 PRIMARY t2 ALL NULL NULL NULL NULL 1 Using join buffer +1 PRIMARY t2 ALL NULL NULL NULL NULL 1 Using where; Using join buffer +1 PRIMARY t3 ALL NULL NULL NULL NULL 2 FirstMatch(t2); Using join buffer +drop table t2, t3; set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value === modified file 'mysql-test/t/subselect_sj2.test' --- a/mysql-test/t/subselect_sj2.test 2009-03-21 15:31:38 +0000 +++ b/mysql-test/t/subselect_sj2.test 2009-07-06 14:33:29 +0000 @@ -872,3 +872,15 @@ explain select 1 from t2 where c2 = any (select log10(null) from t1 where c6 <null) ; drop table t1, t2; +--echo # +--echo # BUG#42742: crash in setup_sj_materialization, Copy_field::set +--echo # +create table t3 ( c1 year) engine=innodb; +insert into t3 values (2135),(2142); +create table t2 (c1 tinytext,c2 text,c6 timestamp) engine=innodb; +-- echo # The following must not crash, EXPLAIN should show one SJ strategy, not a mix: +explain select 1 from t2 where + c2 in (select 1 from t3, t2) and + c1 in (select convert(c6,char(1)) from t2); +drop table t2, t3; + === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-07-06 07:57:39 +0000 +++ b/sql/sql_select.cc 2009-07-06 14:33:29 +0000 @@ -7916,7 +7916,11 @@ uint i_end= first + join->best_positions[first].n_sj_tables; for (uint i= first; i < i_end; i++) + { + if (i != first) + join->best_positions[i].sj_strategy= SJ_OPT_NONE; handled_tabs |= join->best_positions[i].table->table->map; + } if (tablenr != first) pos->sj_strategy= SJ_OPT_NONE;

1 0