~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to sql/opt_sum.cc

  • 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:
 
1
/* Copyright (C) 2000-2003 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
 
 
17
/**
 
18
  @file
 
19
 
 
20
  Optimising of MIN(), MAX() and COUNT(*) queries without 'group by' clause
 
21
  by replacing the aggregate expression with a constant.  
 
22
 
 
23
  Given a table with a compound key on columns (a,b,c), the following
 
24
  types of queries are optimised (assuming the table handler supports
 
25
  the required methods)
 
26
 
 
27
  @verbatim
 
28
  SELECT COUNT(*) FROM t1[,t2,t3,...]
 
29
  SELECT MIN(b) FROM t1 WHERE a=const
 
30
  SELECT MAX(c) FROM t1 WHERE a=const AND b=const
 
31
  SELECT MAX(b) FROM t1 WHERE a=const AND b<const
 
32
  SELECT MIN(b) FROM t1 WHERE a=const AND b>const
 
33
  SELECT MIN(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
 
34
  SELECT MAX(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
 
35
  @endverbatim
 
36
 
 
37
  Instead of '<' one can use '<=', '>', '>=' and '=' as well.
 
38
  Instead of 'a=const' the condition 'a IS NULL' can be used.
 
39
 
 
40
  If all selected fields are replaced then we will also remove all
 
41
  involved tables and return the answer without any join. Thus, the
 
42
  following query will be replaced with a row of two constants:
 
43
  @verbatim
 
44
  SELECT MAX(b), MIN(d) FROM t1,t2 
 
45
    WHERE a=const AND b<const AND d>const
 
46
  @endverbatim
 
47
  (assuming a index for column d of table t2 is defined)
 
48
*/
 
49
 
 
50
#include "mysql_priv.h"
 
51
#include "sql_select.h"
 
52
 
 
53
static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref, Field* field,
 
54
                                COND *cond, uint *range_fl,
 
55
                                uint *key_prefix_length);
 
56
static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
 
57
                            COND *cond, uint range_fl, uint prefix_len);
 
58
static int maxmin_in_range(bool max_fl, Field* field, COND *cond);
 
59
 
 
60
 
 
61
/*
 
62
  Get exact count of rows in all tables
 
63
 
 
64
  SYNOPSIS
 
65
    get_exact_records()
 
66
    tables              List of tables
 
67
 
 
68
  NOTES
 
69
    When this is called, we know all table handlers supports HA_HAS_RECORDS
 
70
    or HA_STATS_RECORDS_IS_EXACT
 
71
 
 
72
  RETURN
 
73
    ULONGLONG_MAX       Error: Could not calculate number of rows
 
74
    #                   Multiplication of number of rows in all tables
 
75
*/
 
76
 
 
77
static ulonglong get_exact_record_count(TABLE_LIST *tables)
 
78
{
 
79
  ulonglong count= 1;
 
80
  for (TABLE_LIST *tl= tables; tl; tl= tl->next_leaf)
 
81
  {
 
82
    ha_rows tmp= tl->table->file->records();
 
83
    if ((tmp == HA_POS_ERROR))
 
84
      return ULONGLONG_MAX;
 
85
    count*= tmp;
 
86
  }
 
87
  return count;
 
88
}
 
89
 
 
90
 
 
91
/**
 
92
  Substitutes constants for some COUNT(), MIN() and MAX() functions.
 
93
 
 
94
  @param tables                list of leaves of join table tree
 
95
  @param all_fields            All fields to be returned
 
96
  @param conds                 WHERE clause
 
97
 
 
98
  @note
 
99
    This function is only called for queries with sum functions and no
 
100
    GROUP BY part.
 
101
 
 
102
  @retval
 
103
    0                    no errors
 
104
  @retval
 
105
    1                    if all items were resolved
 
106
  @retval
 
107
    HA_ERR_KEY_NOT_FOUND on impossible conditions
 
108
  @retval
 
109
    HA_ERR_... if a deadlock or a lock wait timeout happens, for example
 
110
*/
 
111
 
 
112
int opt_sum_query(TABLE_LIST *tables, List<Item> &all_fields,COND *conds)
 
