← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/innobase/pars/pars0opt.c

Merged in move of status variables.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/pars/pars0opt.c
1
 
/*****************************************************************************
2
 
 
3
 
Copyright (c) 1997, 2009, Innobase Oy. All Rights Reserved.
4
 
 
5
 
This program is free software; you can redistribute it and/or modify it under
6
 
the terms of the GNU General Public License as published by the Free Software
7
 
Foundation; version 2 of the License.
8
 
 
9
 
This program is distributed in the hope that it will be useful, but WITHOUT
10
 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
 
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
 
 
13
 
You should have received a copy of the GNU General Public License along with
14
 
this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
15
 
St, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
*****************************************************************************/
18
 
 
19
 
/**************************************************//**
20
 
@file pars/pars0opt.c
21
 
Simple SQL optimizer
22
 
 
23
 
Created 12/21/1997 Heikki Tuuri
24
 
*******************************************************/
25
 
 
26
 
#include "pars0opt.h"
27
 
 
28
 
#ifdef UNIV_NONINL
29
 
#include "pars0opt.ic"
30
 
#endif
31
 
 
32
 
#include "row0sel.h"
33
 
#include "row0ins.h"
34
 
#include "row0upd.h"
35
 
#include "dict0dict.h"
36
 
#include "dict0mem.h"
37
 
#include "que0que.h"
38
 
#include "pars0grm.h"
39
 
#include "pars0pars.h"
40
 
#include "lock0lock.h"
41
 
 
42
 
#define OPT_EQUAL       1       /* comparison by = */
43
 
#define OPT_COMPARISON  2       /* comparison by <, >, <=, or >= */
44
 
 
45
 
#define OPT_NOT_COND    1
46
 
#define OPT_END_COND    2
47
 
#define OPT_TEST_COND   3
48
 
#define OPT_SCROLL_COND 4
49
 
 
50
 
 
51
 
/*******************************************************************//**
52
 
Inverts a comparison operator.
53
 
@return the equivalent operator when the order of the arguments is switched */
54
 
static
55
 
int
56
 
opt_invert_cmp_op(
57
 
/*==============*/
58
 
        int     op)     /*!< in: operator */
59
 
{
60
 
        if (op == '<') {
61
 
                return('>');
62
 
        } else if (op == '>') {
63
 
                return('<');
64
 
        } else if (op == '=') {
65
 
                return('=');
66
 
        } else if (op == PARS_LE_TOKEN) {
67
 
                return(PARS_GE_TOKEN);
68
 
        } else if (op == PARS_GE_TOKEN) {
69
 
                return(PARS_LE_TOKEN);
70
 
        } else {
71
 
                ut_error;
72
 
        }
73
 
 
74
 
        return(0);
75
 
}
76
 
 
77
 
/*******************************************************************//**
78
 
Checks if the value of an expression can be calculated BEFORE the nth table
79
 
in a join is accessed. If this is the case, it can possibly be used in an
80
 
index search for the nth table.
81
 
@return TRUE if already determined */
82
 
static
83
 
ibool
84
 
opt_check_exp_determined_before(
85
 
/*============================*/
86
 
        que_node_t*     exp,            /*!< in: expression */
87
 
        sel_node_t*     sel_node,       /*!< in: select node */
88
 
        ulint           nth_table)      /*!< in: nth table will be accessed */
89
 
{
90
 
        func_node_t*    func_node;
91
 
        sym_node_t*     sym_node;
92
 
        dict_table_t*   table;
93
 
        que_node_t*     arg;
94
 
        ulint           i;
95
 
 
96
 
        ut_ad(exp && sel_node);
97
 
 
98
 
        if (que_node_get_type(exp) == QUE_NODE_FUNC) {
99
 
                func_node = exp;
100
 
 
101
 
                arg = func_node->args;
102
 
 
103
 
                while (arg) {
104
 
                        if (!opt_check_exp_determined_before(arg, sel_node,
105
 
                                                             nth_table)) {
106
 
                                return(FALSE);
107
 
                        }
108
 
 
109
 
                        arg = que_node_get_next(arg);
110
 
                }
111
 
 
112
 
                return(TRUE);
113
 
        }
114
 
 
115
 
        ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
116
 
 
117
 
        sym_node = exp;
118
 
 
119
 
        if (sym_node->token_type != SYM_COLUMN) {
120
 
 
121
 
                return(TRUE);
122
 
        }
123
 
 
124
 
        for (i = 0; i < nth_table; i++) {
125
 
 
126
 
                table = sel_node_get_nth_plan(sel_node, i)->table;
127
 
 
128
 
                if (sym_node->table == table) {
129
 
 
130
 
                        return(TRUE);
131
 
                }
132
 
        }
133
 
 
134
 
        return(FALSE);
135
 
}
136
 
 
137
 
/*******************************************************************//**
138
 
Looks in a comparison condition if a column value is already restricted by
139
 
it BEFORE the nth table is accessed.
140
 
@return expression restricting the value of the column, or NULL if not known */
141
 
static
142
 
que_node_t*
143
 
opt_look_for_col_in_comparison_before(
144
 
/*==================================*/
145
 
        ulint           cmp_type,       /*!< in: OPT_EQUAL, OPT_COMPARISON */
146
 
        ulint           col_no,         /*!< in: column number */
147
 
        func_node_t*    search_cond,    /*!< in: comparison condition */
148
 
        sel_node_t*     sel_node,       /*!< in: select node */
149
 
        ulint           nth_table,      /*!< in: nth table in a join (a query
150
 
                                        from a single table is considered a
151
 
                                        join of 1 table) */
152
 
        ulint*          op)             /*!< out: comparison operator ('=',
153
 
                                        PARS_GE_TOKEN, ... ); this is inverted
154
 
                                        if the column appears on the right
155
 
                                        side */
156
 
