1 /*
2 Copyright (c) 2009, 2011, Monty Program Ab
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
16
17 /****************************************************************************
18 MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
19 ****************************************************************************/
20
21 /* MRR range sequence, SEL_ARG* implementation: stack entry */
22 typedef struct st_range_seq_entry
23 {
24 /*
25 Pointers in min and max keys. They point to right-after-end of key
26 images. The 0-th entry has these pointing to key tuple start.
27 */
28 uchar *min_key, *max_key;
29
30 /*
31 Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
32 min_key_flag may have NULL_RANGE set.
33 */
34 uint min_key_flag, max_key_flag;
35
36 /* Number of key parts */
37 uint min_key_parts, max_key_parts;
38 SEL_ARG *key_tree;
39 } RANGE_SEQ_ENTRY;
40
41
42 /*
43 MRR range sequence, SEL_ARG* implementation: SEL_ARG graph traversal context
44 */
45 typedef struct st_sel_arg_range_seq
46 {
47 uint keyno; /* index of used tree in SEL_TREE structure */
48 uint real_keyno; /* Number of the index in tables */
49 PARAM *param;
50 SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
51
52 RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
53 int i; /* Index of last used element in the above array */
54
55 bool at_start; /* TRUE <=> The traversal has just started */
56 /*
57 Iteration functions will set this to FALSE
58 if ranges being traversed do not allow to construct a ROR-scan"
59 */
60 bool is_ror_scan;
61 } SEL_ARG_RANGE_SEQ;
62
63
64 /*
65 Range sequence interface, SEL_ARG* implementation: Initialize the traversal
66
67 SYNOPSIS
68 init()
69 init_params SEL_ARG tree traversal context
70 n_ranges [ignored] The number of ranges obtained
71 flags [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
72
73 RETURN
74 Value of init_param
75 */
76
sel_arg_range_seq_init(void * init_param,uint n_ranges,uint flags)77 range_seq_t sel_arg_range_seq_init(void *init_param, uint n_ranges, uint flags)
78 {
79 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
80 seq->param->range_count=0;
81 seq->at_start= TRUE;
82 seq->param->max_key_parts= 0;
83 seq->stack[0].key_tree= NULL;
84 seq->stack[0].min_key= seq->param->min_key;
85 seq->stack[0].min_key_flag= 0;
86 seq->stack[0].min_key_parts= 0;
87
88 seq->stack[0].max_key= seq->param->max_key;
89 seq->stack[0].max_key_flag= 0;
90 seq->stack[0].max_key_parts= 0;
91 seq->i= 0;
92 return init_param;
93 }
94
95
step_down_to(SEL_ARG_RANGE_SEQ * arg,SEL_ARG * key_tree)96 static void step_down_to(SEL_ARG_RANGE_SEQ *arg, SEL_ARG *key_tree)
97 {
98 RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
99 RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
100
101 cur->key_tree= key_tree;
102 cur->min_key= prev->min_key;
103 cur->max_key= prev->max_key;
104 cur->min_key_parts= prev->min_key_parts;
105 cur->max_key_parts= prev->max_key_parts;
106
107 uint16 stor_length= arg->param->key[arg->keyno][key_tree->part].store_length;
108 cur->min_key_parts += key_tree->store_min(stor_length, &cur->min_key,
109 prev->min_key_flag);
110 cur->max_key_parts += key_tree->store_max(stor_length, &cur->max_key,
111 prev->max_key_flag);
112
113 cur->min_key_flag= prev->min_key_flag | key_tree->min_flag;
114 cur->max_key_flag= prev->max_key_flag | key_tree->max_flag;
115
116 if (key_tree->is_null_interval())
117 cur->min_key_flag |= NULL_RANGE;
118 (arg->i)++;
119 }
120
121
122 /*
123 Range sequence interface, SEL_ARG* implementation: get the next interval
124
125 SYNOPSIS
126 sel_arg_range_seq_next()
127 rseq Value returned from sel_arg_range_seq_init
128 range OUT Store information about the range here
129
130 DESCRIPTION
131 This is "get_next" function for Range sequence interface implementation
132 for SEL_ARG* tree.
133
134 IMPLEMENTATION
135 The traversal also updates those param members:
136 - is_ror_scan
137 - range_count
138 - max_key_part
139
140 RETURN
141 FALSE Ok
142 TRUE No more ranges in the sequence
143 */
144
145 #if defined(_MSC_FULL_VER) && (_MSC_FULL_VER == 160030319)
146 /*
147 Workaround Visual Studio 2010 RTM compiler backend bug, the function enters
148 infinite loop.
149 */
150 #pragma optimize("g", off)
151 #endif
152
sel_arg_range_seq_next(range_seq_t rseq,KEY_MULTI_RANGE * range)153 bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
154 {
155 SEL_ARG *key_tree;
156 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
157 if (seq->at_start)
158 {
159 key_tree= seq->start;
160 seq->at_start= FALSE;
161 goto walk_up_n_right;
162 }
163
164 key_tree= seq->stack[seq->i].key_tree;
165 /* Ok, we're at some "full tuple" position in the tree */
166
167 /* Step down if we can */
168 if (key_tree->next && key_tree->next != &null_element)
169 {
170 //step down; (update the tuple, we'll step right and stay there)
171 seq->i--;
172 step_down_to(seq, key_tree->next);
173 key_tree= key_tree->next;
174 seq->is_ror_scan= FALSE;
175 goto walk_right_n_up;
176 }
177
178 /* Ok, can't step down, walk left until we can step down */
179 while (1)
180 {
181 if (seq->i == 1) // can't step left
182 return 1;
183 /* Step left */
184 seq->i--;
185 key_tree= seq->stack[seq->i].key_tree;
186
187 /* Step down if we can */
188 if (key_tree->next && key_tree->next != &null_element)
189 {
190 // Step down; update the tuple
191 seq->i--;
192 step_down_to(seq, key_tree->next);
193 key_tree= key_tree->next;
194 break;
195 }
196 }
197
198 /*
199 Ok, we've stepped down from the path to previous tuple.
200 Walk right-up while we can
201 */
202 walk_right_n_up:
203 while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
204 key_tree->next_key_part->part == key_tree->part + 1 &&
205 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
206 {
207 {
208 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
209 size_t min_key_length= cur->min_key - seq->param->min_key;
210 size_t max_key_length= cur->max_key - seq->param->max_key;
211 size_t len= cur->min_key - cur[-1].min_key;
212 if (!(min_key_length == max_key_length &&
213 !memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
214 !key_tree->min_flag && !key_tree->max_flag))
215 {
216 seq->is_ror_scan= FALSE;
217 if (!key_tree->min_flag)
218 cur->min_key_parts +=
219 key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
220 &cur->min_key,
221 &cur->min_key_flag, MAX_KEY);
222 if (!key_tree->max_flag)
223 cur->max_key_parts +=
224 key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
225 &cur->max_key,
226 &cur->max_key_flag, MAX_KEY);
227 break;
228 }
229 }
230
231 /*
232 Ok, current atomic interval is in form "t.field=const" and there is
233 next_key_part interval. Step right, and walk up from there.
234 */
235 key_tree= key_tree->next_key_part;
236
237 walk_up_n_right:
238 while (key_tree->prev && key_tree->prev != &null_element)
239 {
240 /* Step up */
241 key_tree= key_tree->prev;
242 }
243 step_down_to(seq, key_tree);
244 }
245
246 /* Ok got a tuple */
247 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
248 uint min_key_length= (uint)(cur->min_key - seq->param->min_key);
249
250 range->ptr= (char*)(intptr)(key_tree->part);
251 uint max_key_parts;
252 if (cur->min_key_flag & GEOM_FLAG)
253 {
254 range->range_flag= cur->min_key_flag;
255
256 /* Here minimum contains also function code bits, and maximum is +inf */
257 range->start_key.key= seq->param->min_key;
258 range->start_key.length= min_key_length;
259 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
260 range->start_key.flag= (ha_rkey_function) (cur->min_key_flag ^ GEOM_FLAG);
261 max_key_parts= cur->min_key_parts;
262 }
263 else
264 {
265 max_key_parts= MY_MAX(cur->min_key_parts, cur->max_key_parts);
266
267 range->start_key.key= seq->param->min_key;
268 range->start_key.length= (uint)(cur->min_key - seq->param->min_key);
269 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
270 range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
271 HA_READ_KEY_EXACT);
272
273 range->end_key.key= seq->param->max_key;
274 range->end_key.length= (uint)(cur->max_key - seq->param->max_key);
275 range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
276 HA_READ_AFTER_KEY);
277 range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
278
279 KEY *key_info;
280 if (seq->real_keyno== MAX_KEY)
281 key_info= NULL;
282 else
283 key_info= &seq->param->table->key_info[seq->real_keyno];
284
285 /*
286 This is an equality range (keypart_0=X and ... and keypart_n=Z) if
287 (1) - There are no flags indicating open range (e.g.,
288 "keypart_x > y") or GIS.
289 (2) - The lower bound and the upper bound of the range has the
290 same value (min_key == max_key).
291 */
292 const uint is_open_range =
293 (NO_MIN_RANGE | NO_MAX_RANGE | NEAR_MIN | NEAR_MAX | GEOM_FLAG);
294 const bool is_eq_range_pred =
295 !(cur->min_key_flag & is_open_range) && // (1)
296 !(cur->max_key_flag & is_open_range) && // (1)
297 range->start_key.length == range->end_key.length && // (2)
298 !memcmp(seq->param->min_key, seq->param->max_key, // (2)
299 range->start_key.length);
300
301 range->range_flag= 0;
302 if (is_eq_range_pred)
303 {
304 range->range_flag = EQ_RANGE;
305
306 /*
307 Conditions below:
308 (1) - Range analysis is used for estimating condition selectivity
309 (2) - This is a unique key, and we have conditions for all its
310 user-defined key parts.
311 (3) - The table uses extended keys, this key covers all components,
312 and we have conditions for all key parts.
313 */
314 if (
315 !key_info || // (1)
316 ((uint)key_tree->part+1 == key_info->user_defined_key_parts && // (2)
317 key_info->flags & HA_NOSAME) || // (2)
318 ((key_info->flags & HA_EXT_NOSAME) && // (3)
319 (uint)key_tree->part+1 == key_info->ext_key_parts) // (3)
320 )
321 range->range_flag |= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
322 }
323
324 if (seq->is_ror_scan)
325 {
326 /*
327 If we get here, the condition on the key was converted to form
328 "(keyXpart1 = c1) AND ... AND (keyXpart{key_tree->part - 1} = cN) AND
329 somecond(keyXpart{key_tree->part})"
330 Check if
331 somecond is "keyXpart{key_tree->part} = const" and
332 uncovered "tail" of KeyX parts is either empty or is identical to
333 first members of clustered primary key.
334 */
335 if (!(!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
336 (range->start_key.length == range->end_key.length) &&
337 !memcmp(range->start_key.key, range->end_key.key, range->start_key.length) &&
338 is_key_scan_ror(seq->param, seq->real_keyno, key_tree->part + 1)))
339 seq->is_ror_scan= FALSE;
340 }
341 }
342 seq->param->range_count++;
343 seq->param->max_key_parts= MY_MAX(seq->param->max_key_parts, max_key_parts);
344 return 0;
345 }
346
347 #if defined(_MSC_FULL_VER) && (_MSC_FULL_VER == 160030319)
348 /* VS2010 compiler bug workaround */
349 #pragma optimize("g", on)
350 #endif
351
352
353 /****************************************************************************
354 MRR Range Sequence Interface implementation that walks array<QUICK_RANGE>
355 ****************************************************************************/
356
357 /*
358 Range sequence interface implementation for array<QUICK_RANGE>: initialize
359
360 SYNOPSIS
361 quick_range_seq_init()
362 init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
363 n_ranges Number of ranges in the sequence (ignored)
364 flags MRR flags (currently not used)
365
366 RETURN
367 Opaque value to be passed to quick_range_seq_next
368 */
369
quick_range_seq_init(void * init_param,uint n_ranges,uint flags)370 range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags)
371 {
372 QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
373 quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
374 quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
375 quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
376 quick->ranges.elements;
377 return &quick->qr_traversal_ctx;
378 }
379
380
381 /*
382 Range sequence interface implementation for array<QUICK_RANGE>: get next
383
384 SYNOPSIS
385 quick_range_seq_next()
386 rseq Value returned from quick_range_seq_init
387 range OUT Store information about the range here
388
389 RETURN
390 0 Ok
391 1 No more ranges in the sequence
392 */
393
quick_range_seq_next(range_seq_t rseq,KEY_MULTI_RANGE * range)394 bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
395 {
396 QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
397
398 if (ctx->cur == ctx->last)
399 return 1; /* no more ranges */
400
401 QUICK_RANGE *cur= *(ctx->cur);
402 cur->make_min_endpoint(&range->start_key);
403 cur->make_max_endpoint(&range->end_key);
404 range->range_flag= cur->flag;
405 ctx->cur++;
406 return 0;
407 }
408
409
410