113
{
 
114
  List_iterator_fast<Item> it(all_fields);
 
115
  int const_result= 1;
 
116
  bool recalc_const_item= 0;
 
117
  ulonglong count= 1;
 
118
  bool is_exact_count= TRUE, maybe_exact_count= TRUE;
 
119
  table_map removed_tables= 0, outer_tables= 0, used_tables= 0;
 
120
  table_map where_tables= 0;
 
121
  Item *item;
 
122
  int error;
 
123
 
 
124
  if (conds)
 
125
    where_tables= conds->used_tables();
 
126
 
 
127
  /*
 
128
    Analyze outer join dependencies, and, if possible, compute the number
 
129
    of returned rows.
 
130
  */
 
131
  for (TABLE_LIST *tl= tables; tl; tl= tl->next_leaf)
 
132
  {
 
133
    TABLE_LIST *embedded;
 
134
    for (embedded= tl ; embedded; embedded= embedded->embedding)
 
135
    {
 
136
      if (embedded->on_expr)
 
137
        break;
 
138
    }
 
139
    if (embedded)
 
140
    /* Don't replace expression on a table that is part of an outer join */
 
141
    {
 
142
      outer_tables|= tl->table->map;
 
143
 
 
144
      /*
 
145
        We can't optimise LEFT JOIN in cases where the WHERE condition
 
146
        restricts the table that is used, like in:
 
147
          SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
 
148
          WHERE t2.field IS NULL;
 
149
      */
 
150
      if (tl->table->map & where_tables)
 
151
        return 0;
 
152
    }
 
153
    else
 
154
      used_tables|= tl->table->map;
 
155
 
 
156
    /*
 
157
      If the storage manager of 'tl' gives exact row count as part of
 
158
      statistics (cheap), compute the total number of rows. If there are
 
159
      no outer table dependencies, this count may be used as the real count.
 
160
      Schema tables are filled after this function is invoked, so we can't
 
161
      get row count 
 
162
    */
 
163
    if (!(tl->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) ||
 
164
        tl->schema_table)
 
165
    {
 
166
      maybe_exact_count&= test(!tl->schema_table &&
 
167
                               (tl->table->file->ha_table_flags() &
 
168
                                HA_HAS_RECORDS));
 
169
      is_exact_count= FALSE;
 
170
      count= 1;                                 // ensure count != 0
 
171
    }
 
172
    else
 
173
    {
 
174
      error= tl->table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
 
175
      if(error)
 
176
      {
 
177
        tl->table->file->print_error(error, MYF(ME_FATALERROR));
 
178
        return error;
 
179
      }
 
180
      count*= tl->table->file->stats.records;
 
181
    }
 
182
  }
 
183
 
 
184
  /*
 
185
    Iterate through all items in the SELECT clause and replace
 
186
    COUNT(), MIN() and MAX() with constants (if possible).
 
187
  */
 
188
 
 
189
  while ((item= it++))
 
190
  {
 
191
    if (item->type() == Item::SUM_FUNC_ITEM)
 
192
    {
 
193
      Item_sum *item_sum= (((Item_sum*) item));
 
194
      switch (item_sum->sum_func()) {
 
195
      case Item_sum::COUNT_FUNC:
 
196
        /*
 
197
          If the expr in COUNT(expr) can never be null we can change this
 
198
          to the number of rows in the tables if this number is exact and
 
199
          there are no outer joins.
 
200
        */
 
201
        if (!conds && !((Item_sum_count*) item)->args[0]->maybe_null &&
 
202
            !outer_tables && maybe_exact_count)
 
203
        {
 
204
          if (!is_exact_count)
 
205
          {
 
206
            if ((count= get_exact_record_count(tables)) == ULONGLONG_MAX)
 
207
            {
 
208
              /* Error from handler in counting rows. Don't optimize count() */
 
209
              const_result= 0;
 
210
              continue;
 
211
            }
 
212
            is_exact_count= 1;                  // count is now exact
 
213
          }
 
214
          ((Item_sum_count*) item)->make_const((longlong) count);
 
215
          recalc_const_item= 1;
 
216
        }
 
217
        else
 
218
          const_result= 0;
 
219
        break;
 
220
      case Item_sum::MIN_FUNC:
 
221
      {
 
222
        /*
 
223
          If MIN(expr) is the first part of a key or if all previous
 
224
          parts of the key is found in the COND, then we can use
 
225
          indexes to find the key.
 
226
        */
 
227
        Item *expr=item_sum->args[0];
 
228
        if (expr->real_item()->type() == Item::FIELD_ITEM)
 
229
        {
 
230
          uchar key_buff[MAX_KEY_LENGTH];
 
231
          TABLE_REF ref;
 
232
          uint range_fl, prefix_len;
 
233
 
 
234
          ref.key_buff= key_buff;
 
235
          Item_field *item_field= (Item_field*) (expr->real_item());
 
236
          TABLE *table= item_field->field->table;
 
237
 
 
238
          /* 
 
239
            Look for a partial key that can be used for optimization.
 
240
            If we succeed, ref.key_length will contain the length of
 
241
            this key, while prefix_len will contain the length of 
 
242
            the beginning of this key without field used in MIN(). 
 
243
            Type of range for the key part for this field will be
 
244
            returned in range_fl.
 
245
          */
 
246
          if (table->file->inited || (outer_tables & table->map) ||
 
247
              !find_key_for_maxmin(0, &ref, item_field->field, conds,
 
248
                                   &range_fl, &prefix_len))
 
249
          {
 
250
            const_result= 0;
 
251
            break;
 
252
          }
 
253
          error= table->file->ha_index_init((uint) ref.key, 1);
 
254
 
 
255
          if (!ref.key_length)
 
256
            error= table->file->index_first(table->record[0]);
 
257
          else 
 
258
          {
 
259
            /*
 
260
              Use index to replace MIN/MAX functions with their values
 
261
              according to the following rules:
 
262
           
 
263
              1) Insert the minimum non-null values where the WHERE clause still
 
264
                 matches, or
 
265
              2) a NULL value if there are only NULL values for key_part_k.
 
266
              3) Fail, producing a row of nulls
 
267
 
 
268
              Implementation: Read the smallest value using the search key. If
 
269
              the interval is open, read the next value after the search
 
270
              key. If read fails, and we're looking for a MIN() value for a
 
271
              nullable column, test if there is an exact match for the key.
 
272
            */
 
273
            if (!(range_fl & NEAR_MIN))
 
274
              /* 
 
275
                 Closed interval: Either The MIN argument is non-nullable, or
 
276
                 we have a >= predicate for the MIN argument.
 
277
              */
 
278
              error= table->file->index_read_map(table->record[0],
 
279
                                                 ref.key_buff,
 
280
                                                 make_prev_keypart_map(ref.key_parts),
 
281
                                                 HA_READ_KEY_OR_NEXT);
 
282
            else
 
283
            {
 
284
              /*
 
285
                Open interval: There are two cases:
 
286
                1) We have only MIN() and the argument column is nullable, or
 
287
                2) there is a > predicate on it, nullability is irrelevant.
 
288
                We need to scan the next bigger record first.
 
289
              */
 
290
              error= table->file->index_read_map(table->record[0],
 
291
                                                 ref.key_buff, 
 
292
                                                 make_prev_keypart_map(ref.key_parts),
 
293
                                                 HA_READ_AFTER_KEY);
 
294
              /* 
 
295
                 If the found record is outside the group formed by the search
 
296
                 prefix, or there is no such record at all, check if all
 
297
                 records in that group have NULL in the MIN argument
 
298
                 column. If that is the case return that NULL.
 
299
 
 
300
                 Check if case 1 from above holds. If it does, we should read
 
301
                 the skipped tuple.
 
302
              */
 
303
              if (item_field->field->real_maybe_null() &&
 
304
                  ref.key_buff[prefix_len] == 1 &&
 
305
                  /*
 
306
                     Last keypart (i.e. the argument to MIN) is set to NULL by
 
307
                     find_key_for_maxmin only if all other keyparts are bound
 
308
                     to constants in a conjunction of equalities. Hence, we
 
309
                     can detect this by checking only if the last keypart is
 
310
                     NULL.
 
311
                  */
 
312
                  (error == HA_ERR_KEY_NOT_FOUND ||
 
313
                   key_cmp_if_same(table, ref.key_buff, ref.key, prefix_len)))
 
314
              {
 
315
                DBUG_ASSERT(item_field->field->real_maybe_null());
 
316
                error= table->file->index_read_map(table->record[0],
 
317
                                                   ref.key_buff,
 
318
                                                   make_prev_keypart_map(ref.key_parts),
 
319
                                                   HA_READ_KEY_EXACT);
 
320
              }
 
321
            }
 
322
          }
 
323
          /* Verify that the read tuple indeed matches the search key */
 
324
          if (!error && reckey_in_range(0, &ref, item_field->field, 
 
325
                                        conds, range_fl, prefix_len))
 
326
            error= HA_ERR_KEY_NOT_FOUND;
 
327
          if (table->key_read)
 
328
          {
 
329
            table->key_read= 0;
 
330
            table->file->extra(HA_EXTRA_NO_KEYREAD);
 
331
          }
 
332
          table->file->ha_index_end();
 
333
          if (error)
 
334
          {
 
335
            if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
 
336
              return HA_ERR_KEY_NOT_FOUND;            // No rows matching WHERE
 
337
            /* HA_ERR_LOCK_DEADLOCK or some other error */
 
338
            table->file->print_error(error, MYF(0));
 
339
            return(error);
 
340
          }
 
341
          removed_tables|= table->map;
 
342
        }
 
343
        else if (!expr->const_item() || !is_exact_count)
 
344
        {
 
345
          /*
 
346
            The optimization is not applicable in both cases:
 
347
            (a) 'expr' is a non-constant expression. Then we can't
 
348
            replace 'expr' by a constant.
 
349
            (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
 
350
            NULL if the query does not return any rows. Thus, if we are not
 
351
            able to determine if the query returns any rows, we can't apply
 
352
            the optimization and replace MIN/MAX with a constant.
 
353
          */
 
354
          const_result= 0;
 
355
          break;
 
356
        }
 
357
        if (!count)
 
358
        {
 
359
          /* If count == 0, then we know that is_exact_count == TRUE. */
 
360
          ((Item_sum_min*) item_sum)->clear(); /* Set to NULL. */
 
361
        }
 
362
        else
 
363
          ((Item_sum_min*) item_sum)->reset(); /* Set to the constant value. */
 
364
        ((Item_sum_min*) item_sum)->make_const();
 
365
        recalc_const_item= 1;
 
366
        break;
 
367
      }
 
368
      case Item_sum::MAX_FUNC:
 
369
      {
 
370
        /*
 
371
          If MAX(expr) is the first part of a key or if all previous
 
372
          parts of the key is found in the COND, then we can use
 
373
          indexes to find the key.
 
374
        */
 
375
        Item *expr=item_sum->args[0];
 
376
        if (expr->real_item()->type() == Item::FIELD_ITEM)
 
377
        {
 
378
          uchar key_buff[MAX_KEY_LENGTH];
 
379
          TABLE_REF ref;
 
380
          uint range_fl, prefix_len;
 
381
 
 
382
          ref.key_buff= key_buff;
 
383
          Item_field *item_field= (Item_field*) (expr->real_item());
 
384
          TABLE *table= item_field->field->table;
 
385
 
 
386
          /* 
 
387
            Look for a partial key that can be used for optimization.
 
388
            If we succeed, ref.key_length will contain the length of
 
389
            this key, while prefix_len will contain the length of 
 
390
            the beginning of this key without field used in MAX().
 
391
            Type of range for the key part for this field will be
 
392
            returned in range_fl.
 
393
          */
 
394
          if (table->file->inited || (outer_tables & table->map) ||
 
395
                  !find_key_for_maxmin(1, &ref, item_field->field, conds,
 
396
                                                   &range_fl, &prefix_len))
 
397
          {
 
398
            const_result= 0;
 
399
            break;
 
400
          }
 
401
          error= table->file->ha_index_init((uint) ref.key, 1);
 
402
 
 
403
          if (!ref.key_length)
 
404
            error= table->file->index_last(table->record[0]);
 
405
          else
 
406
            error= table->file->index_read_map(table->record[0], key_buff,
 
407
                                               make_prev_keypart_map(ref.key_parts),
 
408
                                               range_fl & NEAR_MAX ?
 
409
                                               HA_READ_BEFORE_KEY :
 
410
                                               HA_READ_PREFIX_LAST_OR_PREV);
 
411
          if (!error && reckey_in_range(1, &ref, item_field->field,
 
412
                                        conds, range_fl, prefix_len))
 
413
            error= HA_ERR_KEY_NOT_FOUND;
 
414
          if (table->key_read)
 
415
          {
 
416
            table->key_read=0;
 
417
            table->file->extra(HA_EXTRA_NO_KEYREAD);
 
418
          }
 
419
          table->file->ha_index_end();
 
420
          if (error)
 
421
          {
 
422
            if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
 
423
              return HA_ERR_KEY_NOT_FOUND;           // No rows matching WHERE
 
424
            /* HA_ERR_LOCK_DEADLOCK or some other error */
 
425
            table->file->print_error(error, MYF(ME_FATALERROR));
 
426
            return(error);
 
427
          }
 
428
          removed_tables|= table->map;
 
429
        }
 
430
        else if (!expr->const_item() || !is_exact_count)
 
431
        {
 
432
          /*
 
433
            The optimization is not applicable in both cases:
 
434
            (a) 'expr' is a non-constant expression. Then we can't
 
435
            replace 'expr' by a constant.
 
436
            (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
 
437
            NULL if the query does not return any rows. Thus, if we are not
 
438
            able to determine if the query returns any rows, we can't apply
 
439
            the optimization and replace MIN/MAX with a constant.
 
440
          */
 
441
          const_result= 0;
 
442
          break;
 
443
        }
 
444
        if (!count)
 
445
        {
 
446
          /* If count != 1, then we know that is_exact_count == TRUE. */
 
447
          ((Item_sum_max*) item_sum)->clear(); /* Set to NULL. */
 
448
        }
 
449
        else
 
450
          ((Item_sum_max*) item_sum)->reset(); /* Set to the constant value. */
 
451
        ((Item_sum_max*) item_sum)->make_const();
 
452
        recalc_const_item= 1;
 
453
        break;
 
454
      }
 
455
      default:
 
456
        const_result= 0;
 
457
        break;
 
458
      }
 
459
    }
 
460
    else if (const_result)
 
461
    {
 
462
      if (recalc_const_item)
 
463
        item->update_used_tables();
 
464
      if (!item->const_item())
 
465
        const_result= 0;
 
466
    }
 
467
  }
 
468
  /*
 
469
    If we have a where clause, we can only ignore searching in the
 
470
    tables if MIN/MAX optimisation replaced all used tables
 
471
    We do not use replaced values in case of:
 
472
    SELECT MIN(key) FROM table_1, empty_table
 
473
    removed_tables is != 0 if we have used MIN() or MAX().
 
474
  */
 
475
  if (removed_tables && used_tables != removed_tables)
 
476
    const_result= 0;                            // We didn't remove all tables
 
477
  return const_result;
 
478
}
 
