diff options
Diffstat (limited to 'sql/opt_range.h')
-rw-r--r-- | sql/opt_range.h | 53 |
1 files changed, 52 insertions, 1 deletions
diff --git a/sql/opt_range.h b/sql/opt_range.h index 11d9f80865a..d37339707b8 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -223,6 +223,43 @@ class RANGE_OPT_PARAM; We avoid consuming too much memory by setting a limit on the number of SEL_ARG object we can construct during one range analysis invocation. + + 5. SEL_ARG GRAPH WEIGHT + + A SEL_ARG graph has a property we call weight, and we define it as follows: + + If the SEL_ARG graph does not have any node with multiple incoming + next_key_part edges, then its weight is the number of SEL_ARG objects used. + + If there is a node with multiple next_key_part edges, clone the node (and + the nodes connected via prev/next links to it) and redirect one of the + incoming next_key_part to the clone. (If the node has "peer" nodes + connected to it via prev/next links, they will have to be cloned as well) + + Repeat this until we get a graph without multiple next_key_part edges + coming into the same node. Then, the number of SEL_ARG objects in the + graph is the weight. + + Example: + + | +-------+ $ $ + \->| kp1=2 |--$--------------$-+ + +-------+ $ $ | +--------+ + | $ $ ==>| kp3=11 | + +-------+ $ $ | +--------+ + | kp1=3 |--$--------------$-+ | + +-------+ $ $ +--------+ + $ $ | kp3=14 | + $ $ +--------+ + + Here, the weight is 2 + 2*2=6. + + The rationale behind the weight is: + - it has the same order-of-magnitude as the number of ranges that the + SEL_ARG graph is describing, + - it is a lot easier to compute, + - it can be updated incrementally when performing AND/OR operations on + parts of the graph. */ class SEL_ARG :public Sql_alloc @@ -236,6 +273,9 @@ public: /* The ordinal number the least significant component encountered in the ranges of the SEL_ARG tree (the first component has number 1) + + Note: this number is currently not precise, it is an upper bound. + @seealso SEL_ARG::get_max_key_part() */ uint16 max_part_no; /* @@ -263,6 +303,14 @@ public: enum leaf_color { BLACK,RED } color; enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type; + /* + For R-B root nodes only: the graph weight, as defined above in the + SEL_ARG GRAPH WEIGHT section. + */ + uint weight; + enum { MAX_WEIGHT = 32000 }; + + /* See RANGE_OPT_PARAM::alloced_sel_args */ enum { MAX_SEL_ARGS = 16000 }; SEL_ARG() {} @@ -273,7 +321,7 @@ public: SEL_ARG(enum Type type_arg) :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, elements(1),use_count(1),left(0),right(0), - next_key_part(0), color(BLACK), type(type_arg) + next_key_part(0), color(BLACK), type(type_arg), weight(1) {} /** returns true if a range predicate is equal. Use all_same() @@ -287,6 +335,9 @@ public: return true; return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0; } + + uint get_max_key_part() const; + /** returns true if all the predicates in the keypart tree are equal */ |