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