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

From: | Sven Sandberg | Date: | January 14 2011 6:50pm |

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

View as plain text |

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. 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. (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. 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 |