← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Monty Taylor
  • Date: 2009-09-30 07:01:32 UTC
  • mto: This revision was merged to the branch mainline in revision 1184.
  • Revision ID: mordred@inaugust.com-20090930070132-b1ol1xu1rpajdddy
Small namespace cleanup.

Show diffs side-by-side

added added

removed removed

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