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