{
157
 
        sym_node_t*     sym_node;
158
 
        dict_table_t*   table;
159
 
        que_node_t*     exp;
160
 
        que_node_t*     arg;
161
 
 
162
 
        ut_ad(search_cond);
163
 
 
164
 
        ut_a((search_cond->func == '<')
165
 
             || (search_cond->func == '>')
166
 
             || (search_cond->func == '=')
167
 
             || (search_cond->func == PARS_GE_TOKEN)
168
 
             || (search_cond->func == PARS_LE_TOKEN));
169
 
 
170
 
        table = sel_node_get_nth_plan(sel_node, nth_table)->table;
171
 
 
172
 
        if ((cmp_type == OPT_EQUAL) && (search_cond->func != '=')) {
173
 
 
174
 
                return(NULL);
175
 
 
176
 
        } else if ((cmp_type == OPT_COMPARISON)
177
 
                   && (search_cond->func != '<')
178
 
                   && (search_cond->func != '>')
179
 
                   && (search_cond->func != PARS_GE_TOKEN)
180
 
                   && (search_cond->func != PARS_LE_TOKEN)) {
181
 
 
182
 
                return(NULL);
183
 
        }
184
 
 
185
 
        arg = search_cond->args;
186
 
 
187
 
        if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
188
 
                sym_node = arg;
189
 
 
190
 
                if ((sym_node->token_type == SYM_COLUMN)
191
 
                    && (sym_node->table == table)
192
 
                    && (sym_node->col_no == col_no)) {
193
 
 
194
 
                        /* sym_node contains the desired column id */
195
 
 
196
 
                        /* Check if the expression on the right side of the
197
 
                        operator is already determined */
198
 
 
199
 
                        exp = que_node_get_next(arg);
200
 
 
201
 
                        if (opt_check_exp_determined_before(exp, sel_node,
202
 
                                                            nth_table)) {
203
 
                                *op = search_cond->func;
204
 
 
205
 
                                return(exp);
206
 
                        }
207
 
                }
208
 
        }
209
 
 
210
 
        exp = search_cond->args;
211
 
        arg = que_node_get_next(arg);
212
 
 
213
 
        if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
214
 
                sym_node = arg;
215
 
 
216
 
                if ((sym_node->token_type == SYM_COLUMN)
217
 
                    && (sym_node->table == table)
218
 
                    && (sym_node->col_no == col_no)) {
219
 
 
220
 
                        if (opt_check_exp_determined_before(exp, sel_node,
221
 
                                                            nth_table)) {
222
 
                                *op = opt_invert_cmp_op(search_cond->func);
223
 
 
224
 
                                return(exp);
225
 
                        }
226
 
                }
227
 
        }
228
 
 
229
 
        return(NULL);
230
 
}
231
 
 
232
 
/*******************************************************************//**
233
 
Looks in a search condition if a column value is already restricted by the
234
 
search condition BEFORE the nth table is accessed. Takes into account that
235
 
if we will fetch in an ascending order, we cannot utilize an upper limit for
236
 
a column value; in a descending order, respectively, a lower limit.
237
 
@return expression restricting the value of the column, or NULL if not known */
238
 
static
239
 
que_node_t*
240
 
opt_look_for_col_in_cond_before(
241
 
/*============================*/
242
 
        ulint           cmp_type,       /*!< in: OPT_EQUAL, OPT_COMPARISON */
243
 
        ulint           col_no,         /*!< in: column number */
244
 
        func_node_t*    search_cond,    /*!< in: search condition or NULL */
245
 
        sel_node_t*     sel_node,       /*!< in: select node */
246
 
        ulint           nth_table,      /*!< in: nth table in a join (a query
247
 
                                        from a single table is considered a
248
 
                                        join of 1 table) */
249
 
        ulint*          op)             /*!< out: comparison operator ('=',
250
 
                                        PARS_GE_TOKEN, ... ) */
251
 
{
252
 
        func_node_t*    new_cond;
253
 
        que_node_t*     exp;
254
 
 
255
 
        if (search_cond == NULL) {
256
 
 
257
 
                return(NULL);
258
 
        }
259
 
 
260
 
        ut_a(que_node_get_type(search_cond) == QUE_NODE_FUNC);
261
 
        ut_a(search_cond->func != PARS_OR_TOKEN);
262
 
        ut_a(search_cond->func != PARS_NOT_TOKEN);
263
 
 
264
 
        if (search_cond->func == PARS_AND_TOKEN) {
265
 
                new_cond = search_cond->args;
266
 
 
267
 
                exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
268
 
                                                      new_cond, sel_node,
269
 
                                                      nth_table, op);
270
 
                if (exp) {
271
 
 
272
 
                        return(exp);
273
 
                }
274
 
 
275
 
                new_cond = que_node_get_next(new_cond);
276
 
 
277
 
                exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
278
 
                                                      new_cond, sel_node,
279
 
                                                      nth_table, op);
280
 
                return(exp);
281
 
        }
282
 
 
283
 
        exp = opt_look_for_col_in_comparison_before(cmp_type, col_no,
284
 
                                                    search_cond, sel_node,
285
 
                                                    nth_table, op);
286
 
        if (exp == NULL) {
287
 
 
288
 
                return(NULL);
289
 
        }
290
 
 
291
 
        /* If we will fetch in an ascending order, we cannot utilize an upper
292
 
        limit for a column value; in a descending order, respectively, a lower
293
 
        limit */
294
 
 
295
 
        if (sel_node->asc && ((*op == '<') || (*op == PARS_LE_TOKEN))) {
296
 
 
297
 
                return(NULL);
298
 
 
299
 
        } else if (!sel_node->asc
300
 
                   && ((*op == '>') || (*op == PARS_GE_TOKEN))) {
301
 
 
302
 
                return(NULL);
303
 
        }
304
 
 
305
 
        return(exp);
306
 
}
307
 
 
308
 
