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