List: | Commits | « Previous MessageNext Message » | |

From: | He Zhenxing | Date: | January 18 2011 2:52am |

Subject: | Re: bzr commit into mysql-5.1-bugteam branch (zhenxing.he:3418) Bug#42415 | ||

View as plain text |

Sven Sandberg wrote: > Hi Zhenxing, > > This is a partial review, let's discuss it more on IRC. > > This is a very difficult bug and you did a very detailed and analysis. > You also implemented the complicated algorithm that solves it. > Thank you! > There is still the the unresolved issue of how we can call fix_fields() > before decide_logging_format(). I also have three suggestions to improve > the implementation: > > (1) It seems you added a condition that marks the table as ordered > when there is an ORDER BY on every column. I may be wrong but I think > this is not correct. > I think you're right, case insensitive columns will be a problem. > (2) I think you have implemented the algorithm I suggested in the bug > report on 29 Oct. Please see my comment on 3 Nov: there is a more > efficient algorithm. > > (3) This implementation does a lot of allocation. I think it's > possible to optimize away that by using a more compact graph representation. > Agree, will try to work on your suggestions. > > On 12/09/2010 05:18 AM, He Zhenxing wrote: > [...] > > === modified file 'sql/sql_select.cc' > > --- a/sql/sql_select.cc 2010-05-27 15:13:53 +0000 > > +++ b/sql/sql_select.cc 2010-12-09 04:18:42 +0000 > [...] > > @@ -17162,6 +17178,457 @@ bool JOIN::change_result(select_result * > [...] > > +/* > > + And-or graph truth propogation algorithm is used to calculate if the > > + statement is ordered or not. > > + > > + Nodes: > > + JoinNode - And node, this is the root, successors are a list of > > + ConstOrderedTableNode. > > + ConstOrderedTableNode - Or node, have two TableNode as successors, > > + one for ordered table, and the other for constant table. > > + TableNode - Or node, have a list of KeyNode and one AllColumnsNode > > + as successors. > > + KeyNode - And node, successors are a list of ColumnNode that corresponding > > + to the fields of the key. > > + AllColumnsNode - And node, successors are a list of ColumnNode of all > > + fields of the table. > > + ColumnNode - Or node, represent a field of the table, it will take a > > + TableNode as a successor, which means if a table is true > > + (const or ordered), the all its columns are const or ordered. > > + Successors to other column nodes will be added mutually if > > + there is an equation to that field in the condition. The > > + column nodes for fields that are in the ORDER BY or are > > + equal to constants are added to the init_nodes of the JoinNode, > > + which is used as the initial true values of the propogation. > > (1) If I understand correctly, you have added the following condition > (the AllColumnsNode): > > "If there are ORDER BY clauses that cover all columns, then the table is > marked as ordered". > > However, I think this is not correct. ORDER BY clauses only make the > table deterministic if there is a key. For example, a column may be > ordered using a case-insensitive collation. An example: > > CREATE TABLE t1 (a TEXT COLLATE utf8_general_ci); > CREATE TABLE t2 (a TEXT); > INSERT INTO t1 VALUES ("a"), ("A"); > INSERT INTO t2 SELECT * FROM t1 LIMIT 1; > > > [...] > +bool JoinNode::is_ordered() > +{ > + List<Node> nodes(init_nodes); > + List_iterator<Node> it(nodes); > + Node *node; > + > + while ((node= it++)) > + { > + node->todo--; > + if (node->todo == 0) > + { > + if (node == this) > + return true; > + List_iterator<Node> pit(node->predecessors); > + Node *pnode; > + while ((pnode= pit++)) > + { > + if (pnode->todo) > + nodes.push_back(pnode); > + } > + } > + } > + return false; > +} > > (2) I think the above implements the algorithm from my comment on the > bug on 29 Oct. Please see the comment from 3 Nov: I think that algorithm > has better space requirements. > > > (3) This implementation has to allocate two objects for every node in > the graph (the Node object and a List<Node> object). I also think that > the List class probably allocates one object per element; in that case > there is also one allocated object per edge in the graph and one for > each iteration of the algorithm. I think this may add both time and > space overhead that is significant. I think we can reduce this to only 4 > allocations altogether, and at most 12 bytes per node + 4 bytes per > edge. This should reduce both time and space requirements. Here's the idea: > > - Each node is identified by an integer. The root node is number 0. > > - The only data we need for each node is one integer: the "todo" > field. > > - The graph structure can be represented using two integer lists. The > first list contains all successor lists concatenated into one big > flat list. The second list is indexed by node numbers and gives for > each node the offset in the first list where the node's successors > are stored. > > - The set S is represented as a list. Elements are added and removed > from S in a stack-like way, i.e., pushed to the end when added and > popped from the end when removed. > > > So the following data types can be used: > > /* > The number of nodes in the graph. > */ > int n_nodes; > /* > The 'todo' array is indexed by node numbers. If N is a node, then > todo[N] contains the number of successors of N that need to be > marked deterministic before N is marked true. > */ > int *todo; > /* > Lists the successors of all nodes. This is a big flat list: > first all successors of node 0, then all successors of node 1, > etc. > */ > int *successor; > /* > If N is a node, then node_successor[N] contains the index into > the 'successor' array where the first successor of N is stored. > */ > int *node_successor; > /* > The 'dirty_nodes' array is a stack used during the evaluation > of the and-or graph. It contains all nodes that have been marked > as true where the truth value has not yet been propagated to > the successors. 'n_dirty_nodes' is the number of elements > in 'dirty_nodes'. > */ > int n_dirty_nodes; > int *dirty_nodes; > > > The algorithm can then be implemented like: > > while (n_dirty_nodes) > { > int node= dirty_nodes[--n_dirty_nodes]; > int i_end= node_successor[node + 1]; > for (int i= node_successor[node]; i < i_end; i++) { > int succ= successor[i]; > if (todo[succ]) { > todo[succ]--; > if (todo[succ] == 0) { > if (succ == 0) // the root node > return TRUE; > dirty_nodes[n_dirty_nodes++]= succ; > } > } > } > } > return FALSE; > > > I think these data structures can be initialized as follows (this is > just a sketch): > > 1. Count the number of nodes of each type. > 2. Allocate todo (n_nodes elements), node_successor (n_nodes+1 > elements), and dirty_nodes (n_nodes elements). > 3. Count the number of successors for each node. Store this temporary > number in node_successor. > 4. Allocate successor. > 5. Initialize node_successor: > int ofs= 0; > for (int i= 0; i <= n_nodes; i++) { > int n_succ= node_successor[i]; > node_successor[i]= ofs; > ofs += n_succ; > } > 6. Fill successor with elements. During this algorithm, we need to > store the number of successors of each node that have been added > to the array. This number can be stored in dirty_nodes. > 7. Initialize dirty_nodes. > > /Sven >

Thread | ||
---|---|---|

• bzr commit into mysql-5.1-bugteam branch (zhenxing.he:3418) Bug#42415 | He Zhenxing | 9 Dec |

• Re: bzr commit into mysql-5.1-bugteam branch (zhenxing.he:3418) Bug#42415 | Sven Sandberg | 14 Jan |

• Re: bzr commit into mysql-5.1-bugteam branch (zhenxing.he:3418)Bug#42415 | He Zhenxing | 18 Jan |