479
 
 
480
 
 
481
/**
 
482
  Test if the predicate compares a field with constants.
 
483
 
 
484
  @param func_item        Predicate item
 
485
  @param[out] args        Here we store the field followed by constants
 
486
  @param[out] inv_order   Is set to 1 if the predicate is of the form
 
487
                          'const op field'
 
488
 
 
489
  @retval
 
490
    0        func_item is a simple predicate: a field is compared with
 
491
    constants
 
492
  @retval
 
493
    1        Otherwise
 
494
*/
 
495
 
 
496
bool simple_pred(Item_func *func_item, Item **args, bool *inv_order)
 
497
{
 
498
  Item *item;
 
499
  *inv_order= 0;
 
500
  switch (func_item->argument_count()) {
 
501
  case 0:
 
502
    /* MULT_EQUAL_FUNC */
 
503
    {
 
504
      Item_equal *item_equal= (Item_equal *) func_item;
 
505
      Item_equal_iterator it(*item_equal);
 
506
      args[0]= it++;
 
507
      if (it++)
 
508
        return 0;
 
509
      if (!(args[1]= item_equal->get_const()))
 
510
        return 0;
 
511
    }
 
512
    break;
 
513
  case 1:
 
514
    /* field IS NULL */
 
515
    item= func_item->arguments()[0];
 
516
    if (item->type() != Item::FIELD_ITEM)
 
517
      return 0;
 
518
    args[0]= item;
 
519
    break;
 
520
  case 2:
 
521
    /* 'field op const' or 'const op field' */
 
522
    item= func_item->arguments()[0];
 
523
    if (item->type() == Item::FIELD_ITEM)
 
524
    {
 
525
      args[0]= item;
 
526
      item= func_item->arguments()[1];
 
527
      if (!item->const_item())
 
528
        return 0;
 
529
      args[1]= item;
 
530
    }
 
531
    else if (item->const_item())
 
532
    {
 
533
      args[1]= item;
 
534
      item= func_item->arguments()[1];
 
535
      if (item->type() != Item::FIELD_ITEM)
 
536
        return 0;
 
537
      args[0]= item;
 
538
      *inv_order= 1;
 
539
    }
 
540
    else
 
541
      return 0;
 
542
    break;
 
543
  case 3:
 
544
    /* field BETWEEN const AND const */
 
545
    item= func_item->arguments()[0];
 
546
    if (item->type() == Item::FIELD_ITEM)
 
547
    {
 
548
      args[0]= item;
 
549
      for (int i= 1 ; i <= 2; i++)
 
550
      {
 
551
        item= func_item->arguments()[i];
 
552
        if (!item->const_item())
 
553
          return 0;
 
554
        args[i]= item;
 
555
      }
 
556
    }
 
557
    else
 
558
      return 0;
 
559
  }
 
560
  return 1;
 
561
}
 