/*******************************************************************//**
309
 
Calculates the goodness for an index according to a select node. The
310
 
goodness is 4 times the number of first fields in index whose values we
311
 
already know exactly in the query. If we have a comparison condition for
312
 
an additional field, 2 point are added. If the index is unique, and we know
313
 
all the unique fields for the index we add 1024 points. For a clustered index
314
 
we add 1 point.
315
 
@return goodness */
316
 
static
317
 
ulint
318
 
opt_calc_index_goodness(
319
 
/*====================*/
320
 
        dict_index_t*   index,          /*!< in: index */
321
 
        sel_node_t*     sel_node,       /*!< in: parsed select node */
322
 
        ulint           nth_table,      /*!< in: nth table in a join */
323
 
        que_node_t**    index_plan,     /*!< in/out: comparison expressions for
324
 
                                        this index */
325
 
        ulint*          last_op)        /*!< out: last comparison operator, if
326
 
                                        goodness > 1 */
327
 
{
328
 
        que_node_t*     exp;
329
 
        ulint           goodness;
330
 
        ulint           n_fields;
331
 
        ulint           col_no;
332
 
        ulint           op;
333
 
        ulint           j;
334
 
 
335
 
        goodness = 0;
336
 
 
337
 
        /* Note that as higher level node pointers in the B-tree contain
338
 
        page addresses as the last field, we must not put more fields in
339
 
        the search tuple than dict_index_get_n_unique_in_tree(index); see
340
 
        the note in btr_cur_search_to_nth_level. */
341
 
 
342
 
        n_fields = dict_index_get_n_unique_in_tree(index);
343
 
 
344
 
        for (j = 0; j < n_fields; j++) {
345
 
 
346
 
                col_no = dict_index_get_nth_col_no(index, j);
347
 
 
348
 
                exp = opt_look_for_col_in_cond_before(
349
 
                        OPT_EQUAL, col_no, sel_node->search_cond,
350
 
                        sel_node, nth_table, &op);
351
 
                if (exp) {
352
 
                        /* The value for this column is exactly known already
353
 
                        at this stage of the join */
354
 
 
355
 
                        index_plan[j] = exp;
356
 
                        *last_op = op;
357
 
                        goodness += 4;
358
 
                } else {
359
 
                        /* Look for non-equality comparisons */
360
 
 
361
 
                        exp = opt_look_for_col_in_cond_before(
362
 
                                OPT_COMPARISON, col_no, sel_node->search_cond,
363
 
                                sel_node, nth_table, &op);
364
 
                        if (exp) {
365
 
                                index_plan[j] = exp;
366
 
                                *last_op = op;
367
 
                                goodness += 2;
368
 
                        }
369
 
 
370
 
                        break;
371
 
                }
372
 
        }
373
 
 
374
 
        if (goodness >= 4 * dict_index_get_n_unique(index)) {
375
 
                goodness += 1024;
376
 
 
377
 
                if (dict_index_is_clust(index)) {
378
 
 
379
 
                        goodness += 1024;
380
 
                }
381
 
        }
382
 
 
383
 
        /* We have to test for goodness here, as last_op may note be set */
384
 
        if (goodness && dict_index_is_clust(index)) {
385
 
 
386
 
                goodness++;
387
 
        }
388
 
 
389
 
        return(goodness);
390
 
}
391
 
 
392
 
/*******************************************************************//**
393
 
Calculates the number of matched fields based on an index goodness.
394
 
@return number of excatly or partially matched fields */
395
 
UNIV_INLINE
396
 
ulint
397
 
opt_calc_n_fields_from_goodness(
398
 
/*============================*/
399
 
        ulint   goodness)       /*!< in: goodness */
400
 
{
401
 
        return(((goodness % 1024) + 2) / 4);
402
 
}
403
 
 
404
 
/*******************************************************************//**
405
 
Converts a comparison operator to the corresponding search mode PAGE_CUR_GE,
406
 
...
407
 
@return search mode */
408
 
UNIV_INLINE
409
 
ulint
410
 
opt_op_to_search_mode(
411
 
/*==================*/
412
 
        ibool   asc,    /*!< in: TRUE if the rows should be fetched in an
413
 
                        ascending order */
414
 
        ulint   op)     /*!< in: operator '=', PARS_GE_TOKEN, ... */
415
 
{
416
 
        if (op == '=') {
417
 
                if (asc) {
418
 
                        return(PAGE_CUR_GE);
419
 
                } else {
420
 
                        return(PAGE_CUR_LE);
421
 
                }
422
 
        } else if (op == '<') {
423
 
                ut_a(!asc);
424
 
                return(PAGE_CUR_L);
425
 
        } else if (op == '>') {
426
 
                ut_a(asc);
427
 
                return(PAGE_CUR_G);
428
 
        } else if (op == PARS_GE_TOKEN) {
429
 
                ut_a(asc);
430
 
                return(PAGE_CUR_GE);
431
 
        } else if (op == PARS_LE_TOKEN) {
432
 
                ut_a(!asc);
433
 
                return(PAGE_CUR_LE);
434
 
        } else {
435
 
                ut_error;
436
 
        }
437
 
 
438
 
        return(0);
439
 
}
440
 
 
441
 
/*******************************************************************//**
442
 
Determines if a node is an argument node of a function node.
443
 
@return TRUE if is an argument */
444
 
static
445
 
ibool
446
 
opt_is_arg(
447
 
/*=======*/
448
 
        que_node_t*     arg_node,       /*!< in: possible argument node */
449
 
        func_node_t*    func_node)      /*!< in: function node */
450
 
{
451
 
        que_node_t*     arg;
452
 
 
453
 
        arg = func_node->args;
454
 
 
455
 
        while (arg) {
456
 
                if (arg == arg_node) {
457
 
 
458
 
                        return(TRUE);
459
 
                }
460
 
 
461
 
                arg = que_node_get_next(arg);
462
 
        }
463
 
 
464
 
        return(FALSE);
465
 
}
466
 
 
467
 
