- developers - lists.mariadb.org

[Maria-developers] Updated (by Guest): Implement UNION ALL without usage of a temporary table (44)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Implement UNION ALL without usage of a temporary table CREATION DATE..: Fri, 14 Aug 2009, 08:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: Monty, Psergey CATEGORY.......: Client-BackLog TASK ID........: 44 (http://askmonty.org/worklog/?tid=44) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 14 Aug 2009, 08:41)=-=- High-Level Specification modified. --- /tmp/wklog.44.old.22182 2009-08-14 08:41:17.000000000 +0300 +++ /tmp/wklog.44.new.22182 2009-08-14 08:41:17.000000000 +0300 @@ -1 +1,205 @@ +<contents> +1. Handling union operations in MySQL Server + 1.1. Specifics of MySQL union operations + 1.2 Validation of union units + 1.3 Execution of union units +2. Optimizations improving performance of UNION ALL operations + 2.1 Execution of UNION ALL without temporary table + 2.2. Avoiding unnecessary copying + 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations +3. Other possible optimizations for union units +</contents> + +1. Handling union operations in MySQL Server +================================== + +1.1. Specifics of MySQL union operations +------------------------------------------------------ + +UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL +allows us to use these operations in a sequence, one after another. For example +the following queries are accepted by the MySQL Server: + (select a1,b1,c1 from t1 where a1=b1) union (select a2,b2,c2 from t2 where +a2!=b2) union + (select a3,b3,c3 from t3 where a3>b3); (1) + (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where +a2!=b2) union all + (select a3,b3,c3 from t3 where a3>b3); (2) +Any mix of UNION and UNION ALL is also acceptable: + (select a1,b1,c3 from t1 where a1=b1) union (select a2,b2,c3 from t2 where +a2!=b2) union all + (select a3,b3,c3 from t3 where a3>b3); (3) + (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where +a2!=b2) union + (select a3,b3,c3 from t3 where a3>b3); (4) +It should be noted that query (4) is equivalent to query (1). At the same time +query (3) is not equivalent to any of the queries (1),(2),(4). +In general any UNION ALL in a sequence of union operations can be equivalently +substituted for UNION if there occur another UNION further in the sequence. +MySQL does not accept nested unions. For example the following valid query is +considered by MySQL Server as erroneous: + ( (select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2) +) union all + ( (select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4) ) + +A sequence of select constructs separated by UNION/UNION ALL is called 'union +unit' if it s not a part of another such sequence. +A union unit can be executed as a query. It also can be used as a subquery. +A union unit can be optionally appended by an ORDER BY and/or LIMIT construct. +In this case it cannot be used as a subquery. + +1.2 Validation of union units +---------------------------------- + +When the parser stage is over the further processing of a union unit is +performed by the function mysql_union. +The function first validate the unit in the method SELECT_LEX_UNIT::prepare. +The method first validates each of the select constructs of the unit and then it +checks that all select are compatible. The method checks that the selects return +the same number of columns and for each set of columns with the same number k +there is a type to which the types of the columns can be coerced. This type is +considered as the type of column k of the result set returned by the union unit. +For example, if in the query (1) the columns b1, b2 and b3 are of the types int, +bigint and double respectively then the second column of the union unit will be +of the type double. If the types of the columns c1,c2,c3 are specified as +varchar(10), varchar(20), varchar(10) then the type of the corresponding column +of the result set will be varchar(20). If the columns have different collations +then a collation from which all these collations can be derived is looked for +and it is assigned as the +collation of the third column in the result set. +After compatibility of the corresponding select columns has been checked and the +types of the columns from of the result set have been determined the method +SELECT_LEX_UNIT::prepare creates a temporary table to store the rows of the +result set for the union unit. Currently rows returned by the selects from the +union unit are always written into a temporary table. To force selects to send +rows to this temporary table SELECT_LEX_UNIT::prepare creates JOIN objects for +the selects such that the JOIN::result field refers to an object of the class +select_union. All selects from a union unit share the same select_union object. + +1.3 Execution of union units +---------------------------------- + +After SELECT_LEX_UNIT::prepare has successfully validated the union unit, has +created a temporary table as a container for rows from the result sets returned +by the selects of the unit, and has prepared all data structures needed for +execution, the function mysql_union invokes SELECT_LEX_UNIT::exec. +The method SELECT_LEX_UNIT::exec processes the selects from the union unit one +by one. +Each select first is optimized with JOIN::optimize(), then it's executed with +JOIN::exec().The result rows from each select are sent to a temporary table. +This table accumulates all rows that are to be returned by the union unit. For +UNION operations duplicate rows are not added, for UNION ALL operations all +records are added. It is achieved by enabling and disabling usage of the unique +index defined on all fields of the temporary table. The index is never used if +only UINION ALL operation occurs in the unit. Otherwise it is enabled before +the first select is executed and disabled after the last UNION operation. +To send rows to the temporary table the method select_union::send_data is used. +For a row it receives from the currently executed select the method first stores +the fields of the row in in the fields of the record buffer of the temporary +table. To do this the method calls function fill_record. All needed type +conversions of the field values are performed when they are stored the record +buffer. After this the method select_union::send_data calls the ha_write_row +handler function to write the record from the buffer to the temporary table. A +possible error on duplicate key that occurs with an attempt to write a duplicate +row is ignored. +After all rows received from all selects have been placed into the temporary +table the method SELECT_LEX_UNIT::exec calls mysql_select that reads rows +from the temporary table and sends them to the output stream (to the client). If +there is an ORDER BY clause to be applied to result of the union unit then the +rows read from the temporary table have to be sorted first. + +2. Optimizations improving performance of UNION ALL operations +================================================= + +The following three optimizations are proposed to be implemented in the +framework of this task. + +2.1 Execution of UNION ALL without temporary table +------------------------------------------------------------------ + +If a union unit with only UNION ALL operations is used at the top level of the +query (in other words it's not used as a subquery) and is not appended with an +ORDER BY clause then it does not make sense to send rows received from selects +to a temporary table at all. After all needed type conversions have been done +the row fields could be sent directly into the output stream. It would improve +the performance of UNION ALL operations since writing to the temporary table and +reading from it would not be needed anymore. In the cases when the result set is +big enough and the temporary table cannot be allocated in the main memory the +performance gains would be significant. Besides, the client could get the first +result rows at once as it would not have to wait until all selects have been +executed. +To make an UNION ALL operation not to send rows to a temporary table we could +provide the JOIN objects created for the selects from the union unit with an +interceptor object that differs from the one they use now. In the current code +they use an object of the class select_union derived from the +select_result_interceptor class. The new interceptor object of the class that +we'll call select_union_send (by analogy with the class select_send) shall +inherit from the select_union and shall have its own implementations of the +virtual methods send_data, send_fields, and send_eof. +The method send_data shall send fields received from selects to the record +buffer of the temporary table and then from this buffer to the output stream. +The method send_fields shall send the format of the rows to the client before it +starts getting records from the first select , while the method send_eof shall +signal about the end of the rows after the last select finishes sending records. +The method create_result_table of the class select_union shall be re-defined +as virtual. The implementation of this method for the class select_union_send +shall call select_union::create_result_table and then shall build internal +structures needed for select_unionsend::send_data. So, the definition of the +class select_union_send should look like this: + class select_union_send :public select_union + { + ... // private structures + public: + select_union_send() :select_union(), ...{...} + bool send_data(List<Item> &items); + bool send_fields(List<Item> &list, uint flags); + bool create_result_table(THD *thd, List<Item> *column_types, + bool is_distinct, ulonglong options, + const char *alias); + }; + +2.2. Avoiding unnecessary copying +------------------------------------------ + +If a field does not need type conversion it does not make sense to send it to a +record buffer. It can be sent directly to the output stream. Different selects +can require type conversions for different columns. +Let's provide each select from the union unit with a data structure (e.g. a +bitmap) that says what fields require conversions, and what don't . Before +execution of a select this data structure must be passed to the +select_union_send object shared by all selects from the unit. The info in this +structure will tell select_union_send::send_data what fields should be sent to +the record buffer for type conversion and what can be sent directly to the +output stream. In this case another variant of the fill_record procedure is +needed that would take as parameter the info that says what fields are to be +stored in the record buffer. + +2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations +---------------------------------------------------------------------------------------------------------- + +If a union unit with a mix of UNIIN/UNION ALL operations and without ORDER BY is +used at the top level of a query then any UNION ALL operation after the last +UNION operation can be executed in more efficient way than it's done in the +current implementation. More exactly, the rows from any select that follows +after the second operand of the last UNION operations could be sent directly to +the output stream. In this case two interceptor objects have to be created: one, +of the type select_union, is shared by the selects for which UNION operations +are performed, another, of the type select_union_send, is shared by the the +remaining selects. For this optimization the method SELECT_LEX_UNIT::exec is to +undergo a serious re-work. + + +3. Other possible optimizations for union units +================================= + +The following optimizations are not supposed to be implemented in the framework +this task. +1. For a union unit containing only UNION ALL with an ORDER BY send rows from +selects directly to the sorting procedure. +2. For a union unit at the top level of the query without ORDER BY clause send +any row received from an operand of a UNION operation directly to the output +stream as soon as it has been checked by a lookup in the temporary table that +it's not a duplicate. +3. Not to use temporary table for any union unit used in EXIST or IN subquery. + DESCRIPTION: Currently when any union operation is executed the rows received from its operands are always sent to a temporary table. Meanwhile for a UNION ALL operation that is used at the top level of a query without an ORDER BY clause it is not necessary. In this case the rows could be sent directly to the client. The goal of this task is to provide such an implementation of UNION ALL operation that would not use temporary table at all in certain, most usable cases. HIGH-LEVEL SPECIFICATION: <contents> 1. Handling union operations in MySQL Server 1.1. Specifics of MySQL union operations 1.2 Validation of union units 1.3 Execution of union units 2. Optimizations improving performance of UNION ALL operations 2.1 Execution of UNION ALL without temporary table 2.2. Avoiding unnecessary copying 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations 3. Other possible optimizations for union units </contents> 1. Handling union operations in MySQL Server ================================== 1.1. Specifics of MySQL union operations ------------------------------------------------------ UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL allows us to use these operations in a sequence, one after another. For example the following queries are accepted by the MySQL Server: (select a1,b1,c1 from t1 where a1=b1) union (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (1) (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (2) Any mix of UNION and UNION ALL is also acceptable: (select a1,b1,c3 from t1 where a1=b1) union (select a2,b2,c3 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (3) (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (4) It should be noted that query (4) is equivalent to query (1). At the same time query (3) is not equivalent to any of the queries (1),(2),(4). In general any UNION ALL in a sequence of union operations can be equivalently substituted for UNION if there occur another UNION further in the sequence. MySQL does not accept nested unions. For example the following valid query is considered by MySQL Server as erroneous: ( (select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2) ) union all ( (select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4) ) A sequence of select constructs separated by UNION/UNION ALL is called 'union unit' if it s not a part of another such sequence. A union unit can be executed as a query. It also can be used as a subquery. A union unit can be optionally appended by an ORDER BY and/or LIMIT construct. In this case it cannot be used as a subquery. 1.2 Validation of union units ---------------------------------- When the parser stage is over the further processing of a union unit is performed by the function mysql_union. The function first validate the unit in the method SELECT_LEX_UNIT::prepare. The method first validates each of the select constructs of the unit and then it checks that all select are compatible. The method checks that the selects return the same number of columns and for each set of columns with the same number k there is a type to which the types of the columns can be coerced. This type is considered as the type of column k of the result set returned by the union unit. For example, if in the query (1) the columns b1, b2 and b3 are of the types int, bigint and double respectively then the second column of the union unit will be of the type double. If the types of the columns c1,c2,c3 are specified as varchar(10), varchar(20), varchar(10) then the type of the corresponding column of the result set will be varchar(20). If the columns have different collations then a collation from which all these collations can be derived is looked for and it is assigned as the collation of the third column in the result set. After compatibility of the corresponding select columns has been checked and the types of the columns from of the result set have been determined the method SELECT_LEX_UNIT::prepare creates a temporary table to store the rows of the result set for the union unit. Currently rows returned by the selects from the union unit are always written into a temporary table. To force selects to send rows to this temporary table SELECT_LEX_UNIT::prepare creates JOIN objects for the selects such that the JOIN::result field refers to an object of the class select_union. All selects from a union unit share the same select_union object. 1.3 Execution of union units ---------------------------------- After SELECT_LEX_UNIT::prepare has successfully validated the union unit, has created a temporary table as a container for rows from the result sets returned by the selects of the unit, and has prepared all data structures needed for execution, the function mysql_union invokes SELECT_LEX_UNIT::exec. The method SELECT_LEX_UNIT::exec processes the selects from the union unit one by one. Each select first is optimized with JOIN::optimize(), then it's executed with JOIN::exec().The result rows from each select are sent to a temporary table. This table accumulates all rows that are to be returned by the union unit. For UNION operations duplicate rows are not added, for UNION ALL operations all records are added. It is achieved by enabling and disabling usage of the unique index defined on all fields of the temporary table. The index is never used if only UINION ALL operation occurs in the unit. Otherwise it is enabled before the first select is executed and disabled after the last UNION operation. To send rows to the temporary table the method select_union::send_data is used. For a row it receives from the currently executed select the method first stores the fields of the row in in the fields of the record buffer of the temporary table. To do this the method calls function fill_record. All needed type conversions of the field values are performed when they are stored the record buffer. After this the method select_union::send_data calls the ha_write_row handler function to write the record from the buffer to the temporary table. A possible error on duplicate key that occurs with an attempt to write a duplicate row is ignored. After all rows received from all selects have been placed into the temporary table the method SELECT_LEX_UNIT::exec calls mysql_select that reads rows from the temporary table and sends them to the output stream (to the client). If there is an ORDER BY clause to be applied to result of the union unit then the rows read from the temporary table have to be sorted first. 2. Optimizations improving performance of UNION ALL operations ================================================= The following three optimizations are proposed to be implemented in the framework of this task. 2.1 Execution of UNION ALL without temporary table ------------------------------------------------------------------ If a union unit with only UNION ALL operations is used at the top level of the query (in other words it's not used as a subquery) and is not appended with an ORDER BY clause then it does not make sense to send rows received from selects to a temporary table at all. After all needed type conversions have been done the row fields could be sent directly into the output stream. It would improve the performance of UNION ALL operations since writing to the temporary table and reading from it would not be needed anymore. In the cases when the result set is big enough and the temporary table cannot be allocated in the main memory the performance gains would be significant. Besides, the client could get the first result rows at once as it would not have to wait until all selects have been executed. To make an UNION ALL operation not to send rows to a temporary table we could provide the JOIN objects created for the selects from the union unit with an interceptor object that differs from the one they use now. In the current code they use an object of the class select_union derived from the select_result_interceptor class. The new interceptor object of the class that we'll call select_union_send (by analogy with the class select_send) shall inherit from the select_union and shall have its own implementations of the virtual methods send_data, send_fields, and send_eof. The method send_data shall send fields received from selects to the record buffer of the temporary table and then from this buffer to the output stream. The method send_fields shall send the format of the rows to the client before it starts getting records from the first select , while the method send_eof shall signal about the end of the rows after the last select finishes sending records. The method create_result_table of the class select_union shall be re-defined as virtual. The implementation of this method for the class select_union_send shall call select_union::create_result_table and then shall build internal structures needed for select_unionsend::send_data. So, the definition of the class select_union_send should look like this: class select_union_send :public select_union { ... // private structures public: select_union_send() :select_union(), ...{...} bool send_data(List<Item> &items); bool send_fields(List<Item> &list, uint flags); bool create_result_table(THD *thd, List<Item> *column_types, bool is_distinct, ulonglong options, const char *alias); }; 2.2. Avoiding unnecessary copying ------------------------------------------ If a field does not need type conversion it does not make sense to send it to a record buffer. It can be sent directly to the output stream. Different selects can require type conversions for different columns. Let's provide each select from the union unit with a data structure (e.g. a bitmap) that says what fields require conversions, and what don't . Before execution of a select this data structure must be passed to the select_union_send object shared by all selects from the unit. The info in this structure will tell select_union_send::send_data what fields should be sent to the record buffer for type conversion and what can be sent directly to the output stream. In this case another variant of the fill_record procedure is needed that would take as parameter the info that says what fields are to be stored in the record buffer. 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations ---------------------------------------------------------------------------------------------------------- If a union unit with a mix of UNIIN/UNION ALL operations and without ORDER BY is used at the top level of a query then any UNION ALL operation after the last UNION operation can be executed in more efficient way than it's done in the current implementation. More exactly, the rows from any select that follows after the second operand of the last UNION operations could be sent directly to the output stream. In this case two interceptor objects have to be created: one, of the type select_union, is shared by the selects for which UNION operations are performed, another, of the type select_union_send, is shared by the the remaining selects. For this optimization the method SELECT_LEX_UNIT::exec is to undergo a serious re-work. 3. Other possible optimizations for union units ================================= The following optimizations are not supposed to be implemented in the framework this task. 1. For a union unit containing only UNION ALL with an ORDER BY send rows from selects directly to the sorting procedure. 2. For a union unit at the top level of the query without ORDER BY clause send any row received from an operand of a UNION operation directly to the output stream as soon as it has been checked by a lookup in the temporary table that it's not a duplicate. 3. Not to use temporary table for any union unit used in EXIST or IN subquery. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Implement UNION ALL without usage of a temporary table (44)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Implement UNION ALL without usage of a temporary table CREATION DATE..: Fri, 14 Aug 2009, 08:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: Monty, Psergey CATEGORY.......: Client-BackLog TASK ID........: 44 (http://askmonty.org/worklog/?tid=44) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 14 Aug 2009, 08:41)=-=- High-Level Specification modified. --- /tmp/wklog.44.old.22182 2009-08-14 08:41:17.000000000 +0300 +++ /tmp/wklog.44.new.22182 2009-08-14 08:41:17.000000000 +0300 @@ -1 +1,205 @@ +<contents> +1. Handling union operations in MySQL Server + 1.1. Specifics of MySQL union operations + 1.2 Validation of union units + 1.3 Execution of union units +2. Optimizations improving performance of UNION ALL operations + 2.1 Execution of UNION ALL without temporary table + 2.2. Avoiding unnecessary copying + 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations +3. Other possible optimizations for union units +</contents> + +1. Handling union operations in MySQL Server +================================== + +1.1. Specifics of MySQL union operations +------------------------------------------------------ + +UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL +allows us to use these operations in a sequence, one after another. For example +the following queries are accepted by the MySQL Server: + (select a1,b1,c1 from t1 where a1=b1) union (select a2,b2,c2 from t2 where +a2!=b2) union + (select a3,b3,c3 from t3 where a3>b3); (1) + (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where +a2!=b2) union all + (select a3,b3,c3 from t3 where a3>b3); (2) +Any mix of UNION and UNION ALL is also acceptable: + (select a1,b1,c3 from t1 where a1=b1) union (select a2,b2,c3 from t2 where +a2!=b2) union all + (select a3,b3,c3 from t3 where a3>b3); (3) + (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where +a2!=b2) union + (select a3,b3,c3 from t3 where a3>b3); (4) +It should be noted that query (4) is equivalent to query (1). At the same time +query (3) is not equivalent to any of the queries (1),(2),(4). +In general any UNION ALL in a sequence of union operations can be equivalently +substituted for UNION if there occur another UNION further in the sequence. +MySQL does not accept nested unions. For example the following valid query is +considered by MySQL Server as erroneous: + ( (select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2) +) union all + ( (select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4) ) + +A sequence of select constructs separated by UNION/UNION ALL is called 'union +unit' if it s not a part of another such sequence. +A union unit can be executed as a query. It also can be used as a subquery. +A union unit can be optionally appended by an ORDER BY and/or LIMIT construct. +In this case it cannot be used as a subquery. + +1.2 Validation of union units +---------------------------------- + +When the parser stage is over the further processing of a union unit is +performed by the function mysql_union. +The function first validate the unit in the method SELECT_LEX_UNIT::prepare. +The method first validates each of the select constructs of the unit and then it +checks that all select are compatible. The method checks that the selects return +the same number of columns and for each set of columns with the same number k +there is a type to which the types of the columns can be coerced. This type is +considered as the type of column k of the result set returned by the union unit. +For example, if in the query (1) the columns b1, b2 and b3 are of the types int, +bigint and double respectively then the second column of the union unit will be +of the type double. If the types of the columns c1,c2,c3 are specified as +varchar(10), varchar(20), varchar(10) then the type of the corresponding column +of the result set will be varchar(20). If the columns have different collations +then a collation from which all these collations can be derived is looked for +and it is assigned as the +collation of the third column in the result set. +After compatibility of the corresponding select columns has been checked and the +types of the columns from of the result set have been determined the method +SELECT_LEX_UNIT::prepare creates a temporary table to store the rows of the +result set for the union unit. Currently rows returned by the selects from the +union unit are always written into a temporary table. To force selects to send +rows to this temporary table SELECT_LEX_UNIT::prepare creates JOIN objects for +the selects such that the JOIN::result field refers to an object of the class +select_union. All selects from a union unit share the same select_union object. + +1.3 Execution of union units +---------------------------------- + +After SELECT_LEX_UNIT::prepare has successfully validated the union unit, has +created a temporary table as a container for rows from the result sets returned +by the selects of the unit, and has prepared all data structures needed for +execution, the function mysql_union invokes SELECT_LEX_UNIT::exec. +The method SELECT_LEX_UNIT::exec processes the selects from the union unit one +by one. +Each select first is optimized with JOIN::optimize(), then it's executed with +JOIN::exec().The result rows from each select are sent to a temporary table. +This table accumulates all rows that are to be returned by the union unit. For +UNION operations duplicate rows are not added, for UNION ALL operations all +records are added. It is achieved by enabling and disabling usage of the unique +index defined on all fields of the temporary table. The index is never used if +only UINION ALL operation occurs in the unit. Otherwise it is enabled before +the first select is executed and disabled after the last UNION operation. +To send rows to the temporary table the method select_union::send_data is used. +For a row it receives from the currently executed select the method first stores +the fields of the row in in the fields of the record buffer of the temporary +table. To do this the method calls function fill_record. All needed type +conversions of the field values are performed when they are stored the record +buffer. After this the method select_union::send_data calls the ha_write_row +handler function to write the record from the buffer to the temporary table. A +possible error on duplicate key that occurs with an attempt to write a duplicate +row is ignored. +After all rows received from all selects have been placed into the temporary +table the method SELECT_LEX_UNIT::exec calls mysql_select that reads rows +from the temporary table and sends them to the output stream (to the client). If +there is an ORDER BY clause to be applied to result of the union unit then the +rows read from the temporary table have to be sorted first. + +2. Optimizations improving performance of UNION ALL operations +================================================= + +The following three optimizations are proposed to be implemented in the +framework of this task. + +2.1 Execution of UNION ALL without temporary table +------------------------------------------------------------------ + +If a union unit with only UNION ALL operations is used at the top level of the +query (in other words it's not used as a subquery) and is not appended with an +ORDER BY clause then it does not make sense to send rows received from selects +to a temporary table at all. After all needed type conversions have been done +the row fields could be sent directly into the output stream. It would improve +the performance of UNION ALL operations since writing to the temporary table and +reading from it would not be needed anymore. In the cases when the result set is +big enough and the temporary table cannot be allocated in the main memory the +performance gains would be significant. Besides, the client could get the first +result rows at once as it would not have to wait until all selects have been +executed. +To make an UNION ALL operation not to send rows to a temporary table we could +provide the JOIN objects created for the selects from the union unit with an +interceptor object that differs from the one they use now. In the current code +they use an object of the class select_union derived from the +select_result_interceptor class. The new interceptor object of the class that +we'll call select_union_send (by analogy with the class select_send) shall +inherit from the select_union and shall have its own implementations of the +virtual methods send_data, send_fields, and send_eof. +The method send_data shall send fields received from selects to the record +buffer of the temporary table and then from this buffer to the output stream. +The method send_fields shall send the format of the rows to the client before it +starts getting records from the first select , while the method send_eof shall +signal about the end of the rows after the last select finishes sending records. +The method create_result_table of the class select_union shall be re-defined +as virtual. The implementation of this method for the class select_union_send +shall call select_union::create_result_table and then shall build internal +structures needed for select_unionsend::send_data. So, the definition of the +class select_union_send should look like this: + class select_union_send :public select_union + { + ... // private structures + public: + select_union_send() :select_union(), ...{...} + bool send_data(List<Item> &items); + bool send_fields(List<Item> &list, uint flags); + bool create_result_table(THD *thd, List<Item> *column_types, + bool is_distinct, ulonglong options, + const char *alias); + }; + +2.2. Avoiding unnecessary copying +------------------------------------------ + +If a field does not need type conversion it does not make sense to send it to a +record buffer. It can be sent directly to the output stream. Different selects +can require type conversions for different columns. +Let's provide each select from the union unit with a data structure (e.g. a +bitmap) that says what fields require conversions, and what don't . Before +execution of a select this data structure must be passed to the +select_union_send object shared by all selects from the unit. The info in this +structure will tell select_union_send::send_data what fields should be sent to +the record buffer for type conversion and what can be sent directly to the +output stream. In this case another variant of the fill_record procedure is +needed that would take as parameter the info that says what fields are to be +stored in the record buffer. + +2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations +---------------------------------------------------------------------------------------------------------- + +If a union unit with a mix of UNIIN/UNION ALL operations and without ORDER BY is +used at the top level of a query then any UNION ALL operation after the last +UNION operation can be executed in more efficient way than it's done in the +current implementation. More exactly, the rows from any select that follows +after the second operand of the last UNION operations could be sent directly to +the output stream. In this case two interceptor objects have to be created: one, +of the type select_union, is shared by the selects for which UNION operations +are performed, another, of the type select_union_send, is shared by the the +remaining selects. For this optimization the method SELECT_LEX_UNIT::exec is to +undergo a serious re-work. + + +3. Other possible optimizations for union units +================================= + +The following optimizations are not supposed to be implemented in the framework +this task. +1. For a union unit containing only UNION ALL with an ORDER BY send rows from +selects directly to the sorting procedure. +2. For a union unit at the top level of the query without ORDER BY clause send +any row received from an operand of a UNION operation directly to the output +stream as soon as it has been checked by a lookup in the temporary table that +it's not a duplicate. +3. Not to use temporary table for any union unit used in EXIST or IN subquery. + DESCRIPTION: Currently when any union operation is executed the rows received from its operands are always sent to a temporary table. Meanwhile for a UNION ALL operation that is used at the top level of a query without an ORDER BY clause it is not necessary. In this case the rows could be sent directly to the client. The goal of this task is to provide such an implementation of UNION ALL operation that would not use temporary table at all in certain, most usable cases. HIGH-LEVEL SPECIFICATION: <contents> 1. Handling union operations in MySQL Server 1.1. Specifics of MySQL union operations 1.2 Validation of union units 1.3 Execution of union units 2. Optimizations improving performance of UNION ALL operations 2.1 Execution of UNION ALL without temporary table 2.2. Avoiding unnecessary copying 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations 3. Other possible optimizations for union units </contents> 1. Handling union operations in MySQL Server ================================== 1.1. Specifics of MySQL union operations ------------------------------------------------------ UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL allows us to use these operations in a sequence, one after another. For example the following queries are accepted by the MySQL Server: (select a1,b1,c1 from t1 where a1=b1) union (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (1) (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (2) Any mix of UNION and UNION ALL is also acceptable: (select a1,b1,c3 from t1 where a1=b1) union (select a2,b2,c3 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (3) (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (4) It should be noted that query (4) is equivalent to query (1). At the same time query (3) is not equivalent to any of the queries (1),(2),(4). In general any UNION ALL in a sequence of union operations can be equivalently substituted for UNION if there occur another UNION further in the sequence. MySQL does not accept nested unions. For example the following valid query is considered by MySQL Server as erroneous: ( (select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2) ) union all ( (select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4) ) A sequence of select constructs separated by UNION/UNION ALL is called 'union unit' if it s not a part of another such sequence. A union unit can be executed as a query. It also can be used as a subquery. A union unit can be optionally appended by an ORDER BY and/or LIMIT construct. In this case it cannot be used as a subquery. 1.2 Validation of union units ---------------------------------- When the parser stage is over the further processing of a union unit is performed by the function mysql_union. The function first validate the unit in the method SELECT_LEX_UNIT::prepare. The method first validates each of the select constructs of the unit and then it checks that all select are compatible. The method checks that the selects return the same number of columns and for each set of columns with the same number k there is a type to which the types of the columns can be coerced. This type is considered as the type of column k of the result set returned by the union unit. For example, if in the query (1) the columns b1, b2 and b3 are of the types int, bigint and double respectively then the second column of the union unit will be of the type double. If the types of the columns c1,c2,c3 are specified as varchar(10), varchar(20), varchar(10) then the type of the corresponding column of the result set will be varchar(20). If the columns have different collations then a collation from which all these collations can be derived is looked for and it is assigned as the collation of the third column in the result set. After compatibility of the corresponding select columns has been checked and the types of the columns from of the result set have been determined the method SELECT_LEX_UNIT::prepare creates a temporary table to store the rows of the result set for the union unit. Currently rows returned by the selects from the union unit are always written into a temporary table. To force selects to send rows to this temporary table SELECT_LEX_UNIT::prepare creates JOIN objects for the selects such that the JOIN::result field refers to an object of the class select_union. All selects from a union unit share the same select_union object. 1.3 Execution of union units ---------------------------------- After SELECT_LEX_UNIT::prepare has successfully validated the union unit, has created a temporary table as a container for rows from the result sets returned by the selects of the unit, and has prepared all data structures needed for execution, the function mysql_union invokes SELECT_LEX_UNIT::exec. The method SELECT_LEX_UNIT::exec processes the selects from the union unit one by one. Each select first is optimized with JOIN::optimize(), then it's executed with JOIN::exec().The result rows from each select are sent to a temporary table. This table accumulates all rows that are to be returned by the union unit. For UNION operations duplicate rows are not added, for UNION ALL operations all records are added. It is achieved by enabling and disabling usage of the unique index defined on all fields of the temporary table. The index is never used if only UINION ALL operation occurs in the unit. Otherwise it is enabled before the first select is executed and disabled after the last UNION operation. To send rows to the temporary table the method select_union::send_data is used. For a row it receives from the currently executed select the method first stores the fields of the row in in the fields of the record buffer of the temporary table. To do this the method calls function fill_record. All needed type conversions of the field values are performed when they are stored the record buffer. After this the method select_union::send_data calls the ha_write_row handler function to write the record from the buffer to the temporary table. A possible error on duplicate key that occurs with an attempt to write a duplicate row is ignored. After all rows received from all selects have been placed into the temporary table the method SELECT_LEX_UNIT::exec calls mysql_select that reads rows from the temporary table and sends them to the output stream (to the client). If there is an ORDER BY clause to be applied to result of the union unit then the rows read from the temporary table have to be sorted first. 2. Optimizations improving performance of UNION ALL operations ================================================= The following three optimizations are proposed to be implemented in the framework of this task. 2.1 Execution of UNION ALL without temporary table ------------------------------------------------------------------ If a union unit with only UNION ALL operations is used at the top level of the query (in other words it's not used as a subquery) and is not appended with an ORDER BY clause then it does not make sense to send rows received from selects to a temporary table at all. After all needed type conversions have been done the row fields could be sent directly into the output stream. It would improve the performance of UNION ALL operations since writing to the temporary table and reading from it would not be needed anymore. In the cases when the result set is big enough and the temporary table cannot be allocated in the main memory the performance gains would be significant. Besides, the client could get the first result rows at once as it would not have to wait until all selects have been executed. To make an UNION ALL operation not to send rows to a temporary table we could provide the JOIN objects created for the selects from the union unit with an interceptor object that differs from the one they use now. In the current code they use an object of the class select_union derived from the select_result_interceptor class. The new interceptor object of the class that we'll call select_union_send (by analogy with the class select_send) shall inherit from the select_union and shall have its own implementations of the virtual methods send_data, send_fields, and send_eof. The method send_data shall send fields received from selects to the record buffer of the temporary table and then from this buffer to the output stream. The method send_fields shall send the format of the rows to the client before it starts getting records from the first select , while the method send_eof shall signal about the end of the rows after the last select finishes sending records. The method create_result_table of the class select_union shall be re-defined as virtual. The implementation of this method for the class select_union_send shall call select_union::create_result_table and then shall build internal structures needed for select_unionsend::send_data. So, the definition of the class select_union_send should look like this: class select_union_send :public select_union { ... // private structures public: select_union_send() :select_union(), ...{...} bool send_data(List<Item> &items); bool send_fields(List<Item> &list, uint flags); bool create_result_table(THD *thd, List<Item> *column_types, bool is_distinct, ulonglong options, const char *alias); }; 2.2. Avoiding unnecessary copying ------------------------------------------ If a field does not need type conversion it does not make sense to send it to a record buffer. It can be sent directly to the output stream. Different selects can require type conversions for different columns. Let's provide each select from the union unit with a data structure (e.g. a bitmap) that says what fields require conversions, and what don't . Before execution of a select this data structure must be passed to the select_union_send object shared by all selects from the unit. The info in this structure will tell select_union_send::send_data what fields should be sent to the record buffer for type conversion and what can be sent directly to the output stream. In this case another variant of the fill_record procedure is needed that would take as parameter the info that says what fields are to be stored in the record buffer. 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations ---------------------------------------------------------------------------------------------------------- If a union unit with a mix of UNIIN/UNION ALL operations and without ORDER BY is used at the top level of a query then any UNION ALL operation after the last UNION operation can be executed in more efficient way than it's done in the current implementation. More exactly, the rows from any select that follows after the second operand of the last UNION operations could be sent directly to the output stream. In this case two interceptor objects have to be created: one, of the type select_union, is shared by the selects for which UNION operations are performed, another, of the type select_union_send, is shared by the the remaining selects. For this optimization the method SELECT_LEX_UNIT::exec is to undergo a serious re-work. 3. Other possible optimizations for union units ================================= The following optimizations are not supposed to be implemented in the framework this task. 1. For a union unit containing only UNION ALL with an ORDER BY send rows from selects directly to the sorting procedure. 2. For a union unit at the top level of the query without ORDER BY clause send any row received from an operand of a UNION operation directly to the output stream as soon as it has been checked by a lookup in the temporary table that it's not a duplicate. 3. Not to use temporary table for any union unit used in EXIST or IN subquery. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Igor): Implement UNION ALL without usage of a temporary table (44)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Implement UNION ALL without usage of a temporary table CREATION DATE..: Fri, 14 Aug 2009, 08:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: Monty, Psergey CATEGORY.......: Client-BackLog TASK ID........: 44 (http://askmonty.org/worklog/?tid=44) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Currently when any union operation is executed the rows received from its operands are always sent to a temporary table. Meanwhile for a UNION ALL operation that is used at the top level of a query without an ORDER BY clause it is not necessary. In this case the rows could be sent directly to the client. The goal of this task is to provide such an implementation of UNION ALL operation that would not use temporary table at all in certain, most usable cases. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Igor): Implement UNION ALL without usage of a temporary table (44)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Implement UNION ALL without usage of a temporary table CREATION DATE..: Fri, 14 Aug 2009, 08:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: Monty, Psergey CATEGORY.......: Client-BackLog TASK ID........: 44 (http://askmonty.org/worklog/?tid=44) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Currently when any union operation is executed the rows received from its operands are always sent to a temporary table. Meanwhile for a UNION ALL operation that is used at the top level of a query without an ORDER BY clause it is not necessary. In this case the rows could be sent directly to the client. The goal of this task is to provide such an implementation of UNION ALL operation that would not use temporary table at all in certain, most usable cases. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Igor): Implement UNION ALL without usage of a temporary table (44)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Implement UNION ALL without usage of a temporary table CREATION DATE..: Fri, 14 Aug 2009, 08:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: Monty, Psergey CATEGORY.......: Client-BackLog TASK ID........: 44 (http://askmonty.org/worklog/?tid=44) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Currently when any union operation is executed the rows received from its operands are always sent to a temporary table. Meanwhile for a UNION ALL operation that is used at the top level of a query without an ORDER BY clause it is not necessary. In this case the rows could be sent directly to the client. The goal of this task is to provide such an implementation of UNION ALL operation that would not use temporary table at all in certain, most usable cases. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Igor): Implement UNION ALL without usage of a temporary table (44)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Implement UNION ALL without usage of a temporary table CREATION DATE..: Fri, 14 Aug 2009, 08:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: Monty, Psergey CATEGORY.......: Client-BackLog TASK ID........: 44 (http://askmonty.org/worklog/?tid=44) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Currently when any union operation is executed the rows received from its operands are always sent to a temporary table. Meanwhile for a UNION ALL operation that is used at the top level of a query without an ORDER BY clause it is not necessary. In this case the rows could be sent directly to the client. The goal of this task is to provide such an implementation of UNION ALL operation that would not use temporary table at all in certain, most usable cases. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Rev 2720: Merge maria-5.1 -> maria-5.1-table-elimination in file:///home/psergey/dev/maria-5.1-table-elim-r10/
by Sergey Petrunya 13 Aug '09

13 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r10/ ------------------------------------------------------------ revno: 2720 revision-id: psergey(a)askmonty.org-20090813211212-jghejwxsl6adtopl parent: knielsen(a)knielsen-hq.org-20090805072137-wg97dcem1cxnzt3p parent: psergey(a)askmonty.org-20090813204452-o8whzlbio19cgkyv committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r10 timestamp: Fri 2009-08-14 01:12:12 +0400 message: Merge maria-5.1 -> maria-5.1-table-elimination added: mysql-test/r/table_elim.result table_elim.result-20090603125022-nge13y0ohk1g2tt2-1 mysql-test/t/table_elim.test table_elim.test-20090603125018-ka3vcfrm07bsldz8-1 sql-bench/test-table-elimination.sh testtableelimination-20090616194329-gai92muve732qknl-1 sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 modified: .bzrignore sp1f-ignore-20001018235455-q4gxfbritt5f42nwix354ufpsvrf5ebj libmysqld/Makefile.am sp1f-makefile.am-20010411110351-26htpk3ynkyh7pkfvnshztqrxx3few4g mysql-test/r/mysql-bug41486.result mysqlbug41486.result-20090323135900-fobg67a3yzg0b7e8-1 mysql-test/r/ps_11bugs.result sp1f-ps_11bugs.result-20041012140047-4pktjlfeq27q6bxqfdsbcszr5nybv6zz mysql-test/r/select.result sp1f-select.result-20010103001548-znkoalxem6wchsbxizfosjhpfmhfyxuk mysql-test/r/subselect.result sp1f-subselect.result-20020512204640-zgegcsgavnfd7t7eyrf7ibuqomsw7uzo mysql-test/r/union.result sp1f-unions_one.result-20010725122836-ofxtwraxeohz7whhrmfdz57sl4a5prmp mysql-test/t/mysql-bug41486.test mysqlbug41486.test-20090323135900-fobg67a3yzg0b7e8-2 mysql-test/valgrind.supp sp1f-valgrind.supp-20050406142216-yg7xhezklqhgqlc3inx36vbghodhbovy sql/CMakeLists.txt sp1f-cmakelists.txt-20060831175237-esoeu5kpdtwjvehkghwy6fzbleniq2wy sql/Makefile.am sp1f-makefile.am-19700101030959-xsjdiakci3nqcdd4xl4yomwdl5eo2f3q sql/item.cc sp1f-item.cc-19700101030959-u7hxqopwpfly4kf5ctlyk2dvrq4l3dhn sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/item_subselect.cc sp1f-item_subselect.cc-20020512204640-qep43aqhsfrwkqmrobni6czc3fqj36oo sql/item_subselect.h sp1f-item_subselect.h-20020512204640-qdg77wil56cxyhtc2bjjdrppxq3wqgh3 sql/item_sum.cc sp1f-item_sum.cc-19700101030959-4woo23bi3am2t2zvsddqbpxk7xbttdkm sql/item_sum.h sp1f-item_sum.h-19700101030959-ecgohlekwm355wxl5fv4zzq3alalbwyl sql/sql_bitmap.h sp1f-sql_bitmap.h-20031024204444-g4eiad7vopzqxe2trxmt3fn3xsvnomvj sql/sql_lex.cc sp1f-sql_lex.cc-19700101030959-4pizwlu5rqkti27gcwsvxkawq6bc2kph sql/sql_lex.h sp1f-sql_lex.h-19700101030959-sgldb2sooc7twtw5q7pgjx7qzqiaa3sn sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz sql/table.h sp1f-table.h-19700101030959-dv72bajftxj5fbdjuajquappanuv2ija ------------------------------------------------------------ revno: 2707.1.27 revision-id: psergey(a)askmonty.org-20090813204452-o8whzlbio19cgkyv parent: psergey(a)askmonty.org-20090813191053-g1xfeieoti4bqgbc committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Fri 2009-08-14 00:44:52 +0400 message: MWL#17: Table elimination - More function renames, added comments modified: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 ------------------------------------------------------------ revno: 2707.1.26 revision-id: psergey(a)askmonty.org-20090813191053-g1xfeieoti4bqgbc parent: psergey(a)askmonty.org-20090813093613-hy7tdlsgdy83xszq committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 23:10:53 +0400 message: MWL#17: Table elimination - Better comments modified: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.25 revision-id: psergey(a)askmonty.org-20090813093613-hy7tdlsgdy83xszq parent: psergey(a)askmonty.org-20090813092402-jlqucf6nultxlv4b committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 13:36:13 +0400 message: MWL#17: Table elimination Fixes after post-review fixes: - Don't search for tables in JOIN_TAB array. it's not initialized yet. use select_lex->leaf_tables instead. modified: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 ------------------------------------------------------------ revno: 2707.1.24 revision-id: psergey(a)askmonty.org-20090813092402-jlqucf6nultxlv4b parent: psergey(a)askmonty.org-20090813000143-dukzk352hjywidk7 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 13:24:02 +0400 message: MWL#17: Table elimination - Post-postreview changes fix: Do set NESTED_JOIN::n_tables to number of tables left after elimination. modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.23 revision-id: psergey(a)askmonty.org-20090813000143-dukzk352hjywidk7 parent: psergey(a)askmonty.org-20090812234302-10es7qmf0m09ahbq committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 04:01:43 +0400 message: MWL#17: Table elimination - When making inferences "field is bound" -> "key is bound", do check that the field is part of the key modified: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 ------------------------------------------------------------ revno: 2707.1.22 revision-id: psergey(a)askmonty.org-20090812234302-10es7qmf0m09ahbq parent: psergey(a)askmonty.org-20090812223421-w4xyzj7azqgo83ps committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 03:43:02 +0400 message: MWL#17: Table elimination - Continue addressing review feedback: remove "unusable KEYUSEs" extension as it is no longer needed. modified: sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz ------------------------------------------------------------ revno: 2707.1.21 revision-id: psergey(a)askmonty.org-20090812223421-w4xyzj7azqgo83ps parent: psergey(a)askmonty.org-20090708171038-9nyc3hcg1o7h8635 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 02:34:21 +0400 message: MWL#17: Table elimination Address review feedback: - Change from Wave-based approach (a-la const table detection) to building and walking functional dependency graph. - Change from piggy-backing on ref-access code and KEYUSE structures to using our own expression analyzer. modified: sql/item.cc sp1f-item.cc-19700101030959-u7hxqopwpfly4kf5ctlyk2dvrq4l3dhn sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 sql/sql_bitmap.h sp1f-sql_bitmap.h-20031024204444-g4eiad7vopzqxe2trxmt3fn3xsvnomvj ------------------------------------------------------------ revno: 2707.1.20 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: sql/sql_lex.cc sp1f-sql_lex.cc-19700101030959-4pizwlu5rqkti27gcwsvxkawq6bc2kph ------------------------------------------------------------ revno: 2707.1.19 revision-id: psergey(a)askmonty.org-20090630132018-8qwou8bqiq5z1qjg parent: psergey(a)askmonty.org-20090630131100-r6o8yqzse4yvny9l committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Tue 2009-06-30 17:20:18 +0400 message: MWL#17: Table elimination - More comments - Renove old code modified: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 ------------------------------------------------------------ revno: 2707.1.18 revision-id: psergey(a)askmonty.org-20090630131100-r6o8yqzse4yvny9l parent: psergey(a)askmonty.org-20090629135115-472up9wsj0dq843i committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Tue 2009-06-30 17:11:00 +0400 message: MWL#17: Table elimination - Last fixes modified: sql/item.cc sp1f-item.cc-19700101030959-u7hxqopwpfly4kf5ctlyk2dvrq4l3dhn sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz sql/table.h sp1f-table.h-19700101030959-dv72bajftxj5fbdjuajquappanuv2ija ------------------------------------------------------------ revno: 2707.1.17 revision-id: psergey(a)askmonty.org-20090629135115-472up9wsj0dq843i parent: psergey(a)askmonty.org-20090625200729-u11xpwwn5ebddx09 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Mon 2009-06-29 17:51:15 +0400 message: MWL#17: Table elimination modified: mysql-test/r/table_elim.result table_elim.result-20090603125022-nge13y0ohk1g2tt2-1 mysql-test/t/table_elim.test table_elim.test-20090603125018-ka3vcfrm07bsldz8-1 sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz sql/table.h sp1f-table.h-19700101030959-dv72bajftxj5fbdjuajquappanuv2ija ------------------------------------------------------------ revno: 2707.1.16 revision-id: psergey(a)askmonty.org-20090625200729-u11xpwwn5ebddx09 parent: psergey(a)askmonty.org-20090625100947-mg9xwnbeyyjgzl3w committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-movearound timestamp: Fri 2009-06-26 00:07:29 +0400 message: MWL#17: Table elimination - Better comments, variable/function renames modified: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz ------------------------------------------------------------ revno: 2707.1.15 revision-id: psergey(a)askmonty.org-20090625100947-mg9xwnbeyyjgzl3w parent: psergey(a)askmonty.org-20090624224414-71xqbljy8jf4z1qs parent: psergey(a)askmonty.org-20090625100553-j1xenbz3o5nekiu2 committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Thu 2009-06-25 14:09:47 +0400 message: Automerge added: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 modified: .bzrignore sp1f-ignore-20001018235455-q4gxfbritt5f42nwix354ufpsvrf5ebj libmysqld/Makefile.am sp1f-makefile.am-20010411110351-26htpk3ynkyh7pkfvnshztqrxx3few4g sql/CMakeLists.txt sp1f-cmakelists.txt-20060831175237-esoeu5kpdtwjvehkghwy6fzbleniq2wy sql/Makefile.am sp1f-makefile.am-19700101030959-xsjdiakci3nqcdd4xl4yomwdl5eo2f3q sql/item.cc sp1f-item.cc-19700101030959-u7hxqopwpfly4kf5ctlyk2dvrq4l3dhn sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/item_subselect.cc sp1f-item_subselect.cc-20020512204640-qep43aqhsfrwkqmrobni6czc3fqj36oo sql/item_sum.h sp1f-item_sum.h-19700101030959-ecgohlekwm355wxl5fv4zzq3alalbwyl sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz ------------------------------------------------------------ revno: 2707.3.1 revision-id: psergey(a)askmonty.org-20090625100553-j1xenbz3o5nekiu2 parent: psergey(a)askmonty.org-20090624090104-c63mp3sfxcxytk0d committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-movearound timestamp: Thu 2009-06-25 14:05:53 +0400 message: MWL#17: Table elimination - Moved table elimination code to sql/opt_table_elimination.cc - Added comments added: sql/opt_table_elimination.cc opt_table_eliminatio-20090625095316-7ka9w3zr7n5114iv-1 modified: .bzrignore sp1f-ignore-20001018235455-q4gxfbritt5f42nwix354ufpsvrf5ebj libmysqld/Makefile.am sp1f-makefile.am-20010411110351-26htpk3ynkyh7pkfvnshztqrxx3few4g sql/CMakeLists.txt sp1f-cmakelists.txt-20060831175237-esoeu5kpdtwjvehkghwy6fzbleniq2wy sql/Makefile.am sp1f-makefile.am-19700101030959-xsjdiakci3nqcdd4xl4yomwdl5eo2f3q sql/item.cc sp1f-item.cc-19700101030959-u7hxqopwpfly4kf5ctlyk2dvrq4l3dhn sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/item_subselect.cc sp1f-item_subselect.cc-20020512204640-qep43aqhsfrwkqmrobni6czc3fqj36oo sql/item_sum.h sp1f-item_sum.h-19700101030959-ecgohlekwm355wxl5fv4zzq3alalbwyl sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz ------------------------------------------------------------ revno: 2707.1.14 revision-id: psergey(a)askmonty.org-20090624224414-71xqbljy8jf4z1qs parent: psergey(a)askmonty.org-20090624090104-c63mp3sfxcxytk0d committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Thu 2009-06-25 02:44:14 +0400 message: MWL#17: Table elimination - fix a typo bug in has_eqref_access_candidate() - Adjust test to remove race condition modified: mysql-test/r/mysql-bug41486.result mysqlbug41486.result-20090323135900-fobg67a3yzg0b7e8-1 mysql-test/t/mysql-bug41486.test mysqlbug41486.test-20090323135900-fobg67a3yzg0b7e8-2 sql/item.cc sp1f-item.cc-19700101030959-u7hxqopwpfly4kf5ctlyk2dvrq4l3dhn ------------------------------------------------------------ revno: 2707.1.13 revision-id: psergey(a)askmonty.org-20090624090104-c63mp3sfxcxytk0d parent: psergey(a)askmonty.org-20090623200613-w9dl8g41ysf51r80 committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Wed 2009-06-24 13:01:04 +0400 message: More comments modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.12 revision-id: psergey(a)askmonty.org-20090623200613-w9dl8g41ysf51r80 parent: psergey(a)askmonty.org-20090622114631-yop0q2p8ktmfnctm committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Wed 2009-06-24 00:06:13 +0400 message: MWL#17: Table elimination - More testcases - Let add_ft_key() set keyuse->usable modified: mysql-test/r/table_elim.result table_elim.result-20090603125022-nge13y0ohk1g2tt2-1 mysql-test/t/table_elim.test table_elim.test-20090603125018-ka3vcfrm07bsldz8-1 sql-bench/test-table-elimination.sh testtableelimination-20090616194329-gai92muve732qknl-1 sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.11 revision-id: psergey(a)askmonty.org-20090622114631-yop0q2p8ktmfnctm parent: psergey(a)askmonty.org-20090617052739-37i1r8lip0m4ft9r committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Mon 2009-06-22 15:46:31 +0400 message: MWL#17: Table elimination - Make elimination check to be able detect cases like t.primary_key_col1=othertbl.col AND t.primary_key_col2=func(t.primary_key_col1). These are needed to handle e.g. the case of func() being a correlated subquery that selects the latest value. - If we've removed a condition with subquery predicate, EXPLAIN [EXTENDED] won't show the subquery anymore modified: sql/item.cc sp1f-item.cc-19700101030959-u7hxqopwpfly4kf5ctlyk2dvrq4l3dhn sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/item_subselect.cc sp1f-item_subselect.cc-20020512204640-qep43aqhsfrwkqmrobni6czc3fqj36oo sql/item_subselect.h sp1f-item_subselect.h-20020512204640-qdg77wil56cxyhtc2bjjdrppxq3wqgh3 sql/item_sum.cc sp1f-item_sum.cc-19700101030959-4woo23bi3am2t2zvsddqbpxk7xbttdkm sql/sql_lex.cc sp1f-sql_lex.cc-19700101030959-4pizwlu5rqkti27gcwsvxkawq6bc2kph sql/sql_lex.h sp1f-sql_lex.h-19700101030959-sgldb2sooc7twtw5q7pgjx7qzqiaa3sn sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz ------------------------------------------------------------ revno: 2707.1.10 revision-id: psergey(a)askmonty.org-20090617052739-37i1r8lip0m4ft9r parent: psergey(a)askmonty.org-20090616204358-yjkyfxczsomrn9yn committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Wed 2009-06-17 09:27:39 +0400 message: * Use excessive parentheses to stop compiler warning * Fix test results to account for changes in previous cset modified: mysql-test/r/select.result sp1f-select.result-20010103001548-znkoalxem6wchsbxizfosjhpfmhfyxuk sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.9 revision-id: psergey(a)askmonty.org-20090616204358-yjkyfxczsomrn9yn parent: psergey(a)askmonty.org-20090616195413-rfmi9un20za8gn8g parent: psergey(a)askmonty.org-20090615162208-p4w8s8jo06bdz1vj committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Wed 2009-06-17 00:43:58 +0400 message: * Merge * Change valgrind suppression to work on valgrind 3.3.0 modified: mysql-test/valgrind.supp sp1f-valgrind.supp-20050406142216-yg7xhezklqhgqlc3inx36vbghodhbovy ------------------------------------------------------------ revno: 2707.2.1 revision-id: psergey(a)askmonty.org-20090615162208-p4w8s8jo06bdz1vj parent: psergey(a)askmonty.org-20090614205924-1vnfwbuo4brzyfhp committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-movearound timestamp: Mon 2009-06-15 20:22:08 +0400 message: Fix spurious valgrind warnings in rpl_trigger.test modified: mysql-test/valgrind.supp sp1f-valgrind.supp-20050406142216-yg7xhezklqhgqlc3inx36vbghodhbovy ------------------------------------------------------------ revno: 2707.1.8 revision-id: psergey(a)askmonty.org-20090616195413-rfmi9un20za8gn8g parent: psergey(a)askmonty.org-20090614205924-1vnfwbuo4brzyfhp committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Tue 2009-06-16 23:54:13 +0400 message: MWL#17: Table elimination - Move eliminate_tables() to before constant table detection. - First code for benchmark added: sql-bench/test-table-elimination.sh testtableelimination-20090616194329-gai92muve732qknl-1 modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.7 revision-id: psergey(a)askmonty.org-20090614205924-1vnfwbuo4brzyfhp parent: psergey(a)askmonty.org-20090614123504-jf4pcb333ojwaxfy committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Mon 2009-06-15 00:59:24 +0400 message: MWL#17: Table elimination - Fix print_join() to work both for EXPLAIN EXTENDED (after table elimination) and for CREATE VIEW (after join->prepare() but without any optimization). modified: mysql-test/r/union.result sp1f-unions_one.result-20010725122836-ofxtwraxeohz7whhrmfdz57sl4a5prmp sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.6 revision-id: psergey(a)askmonty.org-20090614123504-jf4pcb333ojwaxfy parent: psergey(a)askmonty.org-20090614100110-u7l54gk0b6zbtj50 committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Sun 2009-06-14 16:35:04 +0400 message: MWL#17: Table elimination - Fix the previous cset: take into account that select_lex may be printed when 1. There is no select_lex->join at all (in that case, assume that no tables were eliminated) 2. select_lex->join exists but there was no JOIN::optimize() call yet. handle this by initializing join->eliminated really early. modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz ------------------------------------------------------------ revno: 2707.1.5 revision-id: psergey(a)askmonty.org-20090614100110-u7l54gk0b6zbtj50 parent: psergey(a)askmonty.org-20090609211133-wfau2tgwo2vpgc5d committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Sun 2009-06-14 14:01:10 +0400 message: MWL#17: Table elimination - Do not show eliminated tables in the output of EXPLAIN EXTENDED modified: mysql-test/r/table_elim.result table_elim.result-20090603125022-nge13y0ohk1g2tt2-1 mysql-test/t/table_elim.test table_elim.test-20090603125018-ka3vcfrm07bsldz8-1 sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz sql/table.h sp1f-table.h-19700101030959-dv72bajftxj5fbdjuajquappanuv2ija ------------------------------------------------------------ revno: 2707.1.4 revision-id: psergey(a)askmonty.org-20090609211133-wfau2tgwo2vpgc5d parent: psergey(a)askmonty.org-20090608135546-ut1yrzbah4gdw6e6 committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Wed 2009-06-10 01:11:33 +0400 message: MWL#17: Table elimination - Make elimination work with aggregate functions. The problem was that aggregate functions reported all table bits in used_tables(), and that prevented table elimination. Fixed by making aggregate functions return more correct value from used_tables(). modified: mysql-test/r/ps_11bugs.result sp1f-ps_11bugs.result-20041012140047-4pktjlfeq27q6bxqfdsbcszr5nybv6zz mysql-test/r/subselect.result sp1f-subselect.result-20020512204640-zgegcsgavnfd7t7eyrf7ibuqomsw7uzo mysql-test/r/table_elim.result table_elim.result-20090603125022-nge13y0ohk1g2tt2-1 mysql-test/t/table_elim.test table_elim.test-20090603125018-ka3vcfrm07bsldz8-1 sql/item.h sp1f-item.h-19700101030959-rrkb43htudd62batmoteashkebcwykpa sql/item_sum.cc sp1f-item_sum.cc-19700101030959-4woo23bi3am2t2zvsddqbpxk7xbttdkm sql/item_sum.h sp1f-item_sum.h-19700101030959-ecgohlekwm355wxl5fv4zzq3alalbwyl ------------------------------------------------------------ revno: 2707.1.3 revision-id: psergey(a)askmonty.org-20090608135546-ut1yrzbah4gdw6e6 parent: psergey(a)askmonty.org-20090607182938-ycajee5ozg33b7c8 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-fix timestamp: Mon 2009-06-08 17:55:46 +0400 message: Fix valgrind failure: provide an implementation of strmov_overlapp() that really can handle overlapping. added: strings/strmov_overlapp.c strmov_overlapp.c-20090608135132-403c5p4dlnexqwxi-1 modified: include/m_string.h sp1f-m_string.h-19700101030959-rraattbvw5ffkokv4sixxf3s7brqqaga libmysql/Makefile.shared sp1f-makefile.shared-20000818182429-m3kdhxi23vorlqjct2y2hl3yw357jtxt strings/Makefile.am sp1f-makefile.am-19700101030959-jfitkanzc3r4h2otoyaaprgqn7muf4ux ------------------------------------------------------------ revno: 2707.1.2 revision-id: psergey(a)askmonty.org-20090607182938-ycajee5ozg33b7c8 parent: psergey(a)askmonty.org-20090603182330-ll3gc91iowhtgb23 parent: psergey(a)askmonty.org-20090607182403-6sfpvdr7nkkekcy9 committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1 timestamp: Sun 2009-06-07 22:29:38 +0400 message: Merge MWL#17: Table elimination modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2705.2.2 revision-id: psergey(a)askmonty.org-20090607182403-6sfpvdr7nkkekcy9 parent: psergey(a)askmonty.org-20090603131045-c8jqhwlanli7eimv committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Sun 2009-06-07 22:24:03 +0400 message: MWL#17: Table Elimination - Fix trivial valgrind warning modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb ------------------------------------------------------------ revno: 2707.1.1 revision-id: psergey(a)askmonty.org-20090603182330-ll3gc91iowhtgb23 parent: knielsen(a)knielsen-hq.org-20090602110359-n4q9gof38buucrny parent: psergey(a)askmonty.org-20090603131045-c8jqhwlanli7eimv committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1 timestamp: Wed 2009-06-03 22:23:30 +0400 message: Merge MWL#17 with maria/5.1 added: mysql-test/r/table_elim.result table_elim.result-20090603125022-nge13y0ohk1g2tt2-1 mysql-test/t/table_elim.test table_elim.test-20090603125018-ka3vcfrm07bsldz8-1 modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz sql/table.h sp1f-table.h-19700101030959-dv72bajftxj5fbdjuajquappanuv2ija ------------------------------------------------------------ revno: 2705.2.1 revision-id: psergey(a)askmonty.org-20090603131045-c8jqhwlanli7eimv parent: knielsen(a)knielsen-hq.org-20090522175325-xpwm83ilnhqoqjz0 committer: Sergey Petrunia <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim timestamp: Wed 2009-06-03 17:10:45 +0400 message: MWL#17: Table elimination - First code. Elimination works for simple cases, passes the testsuite. - Known issues: = No elimination is done for aggregate functions. = EXPLAIN EXTENDED shows eliminated tables (I think it better not) = No benchmark yet = The code needs some polishing. added: mysql-test/r/table_elim.result table_elim.result-20090603125022-nge13y0ohk1g2tt2-1 mysql-test/t/table_elim.test table_elim.test-20090603125018-ka3vcfrm07bsldz8-1 modified: sql/sql_select.cc sp1f-sql_select.cc-19700101030959-egb7whpkh76zzvikycs5nsnuviu4fdlb sql/sql_select.h sp1f-sql_select.h-19700101030959-oqegfxr76xlgmrzd6qlevonoibfnwzoz sql/table.h sp1f-table.h-19700101030959-dv72bajftxj5fbdjuajquappanuv2ija Diff too large for email (3022 lines, the limit is 1000).

1 0

[Maria-developers] Rev 2734: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r5/
by Sergey Petrunya 13 Aug '09

13 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r5/ ------------------------------------------------------------ revno: 2734 revision-id: psergey(a)askmonty.org-20090813204452-o8whzlbio19cgkyv parent: psergey(a)askmonty.org-20090813191053-g1xfeieoti4bqgbc committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Fri 2009-08-14 00:44:52 +0400 message: MWL#17: Table elimination - More function renames, added comments === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-13 19:10:53 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-13 20:44:52 +0000 @@ -93,11 +93,9 @@ /* - A field. - - Depends on table or equality - - Has expressions it participates as dependencies - - There is no counter, bound fields are in $list, not bound are not. + A table field. There is only one such object for any tblX.fieldY + - the field epends on its table and equalities + - expressions that use the field are its dependencies */ class Field_dep : public Func_dep { @@ -107,19 +105,23 @@ { type= Func_dep::FD_FIELD; } - /* Table we're from. It also has pointers to keys that we're part of */ - Table_dep *table; + + Table_dep *table; /* Table this field is from */ Field *field; + /* + Field_deps that belong to one table form a linked list. list members are + ordered by field_index + */ Field_dep *next_table_field; uint bitmap_offset; /* Offset of our part of the bitmap */ }; /* - A unique key. - - Depends on all its components - - Has its table as dependency + A Unique key. + - Unique key depends on all of its components + - Key's table is its dependency */ class Key_dep: public Func_dep { @@ -133,14 +135,15 @@ Table_dep *table; /* Table this key is from */ uint keyno; uint n_missing_keyparts; + /* Unique keys form a linked list, ordered by keyno */ Key_dep *next_table_key; }; /* - A table. - - Depends on any of its unique keys - - Has its fields and embedding outer join as dependency. + A table. + - table depends on any of its unique keys + - has its fields and embedding outer join as dependency. */ class Table_dep : public Func_dep { @@ -151,16 +154,16 @@ type= Func_dep::FD_TABLE; } TABLE *table; - Field_dep *fields; /* Fields that belong to this table */ - Key_dep *keys; /* Unique keys */ - Outer_join_dep *outer_join_dep; + Field_dep *fields; /* Ordered list of fields that belong to this table */ + Key_dep *keys; /* Ordered list of Unique keys in this table */ + Outer_join_dep *outer_join_dep; /* Innermost eliminable outer join we're in */ }; /* - An outer join nest. - - Depends on all tables inside it. - - (And that's it). + An outer join nest that is subject to elimination + - it depends on all tables inside it + - has its parent outer join as dependency */ class Outer_join_dep: public Func_dep { @@ -171,14 +174,27 @@ { type= Func_dep::FD_OUTER_JOIN; } + /* + Outer join we're representing. This can be a join nest or a one table that + is outer join'ed. + */ TABLE_LIST *table_list; + + /* + Tables within this outer join (and its descendants) that are not yet known + to be functionally dependent. + */ table_map missing_tables; + /* All tables within this outer join and its descendants */ table_map all_tables; + /* Parent eliminable outer join, if any */ Outer_join_dep *parent; }; -/* TODO need this? */ +/* + Table elimination context +*/ class Table_elimination { public: @@ -204,20 +220,22 @@ static -void build_funcdeps_for_cond(Table_elimination *te, Equality_dep **fdeps, - uint *and_level, Item *cond, - table_map usable_tables); +void build_eq_deps_for_cond(Table_elimination *te, Equality_dep **fdeps, + uint *and_level, Item *cond, + table_map usable_tables); static -void add_funcdep(Table_elimination *te, - Equality_dep **eq_dep, uint and_level, - Item_func *cond, Field *field, - bool eq_func, Item **value, - uint num_values, table_map usable_tables); +void add_eq_dep(Table_elimination *te, + Equality_dep **eq_dep, uint and_level, + Item_func *cond, Field *field, + bool eq_func, Item **value, + uint num_values, table_map usable_tables); static Equality_dep *merge_func_deps(Equality_dep *start, Equality_dep *new_fields, Equality_dep *end, uint and_level); -Field_dep *get_field_dep(Table_elimination *te, Field *field); +static Table_dep *get_table_dep(Table_elimination *te, TABLE *table); +static Field_dep *get_field_dep(Table_elimination *te, Field *field); + void eliminate_tables(JOIN *join); static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl); @@ -228,24 +246,25 @@ /*******************************************************************************************/ /* - Produce FUNC_DEP elements for the given item (i.e. condition) and add them - to fdeps array. + Produce Eq_dep elements for given condition. SYNOPSIS - build_funcdeps_for_cond() - fdeps INOUT Put created FUNC_DEP structures here - + build_eq_deps_for_cond() + te Table elimination context + fdeps INOUT Put produced equality conditions here + and_level INOUT AND-level (like in add_key_fields) + cond Condition to process + usable_tables Tables which fields we're interested in. That is, + Equality_dep represent "tbl.col=expr" and we'll + produce them only if tbl is in usable_tables. DESCRIPTION - a - - SEE ALSO - add_key_fields() - + This function is modeled after add_key_fields() */ + static -void build_funcdeps_for_cond(Table_elimination *te, - Equality_dep **fdeps, uint *and_level, Item *cond, - table_map usable_tables) +void build_eq_deps_for_cond(Table_elimination *te, Equality_dep **fdeps, + uint *and_level, Item *cond, + table_map usable_tables) { if (cond->type() == Item_func::COND_ITEM) { @@ -258,7 +277,7 @@ Item *item; while ((item=li++)) { - build_funcdeps_for_cond(te, fdeps, and_level, item, usable_tables); + build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables); } /* TODO: inject here a "if we have {t.col=const AND t.col=smth_else}, then @@ -270,13 +289,13 @@ else { (*and_level)++; - build_funcdeps_for_cond(te, fdeps, and_level, li++, usable_tables); + build_eq_deps_for_cond(te, fdeps, and_level, li++, usable_tables); Item *item; while ((item=li++)) { Equality_dep *start_key_fields= *fdeps; (*and_level)++; - build_funcdeps_for_cond(te, fdeps, and_level, item, usable_tables); + build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables); *fdeps= merge_func_deps(org_key_fields, start_key_fields, *fdeps, ++(*and_level)); } @@ -304,11 +323,11 @@ values--; DBUG_ASSERT(cond_func->functype() != Item_func::IN_FUNC || cond_func->argument_count() != 2); - add_funcdep(te, fdeps, *and_level, cond_func, - ((Item_field*)(cond_func->key_item()->real_item()))->field, - 0, values, - cond_func->argument_count()-1, - usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, + ((Item_field*)(cond_func->key_item()->real_item()))->field, + 0, values, + cond_func->argument_count()-1, + usable_tables); } if (cond_func->functype() == Item_func::BETWEEN) { @@ -321,8 +340,8 @@ !(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT)) { field_item= (Item_field *) (cond_func->arguments()[i]->real_item()); - add_funcdep(te, fdeps, *and_level, cond_func, - field_item->field, 0, values, 1, usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, + field_item->field, 0, values, 1, usable_tables); } } } @@ -336,19 +355,19 @@ if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM && !(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT)) { - add_funcdep(te, fdeps, *and_level, cond_func, - ((Item_field*)(cond_func->arguments()[0])->real_item())->field, - equal_func, - cond_func->arguments()+1, 1, usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, + ((Item_field*)(cond_func->arguments()[0])->real_item())->field, + equal_func, + cond_func->arguments()+1, 1, usable_tables); } if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM && cond_func->functype() != Item_func::LIKE_FUNC && !(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT)) { - add_funcdep(te, fdeps, *and_level, cond_func, - ((Item_field*)(cond_func->arguments()[1])->real_item())->field, - equal_func, - cond_func->arguments(),1,usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, + ((Item_field*)(cond_func->arguments()[1])->real_item())->field, + equal_func, + cond_func->arguments(),1,usable_tables); } break; } @@ -360,10 +379,10 @@ Item *tmp=new Item_null; if (unlikely(!tmp)) // Should never be true return; - add_funcdep(te, fdeps, *and_level, cond_func, - ((Item_field*)(cond_func->arguments()[0])->real_item())->field, - cond_func->functype() == Item_func::ISNULL_FUNC, - &tmp, 1, usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, + ((Item_field*)(cond_func->arguments()[0])->real_item())->field, + cond_func->functype() == Item_func::ISNULL_FUNC, + &tmp, 1, usable_tables); } break; case Item_func::OPTIMIZE_EQUAL: @@ -380,8 +399,8 @@ */ while ((item= it++)) { - add_funcdep(te, fdeps, *and_level, cond_func, item->field, - TRUE, &const_item, 1, usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, item->field, + TRUE, &const_item, 1, usable_tables); } } else @@ -400,8 +419,8 @@ { if (!field->eq(item->field)) { - add_funcdep(te, fdeps, *and_level, cond_func, field/*item*/, - TRUE, (Item **) &item, 1, usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, field, + TRUE, (Item **) &item, 1, usable_tables); } } it.rewind(); @@ -411,15 +430,19 @@ } } + /* - Perform an OR operation on two (adjacent) FUNC_DEP arrays. + Perform an OR operation on two (adjacent) Equality_dep arrays. SYNOPSIS merge_func_deps() + start Start of left OR-part + new_fields Start of right OR-part + end End of right OR-part + and_level AND-level. DESCRIPTION - - This function is invoked for two adjacent arrays of FUNC_DEP elements: + This function is invoked for two adjacent arrays of Equality_dep elements: $LEFT_PART $RIGHT_PART +-----------------------+-----------------------+ @@ -527,17 +550,18 @@ /* - Add a funcdep for a given equality. + Add an Equality_dep element for a given predicate, if applicable + + DESCRIPTION + This function is modeled after add_key_field(). */ static -void add_funcdep(Table_elimination *te, - Equality_dep **eq_dep, uint and_level, - Item_func *cond, Field *field, - bool eq_func, Item **value, - uint num_values, table_map usable_tables) +void add_eq_dep(Table_elimination *te, Equality_dep **eq_dep, + uint and_level, Item_func *cond, Field *field, + bool eq_func, Item **value, uint num_values, + table_map usable_tables) { - // Field *field= item_field->field; if (!(field->table->map & usable_tables)) return; @@ -606,7 +630,11 @@ } -Table_dep *get_table_dep(Table_elimination *te, TABLE *table) +/* + Get a Table_dep object for the given table, creating it if necessary. +*/ + +static Table_dep *get_table_dep(Table_elimination *te, TABLE *table) { Table_dep *tbl_dep= new Table_dep(table); Key_dep **key_list= &(tbl_dep->keys); @@ -625,19 +653,21 @@ return te->table_deps[table->tablenr] = tbl_dep; } + /* - Given a field, get its dependency element: if it already exists, find it, - otherwise create it. + Get a Field_dep object for the given field, creating it if necessary */ -Field_dep *get_field_dep(Table_elimination *te, Field *field) +static Field_dep *get_field_dep(Table_elimination *te, Field *field) { TABLE *table= field->table; Table_dep *tbl_dep; + /* First, get the table*/ if (!(tbl_dep= te->table_deps[table->tablenr])) tbl_dep= get_table_dep(te, table); - + + /* Try finding the field in field list */ Field_dep **pfield= &(tbl_dep->fields); while (*pfield && (*pfield)->field->field_index < field->field_index) { @@ -646,20 +676,34 @@ if (*pfield && (*pfield)->field->field_index == field->field_index) return *pfield; + /* Create the field and insert it in the list */ Field_dep *new_field= new Field_dep(tbl_dep, field); - new_field->next_table_field= *pfield; *pfield= new_field; + return new_field; } +/* + Create an Outer_join_dep object for the given outer join + + DESCRIPTION + Outer_join_dep objects for children (or further descendants) are always + created before the parents. +*/ + +static Outer_join_dep *get_outer_join_dep(Table_elimination *te, TABLE_LIST *outer_join, table_map deps_map) { Outer_join_dep *oj_dep; oj_dep= new Outer_join_dep(outer_join, deps_map); - + + /* + Collect a bitmap fo tables that we depend on, and also set parent pointer + for descendant outer join elements. + */ Table_map_iterator it(deps_map); int idx; while ((idx= it.next_bit()) != Table_map_iterator::BITMAP_END) @@ -667,6 +711,11 @@ Table_dep *table_dep; if (!(table_dep= te->table_deps[idx])) { + /* + We get here only when ON expression had no references to inner tables + and Table_map objects weren't created for them. This is a rare/ + unimportant case so it's ok to do not too efficient searches. + */ TABLE *table= NULL; for (TABLE_LIST *tlist= te->join->select_lex->leaf_tables; tlist; tlist=tlist->next_leaf) @@ -680,7 +729,13 @@ DBUG_ASSERT(table); table_dep= get_table_dep(te, table); } - + + /* + Walk from the table up to its embedding outer joins. The goal is to + find the least embedded outer join nest and set its parent pointer to + point to the newly created Outer_join_dep. + to set the pointer of its near + */ if (!table_dep->outer_join_dep) table_dep->outer_join_dep= oj_dep; else @@ -690,43 +745,35 @@ oj= oj->parent; oj->parent=oj_dep; } - } return oj_dep; } /* - Perform table elimination in a given join list + Build functional dependency graph for elements of given join list SYNOPSIS collect_funcdeps_for_join_list() - te Table elimination context. - join_list Join list to work on - its_outer_join TRUE <=> the join_list is an inner side of an - outer join - FALSE <=> otherwise (this is top-level join - list, simplify_joins flattens out all - other kinds of join lists) - - tables_in_list Bitmap of tables embedded in the join_list. - tables_used_elsewhere Bitmap of tables that are referred to from - somewhere outside of the join list (e.g. - select list, HAVING, etc). + te Table elimination context. + join_list Join list to work on + build_eq_deps TRUE <=> build Equality_dep elements for all + members of the join list, even if they cannot + be individually eliminated + tables_used_elsewhere Bitmap of tables that are referred to from + somewhere outside of this join list (e.g. + select list, HAVING, ON expressions of parent + joins, etc). + eliminable_tables INOUT Tables that can potentially be eliminated + (needed so we know for which tables to build + dependencies for) + eq_dep INOUT End of array of equality dependencies. DESCRIPTION - Perform table elimination for a join list. - Try eliminating children nests first. - The "all tables in join nest can produce only one matching record - combination" property checking is modeled after constant table detection, - plus we reuse info attempts to eliminate child join nests. - - RETURN - Number of children left after elimination. 0 means everything was - eliminated. + . */ -static uint +static void collect_funcdeps_for_join_list(Table_elimination *te, List<TABLE_LIST> *join_list, bool build_eq_deps, @@ -771,7 +818,7 @@ { // build comp_cond from ON expression uint and_level=0; - build_funcdeps_for_cond(te, eq_dep, &and_level, tbl->on_expr, + build_eq_deps_for_cond(te, eq_dep, &and_level, tbl->on_expr, *eliminable_tables); } @@ -781,19 +828,13 @@ tables_used_on_left |= tbl->on_expr->used_tables(); } } - return 0; + return; } + /* - Analyze exising FUNC_DEP array and add elements for tables and uniq keys - - SYNOPSIS - - DESCRIPTION - Add FUNC_DEP elements - - RETURN - . + This is used to analyse expressions in "tbl.col=expr" dependencies so + that we can figure out which fields the expression depends on. */ class Field_dependency_setter : public Field_enumerator @@ -819,20 +860,41 @@ return; } } - /* We didn't find the field. Bump the dependency anyway */ + /* + We got here if didn't find this field. It's not a part of + a unique key, and/or there is no field=expr element for it. + Bump the dependency anyway, this will signal that this dependency + cannot be satisfied. + */ te->equality_deps[expr_offset].unknown_args++; } } + Table_elimination *te; - uint expr_offset; /* Offset of the expression we're processing */ + /* Offset of the expression we're processing in the dependency bitmap */ + uint expr_offset; }; +/* + Setup equality dependencies + + SYNOPSIS + setup_equality_deps() + te Table elimination context + bound_deps_list OUT Start of linked list of elements that were found to + be bound (caller will use this to see if that + allows to declare further elements bound) +*/ + static bool setup_equality_deps(Table_elimination *te, Func_dep **bound_deps_list) { DBUG_ENTER("setup_equality_deps"); + /* + Count Field_dep objects and assign each of them a unique bitmap_offset. + */ uint offset= 0; for (Table_dep **tbl_dep=te->table_deps; tbl_dep < te->table_deps + MAX_TABLES; @@ -859,7 +921,10 @@ bitmap_clear_all(&te->expr_deps); /* - Walk through all field=expr elements and collect all fields. + Analyze all "field=expr" dependencies, and have te->expr_deps encode + dependencies of expressions from fields. + + Also collect a linked list of equalities that are bound. */ Func_dep *bound_dep= NULL; Field_dependency_setter deps_setter(te);

1 0

[Maria-developers] Rev 2733: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r5/
by Sergey Petrunya 13 Aug '09

13 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r5/ ------------------------------------------------------------ revno: 2733 revision-id: psergey(a)askmonty.org-20090813191053-g1xfeieoti4bqgbc parent: psergey(a)askmonty.org-20090813093613-hy7tdlsgdy83xszq committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 23:10:53 +0400 message: MWL#17: Table elimination - Better comments === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-13 09:36:13 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-13 19:10:53 +0000 @@ -20,19 +20,16 @@ OVERVIEW The module has one entry point - eliminate_tables() function, which one - needs to call (once) sometime after update_ref_and_keys() but before the - join optimization. + needs to call (once) at some point before the join optimization. eliminate_tables() operates over the JOIN structures. Logically, it removes the right sides of outer join nests. Physically, it changes the following members: * Eliminated tables are marked as constant and moved to the front of the join order. + * In addition to this, they are recorded in JOIN::eliminated_tables bitmap. - * All join nests have their NESTED_JOIN::n_tables updated to discount - the eliminated tables - * Items that became disused because they were in the ON expression of an eliminated outer join are notified by means of the Item tree walk which calls Item::mark_as_eliminated_processor for every item @@ -40,26 +37,13 @@ Item_subselect with its Item_subselect::eliminated flag which is used by EXPLAIN code to check if the subquery should be shown in EXPLAIN. - Table elimination is redone on every PS re-execution. (TODO reasons?) + Table elimination is redone on every PS re-execution. */ + /* - A structure that represents a functional dependency of something over - something else. This can be one of: - - 1. A "tbl.field = expr" equality. The field depends on the expression. - - 2. An Item_equal(...) multi-equality. Each participating field depends on - every other participating field. (TODO???) - - 3. A UNIQUE_KEY(field1, field2, fieldN). The key depends on the fields that - it is composed of. - - 4. A table (which is within an outer join nest). Table depends on a unique - key (value of a unique key identifies a table record) - - 5. An outer join nest. It depends on all tables it contains. - + An abstract structure that represents some entity that's being dependent on + some other entity. */ class Func_dep : public Sql_alloc @@ -73,9 +57,14 @@ FD_UNIQUE_KEY, FD_TABLE, FD_OUTER_JOIN - } type; - Func_dep *next; - bool bound; + } type; /* Type of the object */ + + /* + Used to make a linked list of elements that became bound and thus can + make elements that depend on them bound, too. + */ + Func_dep *next; + bool bound; /* TRUE<=> The entity is considered bound */ Func_dep() : next(NULL), bound(FALSE) {} }; @@ -84,10 +73,10 @@ class Table_dep; class Outer_join_dep; + /* - An equality - - Depends on multiple fields (those in its expression), unknown_args is a - counter of unsatisfied dependencies. + A "tbl.column= expr" equality dependency. tbl.column depends on fields + used in expr. */ class Equality_dep : public Func_dep { @@ -95,8 +84,11 @@ Field_dep *field; Item *val; - uint level; /* Used during condition analysis only */ - uint unknown_args; /* Number of yet unknown arguments */ + /* Used during condition analysis only, similar to KEYUSE::level */ + uint level; + + /* Number of fields referenced from *val that are not yet 'bound' */ + uint unknown_args; }; @@ -139,7 +131,7 @@ type= Func_dep::FD_UNIQUE_KEY; } Table_dep *table; /* Table this key is from */ - uint keyno; // TODO do we care about this + uint keyno; uint n_missing_keyparts; Key_dep *next_table_key; }; === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-08-13 09:24:02 +0000 +++ b/sql/sql_select.cc 2009-08-13 19:10:53 +0000 @@ -114,7 +114,7 @@ COND *conds, bool top); static bool check_interleaving_with_nj(JOIN_TAB *next); static void restore_prev_nj_state(JOIN_TAB *last); -static void reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list); +static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list); static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list, uint first_unused); @@ -8791,23 +8791,26 @@ tables which will be ignored. */ -static void reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list) +static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list) { List_iterator<TABLE_LIST> li(*join_list); TABLE_LIST *table; DBUG_ENTER("reset_nj_counters"); + uint n=0; while ((table= li++)) { NESTED_JOIN *nested_join; if ((nested_join= table->nested_join)) { nested_join->counter= 0; - nested_join->n_tables= my_count_bits(nested_join->used_tables & - ~join->eliminated_tables); - reset_nj_counters(join, &nested_join->join_list); + //nested_join->n_tables= my_count_bits(nested_join->used_tables & + // ~join->eliminated_tables); + nested_join->n_tables= reset_nj_counters(join, &nested_join->join_list); } + if (table->table && (table->table->map & ~join->eliminated_tables)) + n++; } - DBUG_VOID_RETURN; + DBUG_RETURN(n); }

1 0

[Maria-developers] Rev 2732: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r5/
by Sergey Petrunya 13 Aug '09

13 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r5/ ------------------------------------------------------------ revno: 2732 revision-id: psergey(a)askmonty.org-20090813093613-hy7tdlsgdy83xszq parent: psergey(a)askmonty.org-20090813092402-jlqucf6nultxlv4b committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 13:36:13 +0400 message: MWL#17: Table elimination Fixes after post-review fixes: - Don't search for tables in JOIN_TAB array. it's not initialized yet. use select_lex->leaf_tables instead. === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-13 00:01:43 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-13 09:36:13 +0000 @@ -676,16 +676,12 @@ if (!(table_dep= te->table_deps[idx])) { TABLE *table= NULL; - /* - Locate and create the table. The search isnt very efficient but - typically we won't get here as we process the ON expression first - and that will create the Table_dep - */ - for (uint i= 0; i < te->join->tables; i++) + for (TABLE_LIST *tlist= te->join->select_lex->leaf_tables; tlist; + tlist=tlist->next_leaf) { - if (te->join->join_tab[i].table->tablenr == (uint)idx) + if (tlist->table->tablenr == (uint)idx) { - table= te->join->join_tab[i].table; + table=tlist->table; break; } }

1 0