← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

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 (index->type & DICT_CLUSTERED) {
 
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 && index->type & DICT_CLUSTERED) {
 
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 ((best_index->type & DICT_CLUSTERED)
 
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
 
 
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 (!(index->type & DICT_CLUSTERED)) {
 
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 (index->type & DICT_CLUSTERED) {
 
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
 
 
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
 
 
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
}