562
 
 
563
 
 
564
/**
 
565
  Check whether a condition matches a key to get {MAX|MIN}(field):.
 
566
 
 
567
     For the index specified by the keyinfo parameter, index that
 
568
     contains field as its component (field_part), the function
 
569
     checks whether the condition cond is a conjunction and all its
 
570
     conjuncts referring to the columns of the same table as column
 
571
     field are one of the following forms:
 
572
     - f_i= const_i or const_i= f_i or f_i is null,
 
573
     where f_i is part of the index
 
574
     - field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field
 
575
     - field between const1 and const2
 
576
 
 
577
  @param[in]     max_fl         Set to 1 if we are optimising MAX()
 
578
  @param[in,out] ref            Reference to the structure we store the key
 
579
    value
 
580
  @param[in]     keyinfo        Reference to the key info
 
581
  @param[in]     field_part     Pointer to the key part for the field
 
582
  @param[in]     cond           WHERE condition
 
583
  @param[in,out] key_part_used  Map of matchings parts
 
584
  @param[in,out] range_fl       Says whether including key will be used
 
585
  @param[out]    prefix_len     Length of common key part for the range
 
586
    where MAX/MIN is searched for
 
587
 
 
588
  @retval
 
589
    0        Index can't be used.
 
590
  @retval
 
591
    1        We can use index to get MIN/MAX value
 
592
*/
 