/*******************************************************************//**
468
 
Decides if the fetching of rows should be made in a descending order, and
469
 
also checks that the chosen query plan produces a result which satisfies
470
 
the order-by. */
471
 
static
472
 
void
473
 
opt_check_order_by(
474
 
/*===============*/
475
 
        sel_node_t*     sel_node)       /*!< in: select node; asserts an error
476
 
                                        if the plan does not agree with the
477
 
                                        order-by */
478
 
{
479
 
        order_node_t*   order_node;
480
 
        dict_table_t*   order_table;
481
 
        ulint           order_col_no;
482
 
        plan_t*         plan;
483
 
        ulint           i;
484
 
 
485
 
        if (!sel_node->order_by) {
486
 
 
487
 
                return;
488
 
        }
489
 
 
490
 
        order_node = sel_node->order_by;
491
 
        order_col_no = order_node->column->col_no;
492
 
        order_table = order_node->column->table;
493
 
 
494
 
        /* If there is an order-by clause, the first non-exactly matched field
495
 
        in the index used for the last table in the table list should be the
496
 
        column defined in the order-by clause, and for all the other tables
497
 
        we should get only at most a single row, otherwise we cannot presently
498
 
        calculate the order-by, as we have no sort utility */
499
 
 
500
 
        for (i = 0; i < sel_node->n_tables; i++) {
501
 
 
502
 
                plan = sel_node_get_nth_plan(sel_node, i);
503
 
 
504
 
                if (i < sel_node->n_tables - 1) {
505
 
                        ut_a(dict_index_get_n_unique(plan->index)
506
 
                             <= plan->n_exact_match);
507
 
                } else {
508
 
                        ut_a(plan->table == order_table);
509
 
 
510
 
                        ut_a((dict_index_get_n_unique(plan->index)
511
 
                              <= plan->n_exact_match)
512
 
                             || (dict_index_get_nth_col_no(plan->index,
513
 
                                                           plan->n_exact_match)
514
 
                                 == order_col_no));
515
 
                }
516
 
        }
517
 
}
518
 
 
519
 
/*******************************************************************//**
520
 
Optimizes a select. Decides which indexes to tables to use. The tables
521
 
are accessed in the order that they were written to the FROM part in the
522
 
select statement. */
523
 
static
524
 
void
525
 
opt_search_plan_for_table(
526
 
/*======================*/
527
 
        sel_node_t*     sel_node,       /*!< in: parsed select node */
528
 
        ulint           i,              /*!< in: this is the ith table */
529
 
        dict_table_t*   table)          /*!< in: table */
530
 
{
531
 
        plan_t*         plan;
532
 
        dict_index_t*   index;
533
 
        dict_index_t*   best_index;
534
 
        ulint           n_fields;
535
 
        ulint           goodness;
536
 
        ulint           last_op         = 75946965;     /* Eliminate a Purify
537
 
                                                        warning */
538
 
        ulint           best_goodness;
539
 
        ulint           best_last_op = 0; /* remove warning */
540
 
        que_node_t*     index_plan[256];
541
 
        que_node_t*     best_index_plan[256];
542
 
 
543
 
        plan = sel_node_get_nth_plan(sel_node, i);
544
 
 
545
 
        plan->table = table;
546
 
        plan->asc = sel_node->asc;
547
 
        plan->pcur_is_open = FALSE;
548
 
        plan->cursor_at_end = FALSE;
549
 
 
550
 
        /* Calculate goodness for each index of the table */
551
 
 
552
 
        index = dict_table_get_first_index(table);
553
 
        best_index = index; /* Eliminate compiler warning */
554
 
        best_goodness = 0;
555
 
 
556
 
        /* should be do ... until ? comment by Jani */
557
 
        while (index) {
558
 
                goodness = opt_calc_index_goodness(index, sel_node, i,
559
 
                                                   index_plan, &last_op);
560
 
                if (goodness > best_goodness) {
561
 
 
562
 
                        best_index = index;
563
 
                        best_goodness = goodness;
564
 
                        n_fields = opt_calc_n_fields_from_goodness(goodness);
565
 
 
566
 
                        ut_memcpy(best_index_plan, index_plan,
567
 
                                  n_fields * sizeof(void*));
568
 
                        best_last_op = last_op;
569
 
                }
570
 
 
571
 
                index = dict_table_get_next_index(index);
572
 
        }
573
 
 
574
 
        plan->index = best_index;
575
 
 
576
 
        n_fields = opt_calc_n_fields_from_goodness(best_goodness);
577
 
 
578
 
        if (n_fields == 0) {
579
 
                plan->tuple = NULL;
580
 
                plan->n_exact_match = 0;
581
 
        } else {
582
 
                plan->tuple = dtuple_create(pars_sym_tab_global->heap,
583
 
                                            n_fields);
584
 
                dict_index_copy_types(plan->tuple, plan->index, n_fields);
585
 
 
586
 
                plan->tuple_exps = mem_heap_alloc(pars_sym_tab_global->heap,
587
 
                                                  n_fields * sizeof(void*));
588
 
 
589
 
                ut_memcpy(plan->tuple_exps, best_index_plan,
590
 
                          n_fields * sizeof(void*));
591
 
                if (best_last_op == '=') {
592
 
                        plan->n_exact_match = n_fields;
593
 
                } else {
594
 
                        plan->n_exact_match = n_fields - 1;
595
 
                }
596
 
 
597
 
                plan->mode = opt_op_to_search_mode(sel_node->asc,
598
 
                                                   best_last_op);
599
 
        }
600
 
 
601
 
        if (dict_index_is_clust(best_index)
602
 
            && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) {
603
 
 
604
 
                plan->unique_search = TRUE;
605
 
        } else {
606
 
                plan->unique_search = FALSE;
607
 
        }
608
 
 
609
 
        plan->old_vers_heap = NULL;
610
 
 
611
 
        btr_pcur_init(&(plan->pcur));
612
 
        btr_pcur_init(&(plan->clust_pcur));
613
 
}
614
 
 
615
 
