← Back to branch summary

~ubuntu-branches/ubuntu/trusty/drizzle/trusty

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Monty Taylor
  • Date: 2010-03-18 12:12:31 UTC
  • Revision ID: james.westby@ubuntu.com-20100318121231-k6g1xe6cshbwa0f8
Tags: upstream-2010.03.1347
Import upstream version 2010.03.1347

Show diffs side-by-side

added added

removed removed

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