593
 
 
594
static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo, 
 
595
                          KEY_PART_INFO *field_part, COND *cond,
 
596
                          key_part_map *key_part_used, uint *range_fl,
 
597
                          uint *prefix_len)
 
598
{
 
599
  if (!cond)
 
600
    return 1;
 
601
  Field *field= field_part->field;
 
602
  if (!(cond->used_tables() & field->table->map))
 
603
  {
 
604
    /* Condition doesn't restrict the used table */
 
605
    return 1;
 
606
  }
 
607
  if (cond->type() == Item::COND_ITEM)
 
608
  {
 
609
    if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
 
610
      return 0;
 
611
 
 
612
    /* AND */
 
613
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
 
614
    Item *item;
 
615
    while ((item= li++))
 
616
    {
 
617
      if (!matching_cond(max_fl, ref, keyinfo, field_part, item,
 
618
                         key_part_used, range_fl, prefix_len))
 
619
        return 0;
 
620
    }
 
621
    return 1;
 
622
  }
 
623
 
 
624
  if (cond->type() != Item::FUNC_ITEM)
 
625
    return 0;                                 // Not operator, can't optimize
 
626
 
 
627
  bool eq_type= 0;                            // =, <=> or IS NULL
 
628
  bool noeq_type= 0;                          // < or >  
 
629
  bool less_fl= 0;                            // < or <= 
 
630
  bool is_null= 0;
 
631
  bool between= 0;
 
632
 
 
633
  switch (((Item_func*) cond)->functype()) {
 
634
  case Item_func::ISNULL_FUNC:
 
635
    is_null= 1;     /* fall through */
 
636
  case Item_func::EQ_FUNC:
 
637
  case Item_func::EQUAL_FUNC:
 
638
    eq_type= 1;
 
639
    break;
 
640
  case Item_func::LT_FUNC:
 
641
    noeq_type= 1;   /* fall through */
 
642
  case Item_func::LE_FUNC:
 
643
    less_fl= 1;      
 
644
    break;
 
645
  case Item_func::GT_FUNC:
 
646
    noeq_type= 1;   /* fall through */
 
647
  case Item_func::GE_FUNC:
 
648
    break;
 
649
  case Item_func::BETWEEN:
 
650
    between= 1;
 
651
    break;
 
652
  case Item_func::MULT_EQUAL_FUNC:
 
653
    eq_type= 1;
 
654
    break;
 
655
  default:
 
656
    return 0;                                        // Can't optimize function
 
657
  }
 
658
  
 
659
  Item *args[3];
 
660
  bool inv;
 
661
 
 
662
  /* Test if this is a comparison of a field and constant */
 
663
  if (!simple_pred((Item_func*) cond, args, &inv))
 
664
    return 0;
 
665
 
 
666
  if (inv && !eq_type)
 
667
    less_fl= 1-less_fl;                         // Convert '<' -> '>' (etc)
 
668
 
 
669
  /* Check if field is part of the tested partial key */
 
670
  uchar *key_ptr= ref->key_buff;
 
671
  KEY_PART_INFO *part;
 
672
  for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
 
673
 
 
674
  {
 
675
    if (part > field_part)
 
676
      return 0;                     // Field is beyond the tested parts
 
677
    if (part->field->eq(((Item_field*) args[0])->field))
 
678
      break;                        // Found a part of the key for the field
 
679
  }
 
680
 
 
681
  bool is_field_part= part == field_part;
 
682
  if (!(is_field_part || eq_type))
 
683
    return 0;
 
684
 
 
685
  key_part_map org_key_part_used= *key_part_used;
 
686
  if (eq_type || between || max_fl == less_fl)
 
687
  {
 
688
    uint length= (key_ptr-ref->key_buff)+part->store_length;
 
689
    if (ref->key_length < length)
 
690
    {
 
691
    /* Ultimately ref->key_length will contain the length of the search key */
 
692
      ref->key_length= length;      
 
693
      ref->key_parts= (part - keyinfo->key_part) + 1;
 
694
    }
 
695
    if (!*prefix_len && part+1 == field_part)       
 
696
      *prefix_len= length;
 
697
    if (is_field_part && eq_type)
 
698
      *prefix_len= ref->key_length;
 
699
  
 
700
    *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
 
701
  }
 
702
 
 
703
  if (org_key_part_used != *key_part_used ||
 
704
      (is_field_part && 
 
705
       (between || eq_type || max_fl == less_fl) && !cond->val_int()))
 
706
  {
 
707
    /*
 
708
      It's the first predicate for this part or a predicate of the
 
709
      following form  that moves upper/lower bounds for max/min values:
 
710
      - field BETWEEN const AND const
 
711
      - field = const 
 
712
      - field {<|<=} const, when searching for MAX
 
713
      - field {>|>=} const, when searching for MIN
 
714
    */
 
715
 
 
716
    if (is_null)
 
717
    {
 
718
      part->field->set_null();
 
719
      *key_ptr= (uchar) 1;
 
720
    }
 
721
    else
 
722
    {
 
723
      store_val_in_field(part->field, args[between && max_fl ? 2 : 1],
 
724
                         CHECK_FIELD_IGNORE);
 
725
      if (part->null_bit) 
 
726
        *key_ptr++= (uchar) test(part->field->is_null());
 
727
      part->field->get_key_image(key_ptr, part->length, Field::itRAW);
 
728
    }
 
729
    if (is_field_part)
 
730
    {
 
731
      if (between || eq_type)
 
732
        *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
 
733
      else
 
734
      {
 
735
        *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
 
736
        if (noeq_type)
 
737
          *range_fl|=  (max_fl ? NEAR_MAX : NEAR_MIN);
 
738
        else
 
739
          *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
 
740
      }
 
741
    }
 
742
  }
 
743
  else if (eq_type)
 
744
  {
 
745
    if ((!is_null && !cond->val_int()) ||
 
746
        (is_null && !test(part->field->is_null())))
 
747
     return 0;                       // Impossible test
 
748
  }
 
749
  else if (is_field_part)
 
750
    *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
 
751
  return 1;  
 
752
}
 