/*******************************************************************//**
616
 
Looks at a comparison condition and decides if it can, and need, be tested for
617
 
a table AFTER the table has been accessed.
618
 
@return OPT_NOT_COND if not for this table, else OPT_END_COND,
619
 
OPT_TEST_COND, or OPT_SCROLL_COND, where the last means that the
620
 
condition need not be tested, except when scroll cursors are used */
621
 
static
622
 
ulint
623
 
opt_classify_comparison(
624
 
/*====================*/
625
 
        sel_node_t*     sel_node,       /*!< in: select node */
626
 
        ulint           i,              /*!< in: ith table in the join */
627
 
        func_node_t*    cond)           /*!< in: comparison condition */
628
 
{
629
 
        plan_t* plan;
630
 
        ulint   n_fields;
631
 
        ulint   op;
632
 
        ulint   j;
633
 
 
634
 
        ut_ad(cond && sel_node);
635
 
 
636
 
        plan = sel_node_get_nth_plan(sel_node, i);
637
 
 
638
 
        /* Check if the condition is determined after the ith table has been
639
 
        accessed, but not after the i - 1:th */
640
 
 
641
 
        if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) {
642
 
 
643
 
                return(OPT_NOT_COND);
644
 
        }
645
 
 
646
 
        if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) {
647
 
 
648
 
                return(OPT_NOT_COND);
649
 
        }
650
 
 
651
 
        /* If the condition is an exact match condition used in constructing
652
 
        the search tuple, it is classified as OPT_END_COND */
653
 
 
654
 
        if (plan->tuple) {
655
 
                n_fields = dtuple_get_n_fields(plan->tuple);
656
 
        } else {
657
 
                n_fields = 0;
658
 
        }
659
 
 
660
 
        for (j = 0; j < plan->n_exact_match; j++) {
661
 
 
662
 
                if (opt_is_arg(plan->tuple_exps[j], cond)) {
663
 
 
664
 
                        return(OPT_END_COND);
665
 
                }
666
 
        }
667
 
 
668
 
        /* If the condition is an non-exact match condition used in
669
 
        constructing the search tuple, it is classified as OPT_SCROLL_COND.
670
 
        When the cursor is positioned, and if a non-scroll cursor is used,
671
 
        there is no need to test this condition; if a scroll cursor is used
672
 
        the testing is necessary when the cursor is reversed. */
673
 
 
674
 
        if ((n_fields > plan->n_exact_match)
675
 
            && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) {
676
 
 
677
 
                return(OPT_SCROLL_COND);
678
 
        }
679
 
 
680
 
        /* If the condition is a non-exact match condition on the first field
681
 
        in index for which there is no exact match, and it limits the search
682
 
        range from the opposite side of the search tuple already BEFORE we
683
 
        access the table, it is classified as OPT_END_COND */
684
 
 
685
 
        if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match)
686
 
            && opt_look_for_col_in_comparison_before(
687
 
                    OPT_COMPARISON,
688
 
                    dict_index_get_nth_col_no(plan->index,
689
 
                                              plan->n_exact_match),
690
 
                    cond, sel_node, i, &op)) {
691
 
 
692
 
                if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) {
693
 
 
694
 
                        return(OPT_END_COND);
695
 
                }
696
 
 
697
 
                if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) {
698
 
 
699
 
                        return(OPT_END_COND);
700
 
                }
701
 
        }
702
 
 
703
 
        /* Otherwise, cond is classified as OPT_TEST_COND */
704
 
 
705
 
        return(OPT_TEST_COND);
706
 
}
707
 
 
708
 
/*******************************************************************//**
709
 
Recursively looks for test conditions for a table in a join. */
710
 
static
711
 
void
712
 
opt_find_test_conds(
713
 
/*================*/
714
 
        sel_node_t*     sel_node,       /*!< in: select node */
715
 
        ulint           i,              /*!< in: ith table in the join */
716
 
        func_node_t*    cond)           /*!< in: conjunction of search
717
 
                                        conditions or NULL */
718
 
{
719
 
        func_node_t*    new_cond;
720
 
        ulint           class;
721
 
        plan_t*         plan;
722
 
 
723
 
        if (cond == NULL) {
724
 
 
725
 
                return;
726
 
        }
727
 
 
728
 
        if (cond->func == PARS_AND_TOKEN) {
729
 
                new_cond = cond->args;
730
 
 
731
 
                opt_find_test_conds(sel_node, i, new_cond);
732
 
 
733
 
                new_cond = que_node_get_next(new_cond);
734
 
 
735
 
                opt_find_test_conds(sel_node, i, new_cond);
736
 
 
737
 
                return;
738
 
        }
739
 
 
740
 
        plan = sel_node_get_nth_plan(sel_node, i);
741
 
 
742
 
        class = opt_classify_comparison(sel_node, i, cond);
743
 
 
744
 
        if (class == OPT_END_COND) {
745
 
                UT_LIST_ADD_LAST(cond_list, plan->end_conds, cond);
746
 
 
747
 
        } else if (class == OPT_TEST_COND) {
748
 
                UT_LIST_ADD_LAST(cond_list, plan->other_conds, cond);
749
 
 
750
 
        }
751
 
}
752
 
 
753
 
/*******************************************************************//**
754
 
Normalizes a list of comparison conditions so that a column of the table
755
 
appears on the left side of the comparison if possible. This is accomplished
756
 
by switching the arguments of the operator. */
757
 
static
758
 
void
759
 
opt_normalize_cmp_conds(
760
 
/*====================*/
761
 
        func_node_t*    cond,   /*!< in: first in a list of comparison
762
 
                                conditions, or NULL */
763
 
        dict_table_t*   table)  /*!< in: table */
764
 
