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 } SEL_ARG_RANGE_SEQ;
57
58
59 /*
60 Range sequence interface, SEL_ARG* implementation: Initialize the traversal
61
62 SYNOPSIS
63 init()
64 init_params SEL_ARG tree traversal context
65 n_ranges [ignored] The number of ranges obtained
66 flags [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
67
68 RETURN
69 Value of init_param
70 */
71
sel_arg_range_seq_init(void * init_param,uint n_ranges,uint flags)72 range_seq_t sel_arg_range_seq_init(void *init_param, uint n_ranges, uint flags)
73 {
74 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
75 seq->param->range_count=0;
76 seq->at_start= TRUE;
77 seq->param->max_key_part= 0;
78 seq->stack[0].key_tree= NULL;
79 seq->stack[0].min_key= seq->param->min_key;
80 seq->stack[0].min_key_flag= 0;
81 seq->stack[0].min_key_parts= 0;
82
83 seq->stack[0].max_key= seq->param->max_key;
84 seq->stack[0].max_key_flag= 0;
85 seq->stack[0].max_key_parts= 0;
86 seq->i= 0;
87 return init_param;
88 }
89
90
step_down_to(SEL_ARG_RANGE_SEQ * arg,SEL_ARG * key_tree)91 static void step_down_to(SEL_ARG_RANGE_SEQ *arg, SEL_ARG *key_tree)
92 {
93 RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
94 RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
95
96 cur->key_tree= key_tree;
97 cur->min_key= prev->min_key;
98 cur->max_key= prev->max_key;
99 cur->min_key_parts= prev->min_key_parts;
100 cur->max_key_parts= prev->max_key_parts;
101
102 uint16 stor_length= arg->param->key[arg->keyno][key_tree->part].store_length;
103 cur->min_key_parts += key_tree->store_min(stor_length, &cur->min_key,
104 prev->min_key_flag);
105 cur->max_key_parts += key_tree->store_max(stor_length, &cur->max_key,
106 prev->max_key_flag);
107
108 cur->min_key_flag= prev->min_key_flag | key_tree->min_flag;
109 cur->max_key_flag= prev->max_key_flag | key_tree->max_flag;
110
111 if (key_tree->is_null_interval())
112 cur->min_key_flag |= NULL_RANGE;
113 (arg->i)++;
114 }
115
116
117 /*
118 Range sequence interface, SEL_ARG* implementation: get the next interval
119
120 SYNOPSIS
121 sel_arg_range_seq_next()
122 rseq Value returned from sel_arg_range_seq_init
123 range OUT Store information about the range here
124
125 DESCRIPTION
126 This is "get_next" function for Range sequence interface implementation
127 for SEL_ARG* tree.
128
129 IMPLEMENTATION
130 The traversal also updates those param members:
131 - is_ror_scan
132 - range_count
133 - max_key_part
134
135 RETURN
136 FALSE Ok
137 TRUE No more ranges in the sequence
138 */
139
140 #if defined(_MSC_FULL_VER) && (_MSC_FULL_VER == 160030319)
141 /*
142 Workaround Visual Studio 2010 RTM compiler backend bug, the function enters
143 infinite loop.
144 */
145 #pragma optimize("g", off)
146 #endif
147
sel_arg_range_seq_next(range_seq_t rseq,KEY_MULTI_RANGE * range)148 bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
149 {
150 SEL_ARG *key_tree;
151 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
152 if (seq->at_start)
153 {
154 key_tree= seq->start;
155 seq->at_start= FALSE;
156 goto walk_up_n_right;
157 }
158
159 key_tree= seq->stack[seq->i].key_tree;
160 /* Ok, we're at some "full tuple" position in the tree */
161
162 /* Step down if we can */
163 if (key_tree->next && key_tree->next != &null_element)
164 {
165 //step down; (update the tuple, we'll step right and stay there)
166 seq->i--;
167 step_down_to(seq, key_tree->next);
168 key_tree= key_tree->next;
169 seq->param->is_ror_scan= FALSE;
170 goto walk_right_n_up;
171 }
172
173 /* Ok, can't step down, walk left until we can step down */
174 while (1)
175 {
176 if (seq->i == 1) // can't step left
177 return 1;
178 /* Step left */
179 seq->i--;
180 key_tree= seq->stack[seq->i].key_tree;
181
182 /* Step down if we can */
183 if (key_tree->next && key_tree->next != &null_element)
184 {
185 // Step down; update the tuple
186 seq->i--;
187 step_down_to(seq, key_tree->next);
188 key_tree= key_tree->next;
189 break;
190 }
191 }
192
193 /*
194 Ok, we've stepped down from the path to previous tuple.
195 Walk right-up while we can
196 */
197 walk_right_n_up:
198 while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
199 key_tree->next_key_part->part == key_tree->part + 1 &&
200 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
201 {
202 {
203 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
204 size_t min_key_length= cur->min_key - seq->param->min_key;
205 size_t max_key_length= cur->max_key - seq->param->max_key;
206 size_t len= cur->min_key - cur[-1].min_key;
207 if (!(min_key_length == max_key_length &&
208 !memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
209 !key_tree->min_flag && !key_tree->max_flag))
210 {
211 seq->param->is_ror_scan= FALSE;
212 if (!key_tree->min_flag)
213 cur->min_key_parts +=
214 key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
215 &cur->min_key,
216 &cur->min_key_flag, MAX_KEY);
217 if (!key_tree->max_flag)
218 cur->max_key_parts +=
219 key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
220 &cur->max_key,
221 &cur->max_key_flag, MAX_KEY);
222 break;
223 }
224 }
225
226 /*
227 Ok, current atomic interval is in form "t.field=const" and there is
228 next_key_part interval. Step right, and walk up from there.
229 */
230 key_tree= key_tree->next_key_part;
231
232 walk_up_n_right:
233 while (key_tree->prev && key_tree->prev != &null_element)
234 {
235 /* Step up */
236 key_tree= key_tree->prev;
237 }
238 step_down_to(seq, key_tree);
239 }
240
241 /* Ok got a tuple */
242 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
243 uint min_key_length= (uint)(cur->min_key - seq->param->min_key);
244
245 range->ptr= (char*)(intptr)(key_tree->part);
246 if (cur->min_key_flag & GEOM_FLAG)
247 {
248 range->range_flag= cur->min_key_flag;
249
250 /* Here minimum contains also function code bits, and maximum is +inf */
251 range->start_key.key= seq->param->min_key;
252 range->start_key.length= min_key_length;
253 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
254 range->start_key.flag= (ha_rkey_function) (cur->min_key_flag ^ GEOM_FLAG);
255 }
256 else
257 {
258 range->range_flag= cur->min_key_flag | cur->max_key_flag;
259
260 range->start_key.key= seq->param->min_key;
261 range->start_key.length= (uint)(cur->min_key - seq->param->min_key);
262 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
263 range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
264 HA_READ_KEY_EXACT);
265
266 range->end_key.key= seq->param->max_key;
267 range->end_key.length= (uint)(cur->max_key - seq->param->max_key);
268 range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
269 HA_READ_AFTER_KEY);
270 range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
271
272 KEY *key_info;
273 if (seq->real_keyno== MAX_KEY)
274 key_info= NULL;
275 else
276 key_info= &seq->param->table->key_info[seq->real_keyno];
277
278 /*
279 This is an equality range (keypart_0=X and ... and keypart_n=Z) if
280 (1) - There are no flags indicating open range (e.g.,
281 "keypart_x > y") or GIS.
282 (2) - The lower bound and the upper bound of the range has the
283 same value (min_key == max_key).
284 */
285 const uint is_open_range =
286 (NO_MIN_RANGE | NO_MAX_RANGE | NEAR_MIN | NEAR_MAX | GEOM_FLAG);
287 const bool is_eq_range_pred =
288 !(cur->min_key_flag & is_open_range) && // (1)
289 !(cur->max_key_flag & is_open_range) && // (1)
290 range->start_key.length == range->end_key.length && // (2)
291 !memcmp(seq->param->min_key, seq->param->max_key, // (2)
292 range->start_key.length);
293
294 if (is_eq_range_pred)
295 {
296 range->range_flag = EQ_RANGE;
297
298 /*
299 Conditions below:
300 (1) - Range analysis is used for estimating condition selectivity
301 (2) - This is a unique key, and we have conditions for all its
302 user-defined key parts.
303 (3) - The table uses extended keys, this key covers all components,
304 and we have conditions for all key parts.
305 */
306 if (
307 !key_info || // (1)
308 ((uint)key_tree->part+1 == key_info->user_defined_key_parts && // (2)
309 key_info->flags & HA_NOSAME) || // (2)
310 ((key_info->flags & HA_EXT_NOSAME) && // (3)
311 (uint)key_tree->part+1 == key_info->ext_key_parts) // (3)
312 )
313 range->range_flag |= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
314 }
315
316 if (seq->param->is_ror_scan)
317 {
318 /*
319 If we get here, the condition on the key was converted to form
320 "(keyXpart1 = c1) AND ... AND (keyXpart{key_tree->part - 1} = cN) AND
321 somecond(keyXpart{key_tree->part})"
322 Check if
323 somecond is "keyXpart{key_tree->part} = const" and
324 uncovered "tail" of KeyX parts is either empty or is identical to
325 first members of clustered primary key.
326 */
327 if (!(!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
328 (range->start_key.length == range->end_key.length) &&
329 !memcmp(range->start_key.key, range->end_key.key, range->start_key.length) &&
330 is_key_scan_ror(seq->param, seq->real_keyno, key_tree->part + 1)))
331 seq->param->is_ror_scan= FALSE;
332 }
333 }
334 seq->param->range_count++;
335 seq->param->max_key_part=MY_MAX(seq->param->max_key_part,key_tree->part);
336 return 0;
337 }
338
339 #if defined(_MSC_FULL_VER) && (_MSC_FULL_VER == 160030319)
340 /* VS2010 compiler bug workaround */
341 #pragma optimize("g", on)
342 #endif
343
344
345 /****************************************************************************
346 MRR Range Sequence Interface implementation that walks array<QUICK_RANGE>
347 ****************************************************************************/
348
349 /*
350 Range sequence interface implementation for array<QUICK_RANGE>: initialize
351
352 SYNOPSIS
353 quick_range_seq_init()
354 init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
355 n_ranges Number of ranges in the sequence (ignored)
356 flags MRR flags (currently not used)
357
358 RETURN
359 Opaque value to be passed to quick_range_seq_next
360 */
361
quick_range_seq_init(void * init_param,uint n_ranges,uint flags)362 range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags)
363 {
364 QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
365 quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
366 quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
367 quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
368 quick->ranges.elements;
369 return &quick->qr_traversal_ctx;
370 }
371
372
373 /*
374 Range sequence interface implementation for array<QUICK_RANGE>: get next
375
376 SYNOPSIS
377 quick_range_seq_next()
378 rseq Value returned from quick_range_seq_init
379 range OUT Store information about the range here
380
381 RETURN
382 0 Ok
383 1 No more ranges in the sequence
384 */
385
quick_range_seq_next(range_seq_t rseq,KEY_MULTI_RANGE * range)386 bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
387 {
388 QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
389
390 if (ctx->cur == ctx->last)
391 return 1; /* no more ranges */
392
393 QUICK_RANGE *cur= *(ctx->cur);
394 cur->make_min_endpoint(&range->start_key);
395 cur->make_max_endpoint(&range->end_key);
396 range->range_flag= cur->flag;
397 ctx->cur++;
398 return 0;
399 }
400
401
402