753
 
 
754
 
 
755
/**
 
756
  Check whether we can get value for {max|min}(field) by using a key.
 
757
 
 
758
     If where-condition is not a conjunction of 0 or more conjuct the
 
759
     function returns false, otherwise it checks whether there is an
 
760
     index including field as its k-th component/part such that:
 
761
 
 
762
     -# for each previous component f_i there is one and only one conjunct
 
763
        of the form: f_i= const_i or const_i= f_i or f_i is null
 
764
     -# references to field occur only in conjucts of the form:
 
765
        field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or 
 
766
        field BETWEEN const1 AND const2
 
767
     -# all references to the columns from the same table as column field
 
768
        occur only in conjucts mentioned above.
 
769
     -# each of k first components the index is not partial, i.e. is not
 
770
        defined on a fixed length proper prefix of the field.
 
771
 
 
772
     If such an index exists the function through the ref parameter
 
773
     returns the key value to find max/min for the field using the index,
 
774
     the length of first (k-1) components of the key and flags saying
 
775
     how to apply the key for the search max/min value.
 
776
     (if we have a condition field = const, prefix_len contains the length
 
777
     of the whole search key)
 
778
 
 
779
  @param[in]     max_fl      0 for MIN(field) / 1 for MAX(field)
 
780
  @param[in,out] ref         Reference to the structure we store the key value
 
781
  @param[in]     field       Field used inside MIN() / MAX()
 
782
  @param[in]     cond        WHERE condition
 
783
  @param[out]    range_fl    Bit flags for how to search if key is ok
 
784
  @param[out]    prefix_len  Length of prefix for the search range
 
785
 
 
786
  @note
 
787
    This function may set table->key_read to 1, which must be reset after
 
788
    index is used! (This can only happen when function returns 1)
 
789
 
 
790
  @retval
 
791
    0   Index can not be used to optimize MIN(field)/MAX(field)
 
792
  @retval
 
793
    1   Can use key to optimize MIN()/MAX().
 
794
    In this case ref, range_fl and prefix_len are updated
 
795
*/
 