{
765
 
        que_node_t*     arg1;
766
 
        que_node_t*     arg2;
767
 
        sym_node_t*     sym_node;
768
 
 
769
 
        while (cond) {
770
 
                arg1 = cond->args;
771
 
                arg2 = que_node_get_next(arg1);
772
 
 
773
 
                if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) {
774
 
 
775
 
                        sym_node = arg2;
776
 
 
777
 
                        if ((sym_node->token_type == SYM_COLUMN)
778
 
                            && (sym_node->table == table)) {
779
 
 
780
 
                                /* Switch the order of the arguments */
781
 
 
782
 
                                cond->args = arg2;
783
 
                                que_node_list_add_last(NULL, arg2);
784
 
                                que_node_list_add_last(arg2, arg1);
785
 
 
786
 
                                /* Invert the operator */
787
 
                                cond->func = opt_invert_cmp_op(cond->func);
788
 
                        }
789
 
                }
790
 
 
791
 
                cond = UT_LIST_GET_NEXT(cond_list, cond);
792
 
        }
793
 
}
794
 
 
795
 
/*******************************************************************//**
796
 
Finds out the search condition conjuncts we can, and need, to test as the ith
797
 
table in a join is accessed. The search tuple can eliminate the need to test
798
 
some conjuncts. */
799
 
static
800
 
void
801
 
opt_determine_and_normalize_test_conds(
802
 
/*===================================*/
803
 
        sel_node_t*     sel_node,       /*!< in: select node */
804
 
        ulint           i)              /*!< in: ith table in the join */
805
 
{
806
 
        plan_t* plan;
807
 
 
808
 
        plan = sel_node_get_nth_plan(sel_node, i);
809
 
 
810
 
        UT_LIST_INIT(plan->end_conds);
811
 
        UT_LIST_INIT(plan->other_conds);
812
 
 
813
 
        /* Recursively go through the conjuncts and classify them */
814
 
 
815
 
        opt_find_test_conds(sel_node, i, sel_node->search_cond);
816
 
 
817
 
        opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds),
818
 
                                plan->table);
819
 
 
820
 
        ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match);
821
 
}
822
 
 
823
 
/*******************************************************************//**
824
 
Looks for occurrences of the columns of the table in the query subgraph and
825
 
adds them to the list of columns if an occurrence of the same column does not
826
 
already exist in the list. If the column is already in the list, puts a value
827
 
indirection to point to the occurrence in the column list, except if the
828
 
column occurrence we are looking at is in the column list, in which case
829
 
nothing is done. */
830
 
UNIV_INTERN
831
 
void
832
 
opt_find_all_cols(
833
 
/*==============*/
834
 
        ibool           copy_val,       /*!< in: if TRUE, new found columns are
835
 
                                        added as columns to copy */
836
 
        dict_index_t*   index,          /*!< in: index of the table to use */
837
 
        sym_node_list_t* col_list,      /*!< in: base node of a list where
838
 
                                        to add new found columns */
839
 
        plan_t*         plan,           /*!< in: plan or NULL */
840
 
        que_node_t*     exp)            /*!< in: expression or condition or
841
 
                                        NULL */
842
 
{
843
 
        func_node_t*    func_node;
844
 
        que_node_t*     arg;
845
 
        sym_node_t*     sym_node;
846
 
        sym_node_t*     col_node;
847
 
        ulint           col_pos;
848
 
 
849
 
        if (exp == NULL) {
850
 
 
851
 
                return;
852
 
        }
853
 
 
854
 
        if (que_node_get_type(exp) == QUE_NODE_FUNC) {
855
 
                func_node = exp;
856
 
 
857
 
                arg = func_node->args;
858
 
 
859
 
                while (arg) {
860
 
                        opt_find_all_cols(copy_val, index, col_list, plan,
861
 
                                          arg);
862
 
                        arg = que_node_get_next(arg);
863
 
                }
864
 
 
865
 
                return;
866
 
        }
867
 
 
868
 
        ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
869
 
 
870
 
        sym_node = exp;
871
 
 
872
 
        if (sym_node->token_type != SYM_COLUMN) {
873
 
 
874
 
                return;
875
 
        }
876
 
 
877
 
        if (sym_node->table != index->table) {
878
 
 
879
 
                return;
880
 
        }
881
 
 
882
 
        /* Look for an occurrence of the same column in the plan column
883
 
        list */
884
 
 
885
 
        col_node = UT_LIST_GET_FIRST(*col_list);
886
 
 
887
 
        while (col_node) {
888
 
                if (col_node->col_no == sym_node->col_no) {
889
 
 
890
 
                        if (col_node == sym_node) {
891
 
                                /* sym_node was already in a list: do
892
 
                                nothing */
893
 
 
894
 
                                return;
895
 
                        }
896
 
 
897
 
                        /* Put an indirection */
898
 
                        sym_node->indirection = col_node;
899
 
                        sym_node->alias = col_node;
900
 
 
901
 
                        return;
902
 
                }
903
 
 
904
 
                col_node = UT_LIST_GET_NEXT(col_var_list, col_node);
905
 
        }
906
 
 
907
 
        /* The same column did not occur in the list: add it */
908
 
 
909
 
        UT_LIST_ADD_LAST(col_var_list, *col_list, sym_node);
910
 
 
911
 
        sym_node->copy_val = copy_val;
912
 
 
913
 
        /* Fill in the field_no fields in sym_node */
914
 
 
915
 
        sym_node->field_nos[SYM_CLUST_FIELD_NO] = dict_index_get_nth_col_pos(
916
 
                dict_table_get_first_index(index->table), sym_node->col_no);
917
 
        if (!dict_index_is_clust(index)) {
918
 
 
919
 
                ut_a(plan);
920
 
 
921
 
                col_pos = dict_index_get_nth_col_pos(index, sym_node->col_no);
922
 
 
923
 
                if (col_pos == ULINT_UNDEFINED) {
924
 
 
925
 
                        plan->must_get_clust = TRUE;
926
 
                }
927
 
 
928
 
                sym_node->field_nos[SYM_SEC_FIELD_NO] = col_pos;
929
 
        }
930
 
}
931
 
 
932
 