796
 
 
797
      
 
798
static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
 
799
                                Field* field, COND *cond,
 
800
                                uint *range_fl, uint *prefix_len)
 
801
{
 
802
  if (!(field->flags & PART_KEY_FLAG))
 
803
    return 0;                                        // Not key field
 
804
 
 
805
  TABLE *table= field->table;
 
806
  uint idx= 0;
 
807
 
 
808
  KEY *keyinfo,*keyinfo_end;
 
809
  for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys ;
 
810
       keyinfo != keyinfo_end;
 
811
       keyinfo++,idx++)
 
812
  {
 
813
    KEY_PART_INFO *part,*part_end;
 
814
    key_part_map key_part_to_use= 0;
 
815
    /*
 
816
      Perform a check if index is not disabled by ALTER TABLE
 
817
      or IGNORE INDEX.
 
818
    */
 
819
    if (!table->keys_in_use_for_query.is_set(idx))
 
820
      continue;
 
821
    uint jdx= 0;
 
822
    *prefix_len= 0;
 
823
    for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts ;
 
824
         part != part_end ;
 
825
         part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1)
 
826
    {
 
827
      if (!(table->file->index_flags(idx, jdx, 0) & HA_READ_ORDER))
 
828
        return 0;
 
829
 
 
830
      /* Check whether the index component is partial */
 
831
      Field *part_field= table->field[part->fieldnr-1];
 
832
      if ((part_field->flags & BLOB_FLAG) ||
 
833
          part->length < part_field->key_length())
 
834
        break;
 
835
 
 
836
      if (field->eq(part->field))
 
837
      {
 
838
        ref->key= idx;
 
839
        ref->key_length= 0;
 
840
        ref->key_parts= 0;
 
841
        key_part_map key_part_used= 0;
 
842
        *range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
 
843
        if (matching_cond(max_fl, ref, keyinfo, part, cond,
 
844
                          &key_part_used, range_fl, prefix_len) &&
 
845
            !(key_part_to_use & ~key_part_used))
 
846
        {
 
847
          if (!max_fl && key_part_used == key_part_to_use && part->null_bit)
 
848
          {
 
849
            /*
 
850
              The query is on this form:
 
851
 
 
852
              SELECT MIN(key_part_k) 
 
853
              FROM t1 
 
854
              WHERE key_part_1 = const and ... and key_part_k-1 = const
 
855
 
 
856
              If key_part_k is nullable, we want to find the first matching row
 
857
              where key_part_k is not null. The key buffer is now {const, ...,
 
858
              NULL}. This will be passed to the handler along with a flag
 
859
              indicating open interval. If a tuple is read that does not match
 
860
              these search criteria, an attempt will be made to read an exact
 
861
              match for the key buffer.
 
862
            */
 
863
            /* Set the first byte of key_part_k to 1, that means NULL */
 
864
            ref->key_buff[ref->key_length]= 1;
 
865
            ref->key_length+= part->store_length;
 
866
            ref->key_parts++;
 
867
            DBUG_ASSERT(ref->key_parts == jdx+1);
 
868
            *range_fl&= ~NO_MIN_RANGE;
 
869
            *range_fl|= NEAR_MIN; // Open interval
 
870
          }
 
871
          /*
 
872
            The following test is false when the key in the key tree is
 
873
            converted (for example to upper case)
 
874
          */
 
875
          if (field->part_of_key.is_set(idx))
 
876
          {
 
877
            table->key_read= 1;
 
878
            table->file->extra(HA_EXTRA_KEYREAD);
 
879
          }
 
880
          return 1;
 
881
        }
 
882
      }
 
883
    }
 