/*******************************************************************//**
933
 
Looks for occurrences of the columns of the table in conditions which are
934
 
not yet determined AFTER the join operation has fetched a row in the ith
935
 
table. The values for these column must be copied to dynamic memory for
936
 
later use. */
937
 
static
938
 
void
939
 
opt_find_copy_cols(
940
 
/*===============*/
941
 
        sel_node_t*     sel_node,       /*!< in: select node */
942
 
        ulint           i,              /*!< in: ith table in the join */
943
 
        func_node_t*    search_cond)    /*!< in: search condition or NULL */
944
 
{
945
 
        func_node_t*    new_cond;
946
 
        plan_t*         plan;
947
 
 
948
 
        if (search_cond == NULL) {
949
 
 
950
 
                return;
951
 
        }
952
 
 
953
 
        ut_ad(que_node_get_type(search_cond) == QUE_NODE_FUNC);
954
 
 
955
 
        if (search_cond->func == PARS_AND_TOKEN) {
956
 
                new_cond = search_cond->args;
957
 
 
958
 
                opt_find_copy_cols(sel_node, i, new_cond);
959
 
 
960
 
                new_cond = que_node_get_next(new_cond);
961
 
 
962
 
                opt_find_copy_cols(sel_node, i, new_cond);
963
 
 
964
 
                return;
965
 
        }
966
 
 
967
 
        if (!opt_check_exp_determined_before(search_cond, sel_node, i + 1)) {
968
 
 
969
 
                /* Any ith table columns occurring in search_cond should be
970
 
                copied, as this condition cannot be tested already on the
971
 
                fetch from the ith table */
972
 
 
973
 
                plan = sel_node_get_nth_plan(sel_node, i);
974
 
 
975
 
                opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
976
 
                                  search_cond);
977
 
        }
978
 
}
979
 
 
980
 
/*******************************************************************//**
981
 
Classifies the table columns according to whether we use the column only while
982
 
holding the latch on the page, or whether we have to copy the column value to
983
 
dynamic memory. Puts the first occurrence of a column to either list in the
984
 
plan node, and puts indirections to later occurrences of the column. */
985
 
static
986
 
void
987
 
opt_classify_cols(
988
 
/*==============*/
989
 
        sel_node_t*     sel_node,       /*!< in: select node */
990
 
        ulint           i)              /*!< in: ith table in the join */
991
 
{
992
 
        plan_t*         plan;
993
 
        que_node_t*     exp;
994
 
 
995
 
        plan = sel_node_get_nth_plan(sel_node, i);
996
 
 
997
 
        /* The final value of the following field will depend on the
998
 
        environment of the select statement: */
999
 
 
1000
 
        plan->must_get_clust = FALSE;
1001
 
 
1002
 
        UT_LIST_INIT(plan->columns);
1003
 
 
1004
 
        /* All select list columns should be copied: therefore TRUE as the
1005
 
        first argument */
1006
 
 
1007
 
        exp = sel_node->select_list;
1008
 
 
1009
 
        while (exp) {
1010
 
                opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
1011
 
                                  exp);
1012
 
                exp = que_node_get_next(exp);
1013
 
        }
1014
 
 
1015
 
        opt_find_copy_cols(sel_node, i, sel_node->search_cond);
1016
 
 
1017
 
        /* All remaining columns in the search condition are temporary
1018
 
        columns: therefore FALSE */
1019
 
 
1020
 
        opt_find_all_cols(FALSE, plan->index, &(plan->columns), plan,
1021
 
                          sel_node->search_cond);
1022
 
}
1023
 
 
1024
 
/*******************************************************************//**
1025
 
Fills in the info in plan which is used in accessing a clustered index
1026
 
record. The columns must already be classified for the plan node. */
1027
 
static
1028
 
void
1029
 
opt_clust_access(
1030
 
/*=============*/
1031
 
        sel_node_t*     sel_node,       /*!< in: select node */
1032
 
        ulint           n)              /*!< in: nth table in select */
1033
 
{
1034
 
        plan_t*         plan;
1035
 
        dict_table_t*   table;
1036
 
        dict_index_t*   clust_index;
1037
 
        dict_index_t*   index;
1038
 
        mem_heap_t*     heap;
1039
 
        ulint           n_fields;
1040
 
        ulint           pos;
1041
 
        ulint           i;
1042
 
 
1043
 
        plan = sel_node_get_nth_plan(sel_node, n);
1044
 
 
1045
 
        index = plan->index;
1046
 
 
1047
 
        /* The final value of the following field depends on the environment
1048
 
        of the select statement: */
1049
 
 
1050
 
        plan->no_prefetch = FALSE;
1051
 
 
1052
 
        if (dict_index_is_clust(index)) {
1053
 
                plan->clust_map = NULL;
1054
 
                plan->clust_ref = NULL;
1055
 
 
1056
 
                return;
1057
 
        }
1058
 
 
1059
 
        table = index->table;
1060
 
 
1061
 
        clust_index = dict_table_get_first_index(table);
1062
 
 
1063
 
        n_fields = dict_index_get_n_unique(clust_index);
1064
 
 
1065
 
        heap = pars_sym_tab_global->heap;
1066
 
 
1067
 
        plan->clust_ref = dtuple_create(heap, n_fields);
1068
 
 
1069
 
        dict_index_copy_types(plan->clust_ref, clust_index, n_fields);
1070
 
 
1071
 
        plan->clust_map = mem_heap_alloc(heap, n_fields * sizeof(ulint));
1072
 
 
1073
 
        for (i = 0; i < n_fields; i++) {
1074
 
                pos = dict_index_get_nth_field_pos(index, clust_index, i);
1075
 
 
1076
 
                ut_a(pos != ULINT_UNDEFINED);
1077
 
 
1078
 
                /* We optimize here only queries to InnoDB's internal system
1079
 
                tables, and they should not contain column prefix indexes. */
1080
 
 
1081
 
                if (dict_index_get_nth_field(index, pos)->prefix_len != 0
1082
 
                    || dict_index_get_nth_field(clust_index, i)
1083
 
                    ->prefix_len != 0) {
1084
 
                        fprintf(stderr,
1085
 
                                "InnoDB: Error in pars0opt.c:"
1086
 
                                " table %s has prefix_len != 0\n",
1087
 
                                index->table_name);
1088
 
                }
1089
 
 
1090
 
                *(plan->clust_map + i) = pos;
1091
 
 
1092
 
                ut_ad(pos != ULINT_UNDEFINED);
1093
 
        }
1094
 
}
1095
 
 
1096
 