884
  }
 
885
  return 0;
 
886
}
 
887
 
 
888
 
 
889
/**
 
890
  Check whether found key is in range specified by conditions.
 
891
 
 
892
  @param[in] max_fl         0 for MIN(field) / 1 for MAX(field)
 
893
  @param[in] ref            Reference to the key value and info
 
894
  @param[in] field          Field used the MIN/MAX expression
 
895
  @param[in] cond           WHERE condition
 
896
  @param[in] range_fl       Says whether there is a condition to to be checked
 
897
  @param[in] prefix_len     Length of the constant part of the key
 
898
 
 
899
  @retval
 
900
    0        ok
 
901
  @retval
 
902
    1        WHERE was not true for the found row
 
903
*/
 
904
 
 
905
static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
 
906
                            COND *cond, uint range_fl, uint prefix_len)
 
907
{
 
908
  if (key_cmp_if_same(field->table, ref->key_buff, ref->key, prefix_len))
 
909
    return 1;
 
910
  if (!cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
 
911
    return 0;
 
912
  return maxmin_in_range(max_fl, field, cond);
 
913
}
 
914
 
 
915
 
 
916
/**
 
917
  Check whether {MAX|MIN}(field) is in range specified by conditions.
 
918
 
 
919
  @param[in] max_fl          0 for MIN(field) / 1 for MAX(field)
 
920
  @param[in] field           Field used the MIN/MAX expression
 
921
  @param[in] cond            WHERE condition
 
922
 
 
923
  @retval
 
924
    0        ok
 
925
  @retval
 
926
    1        WHERE was not true for the found row
 
927
*/
 
928
 
 
929
static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
 
930
{
 
931
  /* If AND/OR condition */
 
932
  if (cond->type() == Item::COND_ITEM)
 
933
  {
 
934
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
 
935
    Item *item;
 
936
    while ((item= li++))
 
937
    {
 
938
      if (maxmin_in_range(max_fl, field, item))
 
939
        return 1;
 
940
    }
 
941
    return 0;
 
942
  }
 
943
 
 
944
  if (cond->used_tables() != field->table->map)
 
945
    return 0;
 
946
  bool less_fl= 0;
 
947
  switch (((Item_func*) cond)->functype()) {
 
948
  case Item_func::BETWEEN:
 
949
    return cond->val_int() == 0;                // Return 1 if WHERE is false
 
950
  case Item_func::LT_FUNC:
 
951
  case Item_func::LE_FUNC:
 
952
    less_fl= 1;
 
953
  case Item_func::GT_FUNC:
 
954
  case Item_func::GE_FUNC:
 
955
  {
 
956
    Item *item= ((Item_func*) cond)->arguments()[1];
 
957
    /* In case of 'const op item' we have to swap the operator */
 
958
    if (!item->const_item())
 
959
      less_fl= 1-less_fl;
 
960
    /*
 
961
      We only have to check the expression if we are using an expression like
 
962
      SELECT MAX(b) FROM t1 WHERE a=const AND b>const
 
963
      not for
 
964
      SELECT MAX(b) FROM t1 WHERE a=const AND b<const
 
965
    */
 
966
    if (max_fl != less_fl)
 
967
      return cond->val_int() == 0;                // Return 1 if WHERE is false
 
968
    return 0;
 
969
  }
 
970
  case Item_func::EQ_FUNC:
 
971
  case Item_func::EQUAL_FUNC:
 
972
    break;
 
973
  default:                                        // Keep compiler happy
 
974
    DBUG_ASSERT(1);                               // Impossible
 
975
    break;
 
976
  }
 
977
  return 0;
 
978
}
 
979