/*******************************************************************//**
1097
 
Optimizes a select. Decides which indexes to tables to use. The tables
1098
 
are accessed in the order that they were written to the FROM part in the
1099
 
select statement. */
1100
 
UNIV_INTERN
1101
 
void
1102
 
opt_search_plan(
1103
 
/*============*/
1104
 
        sel_node_t*     sel_node)       /*!< in: parsed select node */
1105
 
{
1106
 
        sym_node_t*     table_node;
1107
 
        dict_table_t*   table;
1108
 
        order_node_t*   order_by;
1109
 
        ulint           i;
1110
 
 
1111
 
        sel_node->plans = mem_heap_alloc(pars_sym_tab_global->heap,
1112
 
                                         sel_node->n_tables * sizeof(plan_t));
1113
 
 
1114
 
        /* Analyze the search condition to find out what we know at each
1115
 
        join stage about the conditions that the columns of a table should
1116
 
        satisfy */
1117
 
 
1118
 
        table_node = sel_node->table_list;
1119
 
 
1120
 
        if (sel_node->order_by == NULL) {
1121
 
                sel_node->asc = TRUE;
1122
 
        } else {
1123
 
                order_by = sel_node->order_by;
1124
 
 
1125
 
                sel_node->asc = order_by->asc;
1126
 
        }
1127
 
 
1128
 
        for (i = 0; i < sel_node->n_tables; i++) {
1129
 
 
1130
 
                table = table_node->table;
1131
 
 
1132
 
                /* Choose index through which to access the table */
1133
 
 
1134
 
                opt_search_plan_for_table(sel_node, i, table);
1135
 
 
1136
 
                /* Determine the search condition conjuncts we can test at
1137
 
                this table; normalize the end conditions */
1138
 
 
1139
 
                opt_determine_and_normalize_test_conds(sel_node, i);
1140
 
 
1141
 
                table_node = que_node_get_next(table_node);
1142
 
        }
1143
 
 
1144
 
        table_node = sel_node->table_list;
1145
 
 
1146
 
        for (i = 0; i < sel_node->n_tables; i++) {
1147
 
 
1148
 
                /* Classify the table columns into those we only need to access
1149
 
                but not copy, and to those we must copy to dynamic memory */
1150
 
 
1151
 
                opt_classify_cols(sel_node, i);
1152
 
 
1153
 
                /* Calculate possible info for accessing the clustered index
1154
 
                record */
1155
 
 
1156
 
                opt_clust_access(sel_node, i);
1157
 
 
1158
 
                table_node = que_node_get_next(table_node);
1159
 
        }
1160
 
 
1161
 
        /* Check that the plan obeys a possible order-by clause: if not,
1162
 
        an assertion error occurs */
1163
 
 
1164
 
        opt_check_order_by(sel_node);
1165
 
 
1166
 
#ifdef UNIV_SQL_DEBUG
1167
 
        opt_print_query_plan(sel_node);
1168
 
#endif
1169
 
}
1170
 
 
1171
 
/********************************************************************//**
1172
 
Prints info of a query plan. */
1173
 
UNIV_INTERN
1174
 
void
1175
 
opt_print_query_plan(
1176
 
/*=================*/
1177
 
        sel_node_t*     sel_node)       /*!< in: select node */
1178
 
{
1179
 
        plan_t* plan;
1180
 
        ulint   n_fields;
1181
 
        ulint   i;
1182
 
 
1183
 
        fputs("QUERY PLAN FOR A SELECT NODE\n", stderr);
1184
 
 
1185
 
        fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr);
1186
 
 
1187
 
        if (sel_node->set_x_locks) {
1188
 
                fputs("sets row x-locks; ", stderr);
1189
 
                ut_a(sel_node->row_lock_mode == LOCK_X);
1190
 
                ut_a(!sel_node->consistent_read);
1191
 
        } else if (sel_node->consistent_read) {
1192
 
                fputs("consistent read; ", stderr);
1193
 
        } else {
1194
 
                ut_a(sel_node->row_lock_mode == LOCK_S);
1195
 
                fputs("sets row s-locks; ", stderr);
1196
 
        }
1197
 
 
1198
 
        putc('\n', stderr);
1199
 
 
1200
 
        for (i = 0; i < sel_node->n_tables; i++) {
1201
 
                plan = sel_node_get_nth_plan(sel_node, i);
1202
 
 
1203
 
                if (plan->tuple) {
1204
 
                        n_fields = dtuple_get_n_fields(plan->tuple);
1205
 
                } else {
1206
 
                        n_fields = 0;
1207
 
                }
1208
 
 
1209
 
                fputs("Table ", stderr);
1210
 
                dict_index_name_print(stderr, NULL, plan->index);
1211
 
                fprintf(stderr,"; exact m. %lu, match %lu, end conds %lu\n",
1212
 
                        (unsigned long) plan->n_exact_match,
1213
 
                        (unsigned long) n_fields,
1214
 
                        (unsigned long) UT_LIST_GET_LEN(plan->end_conds));
1215
 
        }
1216
 
}