opt_sum.cc 36.2 KB
Newer Older
1
/* Copyright (c) 2000, 2011, Oracle and/or its affiliates.
2
   Copyright (c) 2008, 2017, MariaDB Corporation.
unknown's avatar
unknown committed
3

unknown's avatar
unknown committed
4 5
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
unknown's avatar
unknown committed
6
   the Free Software Foundation; version 2 of the License.
unknown's avatar
unknown committed
7

unknown's avatar
unknown committed
8 9 10 11
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
unknown's avatar
unknown committed
12

unknown's avatar
unknown committed
13 14
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
Vicențiu Ciorbaru's avatar
Vicențiu Ciorbaru committed
15
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
unknown's avatar
unknown committed
16 17


unknown's avatar
unknown committed
18 19 20
/**
  @file

21 22 23 24 25 26 27
  Optimising of MIN(), MAX() and COUNT(*) queries without 'group by' clause
  by replacing the aggregate expression with a constant.  

  Given a table with a compound key on columns (a,b,c), the following
  types of queries are optimised (assuming the table handler supports
  the required methods)

unknown's avatar
unknown committed
28
  @verbatim
29 30 31 32 33 34 35
  SELECT COUNT(*) FROM t1[,t2,t3,...]
  SELECT MIN(b) FROM t1 WHERE a=const
  SELECT MAX(c) FROM t1 WHERE a=const AND b=const
  SELECT MAX(b) FROM t1 WHERE a=const AND b<const
  SELECT MIN(b) FROM t1 WHERE a=const AND b>const
  SELECT MIN(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
  SELECT MAX(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
unknown's avatar
unknown committed
36
  @endverbatim
37 38 39 40 41 42 43

  Instead of '<' one can use '<=', '>', '>=' and '=' as well.
  Instead of 'a=const' the condition 'a IS NULL' can be used.

  If all selected fields are replaced then we will also remove all
  involved tables and return the answer without any join. Thus, the
  following query will be replaced with a row of two constants:
unknown's avatar
unknown committed
44
  @verbatim
45 46
  SELECT MAX(b), MIN(d) FROM t1,t2 
    WHERE a=const AND b<const AND d>const
unknown's avatar
unknown committed
47
  @endverbatim
48 49
  (assuming a index for column d of table t2 is defined)
*/
unknown's avatar
unknown committed
50

51
#include "mariadb.h"
52 53
#include "sql_priv.h"
#include "key.h"                                // key_cmp_if_same
unknown's avatar
unknown committed
54 55
#include "sql_select.h"

unknown's avatar
unknown committed
56 57 58
static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref, Field* field,
                                COND *cond, uint *range_fl,
                                uint *key_prefix_length);
59 60 61 62
static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
                            COND *cond, uint range_fl, uint prefix_len);
static int maxmin_in_range(bool max_fl, Field* field, COND *cond);

unknown's avatar
unknown committed
63

64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
/*
  Get exact count of rows in all tables

  SYNOPSIS
    get_exact_records()
    tables		List of tables

  NOTES
    When this is called, we know all table handlers supports HA_HAS_RECORDS
    or HA_STATS_RECORDS_IS_EXACT

  RETURN
    ULONGLONG_MAX	Error: Could not calculate number of rows
    #			Multiplication of number of rows in all tables
*/

80
static ulonglong get_exact_record_count(List<TABLE_LIST> &tables)
81 82
{
  ulonglong count= 1;
83 84 85
  TABLE_LIST *tl;
  List_iterator<TABLE_LIST> ti(tables);
  while ((tl= ti++))
86 87
  {
    ha_rows tmp= tl->table->file->records();
88
    if (tmp == HA_POS_ERROR)
89 90 91 92 93 94 95
      return ULONGLONG_MAX;
    count*= tmp;
  }
  return count;
}


96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
/**
  Use index to read MIN(field) value.
  
  @param table      Table object
  @param ref        Reference to the structure where we store the key value
  @item_field       Field used in MIN()
  @range_fl         Whether range endpoint is strict less than
  @prefix_len       Length of common key part for the range
  
  @retval
    0               No errors
    HA_ERR_...      Otherwise
*/

static int get_index_min_value(TABLE *table, TABLE_REF *ref,
                               Item_field *item_field, uint range_fl,
                               uint prefix_len)
{
  int error;
  
  if (!ref->key_length)
Michael Widenius's avatar
Michael Widenius committed
117
    error= table->file->ha_index_first(table->record[0]);
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
  else 
  {
    /*
      Use index to replace MIN/MAX functions with their values
      according to the following rules:

      1) Insert the minimum non-null values where the WHERE clause still
         matches, or
      2) a NULL value if there are only NULL values for key_part_k.
      3) Fail, producing a row of nulls

      Implementation: Read the smallest value using the search key. If
      the interval is open, read the next value after the search
      key. If read fails, and we're looking for a MIN() value for a
      nullable column, test if there is an exact match for the key.
    */
    if (!(range_fl & NEAR_MIN))
      /* 
         Closed interval: Either The MIN argument is non-nullable, or
         we have a >= predicate for the MIN argument.
      */
Michael Widenius's avatar
Michael Widenius committed
139 140 141 142
      error= table->file->ha_index_read_map(table->record[0],
                                            ref->key_buff,
                                            make_prev_keypart_map(ref->key_parts),
                                            HA_READ_KEY_OR_NEXT);
143 144 145 146 147 148 149
    else
    {
      /*
        Open interval: There are two cases:
        1) We have only MIN() and the argument column is nullable, or
        2) there is a > predicate on it, nullability is irrelevant.
        We need to scan the next bigger record first.
150 151
        Open interval is not used if the search key involves the last keypart,
        and it would not work.
152
      */
153
      DBUG_ASSERT(prefix_len < ref->key_length);
Michael Widenius's avatar
Michael Widenius committed
154 155 156 157
      error= table->file->ha_index_read_map(table->record[0],
                                            ref->key_buff,
                                            make_prev_keypart_map(ref->key_parts),
                                            HA_READ_AFTER_KEY);
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
      /* 
         If the found record is outside the group formed by the search
         prefix, or there is no such record at all, check if all
         records in that group have NULL in the MIN argument
         column. If that is the case return that NULL.

         Check if case 1 from above holds. If it does, we should read
         the skipped tuple.
      */
      if (item_field->field->real_maybe_null() &&
          ref->key_buff[prefix_len] == 1 &&
          /*
            Last keypart (i.e. the argument to MIN) is set to NULL by
            find_key_for_maxmin only if all other keyparts are bound
            to constants in a conjunction of equalities. Hence, we
            can detect this by checking only if the last keypart is
            NULL.
          */
          (error == HA_ERR_KEY_NOT_FOUND ||
           key_cmp_if_same(table, ref->key_buff, ref->key, prefix_len)))
      {
        DBUG_ASSERT(item_field->field->real_maybe_null());
Michael Widenius's avatar
Michael Widenius committed
180 181 182 183
        error= table->file->ha_index_read_map(table->record[0],
                                              ref->key_buff,
                                              make_prev_keypart_map(ref->key_parts),
                                              HA_READ_KEY_EXACT);
184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
      }
    }
  }
  return error;
}


/**
  Use index to read MAX(field) value.
  
  @param table      Table object
  @param ref        Reference to the structure where we store the key value
  @range_fl         Whether range endpoint is strict greater than
  
  @retval
    0               No errors
    HA_ERR_...      Otherwise
*/

static int get_index_max_value(TABLE *table, TABLE_REF *ref, uint range_fl)
{
  return (ref->key_length ?
Michael Widenius's avatar
Michael Widenius committed
206 207 208 209 210 211
          table->file->ha_index_read_map(table->record[0], ref->key_buff,
                                         make_prev_keypart_map(ref->key_parts),
                                         range_fl & NEAR_MAX ?
                                         HA_READ_BEFORE_KEY : 
                                         HA_READ_PREFIX_LAST_OR_PREV) :
          table->file->ha_index_last(table->record[0]));
212 213 214 215
}



unknown's avatar
unknown committed
216
/**
unknown's avatar
unknown committed
217 218
  Substitutes constants for some COUNT(), MIN() and MAX() functions.

219
  @param thd                   thread handler
unknown's avatar
unknown committed
220 221 222
  @param tables                list of leaves of join table tree
  @param all_fields            All fields to be returned
  @param conds                 WHERE clause
unknown's avatar
unknown committed
223

unknown's avatar
unknown committed
224
  @note
225
    This function is only called for queries with aggregate functions and no
226 227
    GROUP BY part. This means that the result set shall contain a single
    row only
unknown's avatar
unknown committed
228

unknown's avatar
unknown committed
229
  @retval
unknown's avatar
unknown committed
230
    0                    no errors
unknown's avatar
unknown committed
231
  @retval
unknown's avatar
unknown committed
232
    1                    if all items were resolved
unknown's avatar
unknown committed
233
  @retval
unknown's avatar
unknown committed
234
    HA_ERR_KEY_NOT_FOUND on impossible conditions
unknown's avatar
unknown committed
235 236
  @retval
    HA_ERR_... if a deadlock or a lock wait timeout happens, for example
237 238
  @retval
    ER_...     e.g. ER_SUBQUERY_NO_1_ROW
unknown's avatar
unknown committed
239
*/
unknown's avatar
unknown committed
240

241
int opt_sum_query(THD *thd,
Igor Babaev's avatar
Merge  
Igor Babaev committed
242
                  List<TABLE_LIST> &tables, List<Item> &all_fields, COND *conds)
unknown's avatar
unknown committed
243
{
unknown's avatar
unknown committed
244
  List_iterator_fast<Item> it(all_fields);
245 246
  List_iterator<TABLE_LIST> ti(tables);
  TABLE_LIST *tl;
unknown's avatar
unknown committed
247 248
  int const_result= 1;
  bool recalc_const_item= 0;
249 250
  ulonglong count= 1;
  bool is_exact_count= TRUE, maybe_exact_count= TRUE;
unknown's avatar
unknown committed
251 252
  table_map removed_tables= 0, outer_tables= 0, used_tables= 0;
  table_map where_tables= 0;
unknown's avatar
unknown committed
253
  Item *item;
254
  int error= 0;
255 256
  DBUG_ENTER("opt_sum_query");

Igor Babaev's avatar
Igor Babaev committed
257 258
  thd->lex->current_select->min_max_opt_list.empty();

unknown's avatar
unknown committed
259 260 261
  if (conds)
    where_tables= conds->used_tables();

262 263 264 265
  /*
    Analyze outer join dependencies, and, if possible, compute the number
    of returned rows.
  */
266
  while ((tl= ti++))
267
  {
unknown's avatar
unknown committed
268 269 270 271 272 273 274
    TABLE_LIST *embedded;
    for (embedded= tl ; embedded; embedded= embedded->embedding)
    {
      if (embedded->on_expr)
        break;
    }
    if (embedded)
275
    /* Don't replace expression on a table that is part of an outer join */
unknown's avatar
unknown committed
276 277 278 279
    {
      outer_tables|= tl->table->map;

      /*
280 281
        We can't optimise LEFT JOIN in cases where the WHERE condition
        restricts the table that is used, like in:
unknown's avatar
unknown committed
282
          SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
283
          WHERE t2.field IS NULL;
unknown's avatar
unknown committed
284 285
      */
      if (tl->table->map & where_tables)
286
        DBUG_RETURN(0);
unknown's avatar
unknown committed
287
    }
unknown's avatar
unknown committed
288 289
    else
      used_tables|= tl->table->map;
290 291

    /*
292 293 294
      If the storage manager of 'tl' gives exact row count as part of
      statistics (cheap), compute the total number of rows. If there are
      no outer table dependencies, this count may be used as the real count.
295 296
      Schema tables are filled after this function is invoked, so we can't
      get row count 
297
    */
298
    if (!(tl->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) ||
299
        tl->schema_table)
300
    {
301 302 303
      maybe_exact_count&= MY_TEST(!tl->schema_table &&
                                  (tl->table->file->ha_table_flags() &
                                   HA_HAS_RECORDS));
304
      is_exact_count= FALSE;
305 306
      count= 1;                                 // ensure count != 0
    }
307 308
    else if (tl->is_materialized_derived() || 
             tl->jtbm_subselect)
309 310 311 312 313
    {
      /*
        Can't remove a derived table as it's number of rows is just an
        estimate.
      */
Igor Babaev's avatar
Merge  
Igor Babaev committed
314
      DBUG_RETURN(0);
315
    }
316 317
    else
    {
318
      error= tl->table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
319
      if (unlikely(error))
320
      {
321
        tl->table->file->print_error(error, MYF(ME_FATALERROR));
322
        DBUG_RETURN(error);
323
      }
324
      count*= tl->table->file->stats.records;
325
    }
326 327 328
  }

  /*
329 330
    Iterate through all items in the SELECT clause and replace
    COUNT(), MIN() and MAX() with constants (if possible).
331
  */
unknown's avatar
unknown committed
332 333 334 335 336 337 338 339

  while ((item= it++))
  {
    if (item->type() == Item::SUM_FUNC_ITEM)
    {
      Item_sum *item_sum= (((Item_sum*) item));
      switch (item_sum->sum_func()) {
      case Item_sum::COUNT_FUNC:
340
        /*
341
          If the expr in COUNT(expr) can never be null we can change this
342 343
          to the number of rows in the tables if this number is exact and
          there are no outer joins.
344
        */
345
        if (!conds && !((Item_sum_count*) item)->get_arg(0)->maybe_null &&
346 347
            !outer_tables && maybe_exact_count &&
            ((item->used_tables() & OUTER_REF_TABLE_BIT) == 0))
348
        {
349 350 351 352 353 354 355 356 357 358 359
          if (!is_exact_count)
          {
            if ((count= get_exact_record_count(tables)) == ULONGLONG_MAX)
            {
              /* Error from handler in counting rows. Don't optimize count() */
              const_result= 0;
              continue;
            }
            is_exact_count= 1;                  // count is now exact
          }
          ((Item_sum_count*) item)->make_const((longlong) count);
360
          recalc_const_item= 1;
361 362 363 364
        }
        else
          const_result= 0;
        break;
unknown's avatar
unknown committed
365
      case Item_sum::MIN_FUNC:
366
      case Item_sum::MAX_FUNC:
unknown's avatar
unknown committed
367
      {
368
        int is_max= MY_TEST(item_sum->sum_func() == Item_sum::MAX_FUNC);
369
        /*
370
          If MIN/MAX(expr) is the first part of a key or if all previous
371 372 373
          parts of the key is found in the COND, then we can use
          indexes to find the key.
        */
374
        Item *expr=item_sum->get_arg(0);
375 376
        if (((expr->used_tables() & OUTER_REF_TABLE_BIT) == 0) &&
            expr->real_item()->type() == Item::FIELD_ITEM)
377
        {
378
          uchar key_buff[MAX_KEY_LENGTH];
379 380 381 382
          TABLE_REF ref;
          uint range_fl, prefix_len;

          ref.key_buff= key_buff;
383
          Item_field *item_field= (Item_field*) (expr->real_item());
384 385 386 387 388 389
          TABLE *table= item_field->field->table;

          /* 
            Look for a partial key that can be used for optimization.
            If we succeed, ref.key_length will contain the length of
            this key, while prefix_len will contain the length of 
390
            the beginning of this key without field used in MIN/MAX(). 
unknown's avatar
unknown committed
391 392
            Type of range for the key part for this field will be
            returned in range_fl.
393
          */
394
          if (table->file->inited || (outer_tables & table->map) ||
395
              !find_key_for_maxmin(is_max, &ref, item_field->field, conds,
396 397 398 399 400
                                   &range_fl, &prefix_len))
          {
            const_result= 0;
            break;
          }
401
          longlong info_limit= 1;
402
          error= 0;
403

404 405 406 407 408 409 410 411 412 413
          table->file->info_push(INFO_KIND_FORCE_LIMIT_BEGIN, &info_limit);
          if (!table->const_table)
          {
            if (likely(!(error= table->file->ha_index_init((uint) ref.key,
                                                           1))))
              error= (is_max ?
                      get_index_max_value(table, &ref, range_fl) :
                      get_index_min_value(table, &ref, item_field, range_fl,
                                          prefix_len));
          }
414
          /* Verify that the read tuple indeed matches the search key */
415 416 417
	  if (!error &&
              reckey_in_range(is_max, &ref, item_field->field,
                              conds, range_fl, prefix_len))
418
	    error= HA_ERR_KEY_NOT_FOUND;
419 420 421 422 423
          if (!table->const_table)
          {
            table->file->ha_end_keyread();
            table->file->ha_index_end();
          }
424
          table->file->info_push(INFO_KIND_FORCE_LIMIT_END, NULL);
425
          if (error)
unknown's avatar
unknown committed
426
	  {
unknown's avatar
unknown committed
427
	    if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
428
	      DBUG_RETURN(HA_ERR_KEY_NOT_FOUND); // No rows matching WHERE
unknown's avatar
unknown committed
429 430
	    /* HA_ERR_LOCK_DEADLOCK or some other error */
 	    table->file->print_error(error, MYF(0));
431
            DBUG_RETURN(error);
unknown's avatar
unknown committed
432
	  }
433 434
          removed_tables|= table->map;
        }
unknown's avatar
unknown committed
435
        else if (!expr->const_item() || !is_exact_count || conds)
436
        {
437 438 439 440 441 442 443 444
          /*
            The optimization is not applicable in both cases:
            (a) 'expr' is a non-constant expression. Then we can't
            replace 'expr' by a constant.
            (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
            NULL if the query does not return any rows. Thus, if we are not
            able to determine if the query returns any rows, we can't apply
            the optimization and replace MIN/MAX with a constant.
unknown's avatar
unknown committed
445 446
            (c) there is a WHERE clause. The WHERE conditions may result in
            an empty result, but the clause cannot be taken into account here.
447
          */
448 449 450
          const_result= 0;
          break;
        }
451 452 453
        item_sum->set_aggregator(item_sum->has_with_distinct() ? 
                                 Aggregator::DISTINCT_AGGREGATOR :
                                 Aggregator::SIMPLE_AGGREGATOR);
454
        /*
455 456 457
          If count == 0 (so is_exact_count == TRUE) and
          there're no outer joins, set to NULL,
          otherwise set to the constant value.
458
        */
459
        if (!count && !outer_tables)
460
        {
461
          item_sum->aggregator_clear();
462 463
        }
        else
Igor Babaev's avatar
Igor Babaev committed
464
        {
465
          item_sum->reset_and_add();
Igor Babaev's avatar
Igor Babaev committed
466 467 468 469 470 471
          /*
            Save a reference to the item for possible rollback
            of the min/max optimizations for this select
          */
	  thd->lex->current_select->min_max_opt_list.push_back(item_sum);
        }
472
        item_sum->make_const();
473 474
        recalc_const_item= 1;
        break;
unknown's avatar
unknown committed
475 476
      }
      default:
477 478
        const_result= 0;
        break;
unknown's avatar
unknown committed
479 480 481 482 483
      }
    }
    else if (const_result)
    {
      if (recalc_const_item)
484
        item->update_used_tables();
Igor Babaev's avatar
Igor Babaev committed
485
      if (!item->const_item() && item->type() != Item::WINDOW_FUNC_ITEM)
486
        const_result= 0;
unknown's avatar
unknown committed
487 488
    }
  }
489

490
  if (unlikely(thd->is_error()))
491
    DBUG_RETURN(thd->get_stmt_da()->sql_errno());
492

493 494 495
  /*
    If we have a where clause, we can only ignore searching in the
    tables if MIN/MAX optimisation replaced all used tables
496
    We do not use replaced values in case of:
497 498 499 500
    SELECT MIN(key) FROM table_1, empty_table
    removed_tables is != 0 if we have used MIN() or MAX().
  */
  if (removed_tables && used_tables != removed_tables)
unknown's avatar
unknown committed
501
    const_result= 0;                            // We didn't remove all tables
502
  DBUG_RETURN(const_result);
unknown's avatar
unknown committed
503 504 505
}


506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
/*
  Check if both item1 and item2 are strings, and item1 has fewer characters 
  than item2.
*/

static bool check_item1_shorter_item2(Item *item1, Item *item2)
{
  if (item1->cmp_type() == STRING_RESULT &&
      item2->cmp_type() == STRING_RESULT)
  {
    int len1= item1->max_length / item1->collation.collation->mbmaxlen;
    int len2= item2->max_length / item2->collation.collation->mbmaxlen;
    return len1 < len2;
  }
  return false;  /* When the check is not applicable, it means "not bigger" */
}


unknown's avatar
unknown committed
524 525
/**
  Test if the predicate compares a field with constants.
unknown's avatar
unknown committed
526

unknown's avatar
unknown committed
527 528 529 530
  @param func_item        Predicate item
  @param[out] args        Here we store the field followed by constants
  @param[out] inv_order   Is set to 1 if the predicate is of the form
                          'const op field'
531

unknown's avatar
unknown committed
532
  @retval
Igor Babaev's avatar
Igor Babaev committed
533 534
    0      func_item is a simple predicate: a field is compared with a constant
           whose length does not exceed the max length of the field values  
unknown's avatar
unknown committed
535
  @retval
536 537 538
    1        Otherwise
*/

539
bool simple_pred(Item_func *func_item, Item **args, bool *inv_order)
540 541 542 543
{
  Item *item;
  *inv_order= 0;
  switch (func_item->argument_count()) {
544 545 546 547 548 549
  case 0:
    /* MULT_EQUAL_FUNC */
    {
      Item_equal *item_equal= (Item_equal *) func_item;
      if (!(args[1]= item_equal->get_const()))
        return 0;
550
      Item_equal_fields_iterator it(*item_equal);
Igor Babaev's avatar
Igor Babaev committed
551
      if (!(item= it++))
552
        return 0;
Igor Babaev's avatar
Igor Babaev committed
553
      args[0]= item->real_item();
554
      if (check_item1_shorter_item2(args[0], args[1]))
Igor Babaev's avatar
Igor Babaev committed
555
        return 0;
Igor Babaev's avatar
Igor Babaev committed
556
      if (it++)
557 558 559
        return 0;
    }
    break;
560 561
  case 1:
    /* field IS NULL */
Igor Babaev's avatar
Igor Babaev committed
562
    item= func_item->arguments()[0]->real_item();
563 564 565 566 567 568
    if (item->type() != Item::FIELD_ITEM)
      return 0;
    args[0]= item;
    break;
  case 2:
    /* 'field op const' or 'const op field' */
Igor Babaev's avatar
Igor Babaev committed
569
    item= func_item->arguments()[0]->real_item();
570
    if (item->type() == Item::FIELD_ITEM)
unknown's avatar
unknown committed
571
    {
572
      args[0]= item;
Igor Babaev's avatar
Igor Babaev committed
573
      item= func_item->arguments()[1]->real_item();
574 575 576
      if (!item->const_item())
        return 0;
      args[1]= item;
unknown's avatar
unknown committed
577
    }
578
    else if (item->const_item())
unknown's avatar
unknown committed
579
    {
580
      args[1]= item;
Igor Babaev's avatar
Igor Babaev committed
581
      item= func_item->arguments()[1]->real_item();
582 583 584 585
      if (item->type() != Item::FIELD_ITEM)
        return 0;
      args[0]= item;
      *inv_order= 1;
unknown's avatar
unknown committed
586
    }
587 588
    else
      return 0;
589
    if (check_item1_shorter_item2(args[0], args[1]))
Igor Babaev's avatar
Igor Babaev committed
590
      return 0;
591 592 593
    break;
  case 3:
    /* field BETWEEN const AND const */
Igor Babaev's avatar
Igor Babaev committed
594
    item= func_item->arguments()[0]->real_item();
595
    if (item->type() == Item::FIELD_ITEM)
unknown's avatar
unknown committed
596
    {
597 598 599
      args[0]= item;
      for (int i= 1 ; i <= 2; i++)
      {
Igor Babaev's avatar
Igor Babaev committed
600
        item= func_item->arguments()[i]->real_item();
601 602 603
        if (!item->const_item())
          return 0;
        args[i]= item;
604
        if (check_item1_shorter_item2(args[0], args[i]))
Igor Babaev's avatar
Igor Babaev committed
605
          return 0;
606
      }
unknown's avatar
unknown committed
607
    }
608 609
    else
      return 0;
unknown's avatar
unknown committed
610
  }
611
  return 1;
unknown's avatar
unknown committed
612 613 614
}


unknown's avatar
unknown committed
615 616
/**
  Check whether a condition matches a key to get {MAX|MIN}(field):.
617

618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663
   For the index specified by the keyinfo parameter and an index that
   contains the field as its component (field_part), the function
   checks whether 

   - the condition cond is a conjunction, 
   - all of its conjuncts refer to columns of the same table, and
   - each conjunct is on one of the following forms:
     - f_i = const_i or const_i = f_i or f_i IS NULL,
       where f_i is part of the index
     - field {<|<=|>=|>|=} const
     - const {<|<=|>=|>|=} field
     - field BETWEEN const_1 AND const_2

   As a side-effect, the key value to be used for looking up the MIN/MAX value
   is actually stored inside the Field object. An interesting feature is that
   the function will find the most restrictive endpoint by over-eager
   evaluation of the @c WHERE condition. It continually stores the current
   endpoint inside the Field object. For a query such as

   @code
   SELECT MIN(a) FROM t1 WHERE a > 3 AND a > 5;
   @endcode

   the algorithm will recurse over the conjuction, storing first a 3 in the
   field. In the next recursive invocation the expression a > 5 is evaluated
   as 3 > 5 (Due to the dual nature of Field objects as value carriers and
   field identifiers), which will obviously fail, leading to 5 being stored in
   the Field object.
   
   @param[in]     max_fl         Set to true if we are optimizing MAX(),
                                 false means we are optimizing %MIN()
   @param[in, out] ref           Reference to the structure where the function 
                                 stores the key value
   @param[in]     keyinfo        Reference to the key info
   @param[in]     field_part     Pointer to the key part for the field
   @param[in]     cond           WHERE condition
   @param[in,out] key_part_used  Map of matchings parts. The function will output
                                 the set of key parts actually being matched in 
                                 this set, yet it relies on the caller to 
                                 initialize the value to zero. This is due 
                                 to the fact that this value is passed 
                                 recursively.
   @param[in,out] range_fl       Says whether endpoints use strict greater/less 
                                 than.
   @param[out]    prefix_len     Length of common key part for the range
                                 where MAX/MIN is searched for
unknown's avatar
unknown committed
664 665

  @retval
666
    false    Index can't be used.
unknown's avatar
unknown committed
667
  @retval
668
    true     We can use the index to get MIN/MAX value
669
*/
unknown's avatar
unknown committed
670

671 672 673 674
static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo, 
                          KEY_PART_INFO *field_part, COND *cond,
                          key_part_map *key_part_used, uint *range_fl,
                          uint *prefix_len)
unknown's avatar
unknown committed
675
{
676
  DBUG_ENTER("matching_cond");
677
  if (!cond)
678
    DBUG_RETURN(TRUE);
679
  Field *field= field_part->field;
680 681
  table_map cond_used_tables= cond->used_tables();
  if (cond_used_tables & OUTER_REF_TABLE_BIT)
Igor Babaev's avatar
Igor Babaev committed
682 683 684
  { 
    DBUG_RETURN(FALSE);
  } 
685 686
  if (!(cond_used_tables & field->table->map) &&
      MY_TEST(cond_used_tables & ~PSEUDO_TABLE_BITS))
687 688
  {
    /* Condition doesn't restrict the used table */
Igor Babaev's avatar
Igor Babaev committed
689
    DBUG_RETURN(!cond->const_item());
690
  }
unknown's avatar
unknown committed
691 692
  else if (cond->is_expensive())
    DBUG_RETURN(FALSE);
unknown's avatar
unknown committed
693 694 695
  if (cond->type() == Item::COND_ITEM)
  {
    if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
696
      DBUG_RETURN(FALSE);
unknown's avatar
unknown committed
697

698
    /* AND */
unknown's avatar
unknown committed
699
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
unknown's avatar
unknown committed
700
    Item *item;
701
    while ((item= li++))
unknown's avatar
unknown committed
702
    {
703 704
      if (!matching_cond(max_fl, ref, keyinfo, field_part, item,
                         key_part_used, range_fl, prefix_len))
705
        DBUG_RETURN(FALSE);
unknown's avatar
unknown committed
706
    }
707
    DBUG_RETURN(TRUE);
708 709 710
  }

  if (cond->type() != Item::FUNC_ITEM)
711
    DBUG_RETURN(FALSE);                                 // Not operator, can't optimize
712 713

  bool eq_type= 0;                            // =, <=> or IS NULL
714
  bool is_null_safe_eq= FALSE;                // The operator is NULL safe, e.g. <=> 
715 716
  bool noeq_type= 0;                          // < or >  
  bool less_fl= 0;                            // < or <= 
717 718
  bool is_null= 0;                            // IS NULL
  bool between= 0;                            // BETWEEN ... AND ... 
719 720 721 722 723

  switch (((Item_func*) cond)->functype()) {
  case Item_func::ISNULL_FUNC:
    is_null= 1;     /* fall through */
  case Item_func::EQ_FUNC:
724 725
    eq_type= TRUE;
    break;
726
  case Item_func::EQUAL_FUNC:
727
    eq_type= is_null_safe_eq= TRUE;
728 729 730 731 732 733 734 735 736 737 738
    break;
  case Item_func::LT_FUNC:
    noeq_type= 1;   /* fall through */
  case Item_func::LE_FUNC:
    less_fl= 1;      
    break;
  case Item_func::GT_FUNC:
    noeq_type= 1;   /* fall through */
  case Item_func::GE_FUNC:
    break;
  case Item_func::BETWEEN:
unknown's avatar
unknown committed
739 740
    if (((Item_func_between*) cond)->negated)
      DBUG_RETURN(FALSE);
741 742
    between= 1;
    break;
743 744 745
  case Item_func::MULT_EQUAL_FUNC:
    eq_type= 1;
    break;
746
  default:
747
    DBUG_RETURN(FALSE);                                        // Can't optimize function
748 749 750 751 752 753 754
  }
  
  Item *args[3];
  bool inv;

  /* Test if this is a comparison of a field and constant */
  if (!simple_pred((Item_func*) cond, args, &inv))
755
    DBUG_RETURN(FALSE);
756

757 758
  if (!is_null_safe_eq && !is_null &&
      (args[1]->is_null() || (between && args[2]->is_null())))
759
    DBUG_RETURN(FALSE);
760

761 762 763 764
  if (inv && !eq_type)
    less_fl= 1-less_fl;                         // Convert '<' -> '>' (etc)

  /* Check if field is part of the tested partial key */
765
  uchar *key_ptr= ref->key_buff;
766
  KEY_PART_INFO *part;
767
  for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
768 769 770

  {
    if (part > field_part)
771
      DBUG_RETURN(FALSE);                     // Field is beyond the tested parts
772
    if (part->field->eq(((Item_field*) args[0])->field))
773
      break;                        // Found a part of the key for the field
774 775 776 777
  }

  bool is_field_part= part == field_part;
  if (!(is_field_part || eq_type))
778
    DBUG_RETURN(FALSE);
779 780 781 782

  key_part_map org_key_part_used= *key_part_used;
  if (eq_type || between || max_fl == less_fl)
  {
783
    uint length= (uint)(key_ptr-ref->key_buff)+part->store_length;
784
    if (ref->key_length < length)
785
    {
786 787
    /* Ultimately ref->key_length will contain the length of the search key */
      ref->key_length= length;      
788
      ref->key_parts= (uint)(part - keyinfo->key_part) + 1;
789
    }
790 791 792 793 794 795
    if (!*prefix_len && part+1 == field_part)       
      *prefix_len= length;
    if (is_field_part && eq_type)
      *prefix_len= ref->key_length;
  
    *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
unknown's avatar
unknown committed
796
  }
797

798 799 800 801 802 803 804 805 806 807 808
  if (org_key_part_used == *key_part_used &&
    /*
      The current search key is not being extended with a new key part.  This
      means that the a condition is added a key part for which there was a
      previous condition. We can only overwrite such key parts in some special
      cases, e.g. a > 2 AND a > 1 (here range_fl must be set to something). In
      all other cases the WHERE condition is always false anyway.
    */
      (eq_type || *range_fl == 0))
      DBUG_RETURN(FALSE);

809 810
  if (org_key_part_used != *key_part_used ||
      (is_field_part && 
unknown's avatar
unknown committed
811
       (between || eq_type || max_fl == less_fl) && !cond->val_int()))
unknown's avatar
unknown committed
812
  {
813 814 815 816
    /*
      It's the first predicate for this part or a predicate of the
      following form  that moves upper/lower bounds for max/min values:
      - field BETWEEN const AND const
unknown's avatar
unknown committed
817
      - field = const 
818 819 820 821
      - field {<|<=} const, when searching for MAX
      - field {>|>=} const, when searching for MIN
    */

822
    if (is_null || (is_null_safe_eq && args[1]->is_null()))
unknown's avatar
unknown committed
823
    {
824 825 826 827 828
      /*
        If we have a non-nullable index, we cannot use it,
        since set_null will be ignored, and we will compare uninitialized data.
      */
      if (!part->field->real_maybe_null())
829
        DBUG_RETURN(FALSE);
830
      part->field->set_null();
831
      *key_ptr= (uchar) 1;
unknown's avatar
unknown committed
832
    }
833
    else
unknown's avatar
unknown committed
834
    {
835 836
      /* Update endpoints for MAX/MIN, see function comment. */
      Item *value= args[between && max_fl ? 2 : 1];
837
      value->save_in_field_no_warnings(part->field, 1);
838
      if (part->null_bit) 
839
        *key_ptr++= (uchar) MY_TEST(part->field->is_null());
840
      part->field->get_key_image(key_ptr, part->length, Field::itRAW);
841 842 843
    }
    if (is_field_part)
    {
unknown's avatar
unknown committed
844
      if (between || eq_type)
845 846 847 848 849 850 851 852 853
        *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
      else
      {
        *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
        if (noeq_type)
          *range_fl|=  (max_fl ? NEAR_MAX : NEAR_MIN);
        else
          *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
      }
unknown's avatar
unknown committed
854 855
    }
  }
856 857
  else if (eq_type)
  {
858
    if ((!is_null && !cond->val_int()) ||
859
        (is_null && !MY_TEST(part->field->is_null())))
860
     DBUG_RETURN(FALSE);                       // Impossible test
861 862 863
  }
  else if (is_field_part)
    *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
864
  DBUG_RETURN(TRUE);  
unknown's avatar
unknown committed
865 866 867
}


unknown's avatar
unknown committed
868
/**
869
  Check whether we can get value for {max|min}(field) by using a key.
unknown's avatar
unknown committed
870

unknown's avatar
unknown committed
871 872 873 874 875
     If where-condition is not a conjunction of 0 or more conjuct the
     function returns false, otherwise it checks whether there is an
     index including field as its k-th component/part such that:

     -# for each previous component f_i there is one and only one conjunct
876
        of the form: f_i= const_i or const_i= f_i or f_i is null
unknown's avatar
unknown committed
877
     -# references to field occur only in conjucts of the form:
878 879
        field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or 
        field BETWEEN const1 AND const2
unknown's avatar
unknown committed
880
     -# all references to the columns from the same table as column field
881
        occur only in conjucts mentioned above.
unknown's avatar
unknown committed
882
     -# each of k first components the index is not partial, i.e. is not
unknown's avatar
unknown committed
883
        defined on a fixed length proper prefix of the field.
884 885 886 887 888 889

     If such an index exists the function through the ref parameter
     returns the key value to find max/min for the field using the index,
     the length of first (k-1) components of the key and flags saying
     how to apply the key for the search max/min value.
     (if we have a condition field = const, prefix_len contains the length
unknown's avatar
unknown committed
890 891 892 893 894 895 896 897
     of the whole search key)

  @param[in]     max_fl      0 for MIN(field) / 1 for MAX(field)
  @param[in,out] ref         Reference to the structure we store the key value
  @param[in]     field       Field used inside MIN() / MAX()
  @param[in]     cond        WHERE condition
  @param[out]    range_fl    Bit flags for how to search if key is ok
  @param[out]    prefix_len  Length of prefix for the search range
898

unknown's avatar
unknown committed
899
  @note
900 901 902
    This function may set field->table->key_read to true,
    which must be reset after index is used!
    (This can only happen when function returns 1)
unknown's avatar
unknown committed
903

unknown's avatar
unknown committed
904
  @retval
905
    0   Index can not be used to optimize MIN(field)/MAX(field)
unknown's avatar
unknown committed
906 907 908 909
  @retval
    1   Can use key to optimize MIN()/MAX().
    In this case ref, range_fl and prefix_len are updated
*/
910 911 912 913
      
static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
                                Field* field, COND *cond,
                                uint *range_fl, uint *prefix_len)
unknown's avatar
unknown committed
914 915
{
  if (!(field->flags & PART_KEY_FLAG))
916
    return FALSE;                               // Not key field
917 918

  DBUG_ENTER("find_key_for_maxmin");
unknown's avatar
unknown committed
919

920 921
  TABLE *table= field->table;
  uint idx= 0;
unknown's avatar
unknown committed
922

923
  KEY *keyinfo,*keyinfo_end;
924
  for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys ;
925 926
       keyinfo != keyinfo_end;
       keyinfo++,idx++)
unknown's avatar
unknown committed
927
  {
928 929
    KEY_PART_INFO *part,*part_end;
    key_part_map key_part_to_use= 0;
930 931 932 933 934 935
    /*
      Perform a check if index is not disabled by ALTER TABLE
      or IGNORE INDEX.
    */
    if (!table->keys_in_use_for_query.is_set(idx))
      continue;
unknown's avatar
unknown committed
936
    uint jdx= 0;
unknown's avatar
unknown committed
937
    *prefix_len= 0;
938 939
    part_end= keyinfo->key_part+table->actual_n_key_parts(keyinfo);
    for (part= keyinfo->key_part ;
940
         part != part_end ;
unknown's avatar
unknown committed
941
         part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1)
unknown's avatar
unknown committed
942
    {
943
      if (!(table->file->index_flags(idx, jdx, 0) & HA_READ_ORDER))
944
        DBUG_RETURN(FALSE);
unknown's avatar
unknown committed
945

946 947 948 949
      /* Check whether the index component is partial */
      Field *part_field= table->field[part->fieldnr-1];
      if ((part_field->flags & BLOB_FLAG) ||
          part->length < part_field->key_length())
unknown's avatar
unknown committed
950 951
        break;

952 953 954 955
      if (field->eq(part->field))
      {
        ref->key= idx;
        ref->key_length= 0;
956
        ref->key_parts= 0;
957 958 959 960 961 962 963 964 965
        key_part_map key_part_used= 0;
        *range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
        if (matching_cond(max_fl, ref, keyinfo, part, cond,
                          &key_part_used, range_fl, prefix_len) &&
            !(key_part_to_use & ~key_part_used))
        {
          if (!max_fl && key_part_used == key_part_to_use && part->null_bit)
          {
            /*
966 967 968 969 970 971 972 973 974 975 976 977
              The query is on this form:

              SELECT MIN(key_part_k) 
              FROM t1 
              WHERE key_part_1 = const and ... and key_part_k-1 = const

              If key_part_k is nullable, we want to find the first matching row
              where key_part_k is not null. The key buffer is now {const, ...,
              NULL}. This will be passed to the handler along with a flag
              indicating open interval. If a tuple is read that does not match
              these search criteria, an attempt will be made to read an exact
              match for the key buffer.
978
            */
979
            /* Set the first byte of key_part_k to 1, that means NULL */
980 981
            ref->key_buff[ref->key_length]= 1;
            ref->key_length+= part->store_length;
982 983
            ref->key_parts++;
            DBUG_ASSERT(ref->key_parts == jdx+1);
984
            *range_fl&= ~NO_MIN_RANGE;
985
            *range_fl|= NEAR_MIN; // Open interval
986 987 988 989 990
          }
          /*
            The following test is false when the key in the key tree is
            converted (for example to upper case)
          */
991
          if (field->part_of_key.is_set(idx))
992
            table->file->ha_start_keyread(idx);
993
          DBUG_RETURN(TRUE);
994 995
        }
      }
unknown's avatar
unknown committed
996 997
    }
  }
998
  DBUG_RETURN(FALSE);
999 1000
}

1001

unknown's avatar
unknown committed
1002 1003
/**
  Check whether found key is in range specified by conditions.
1004

unknown's avatar
unknown committed
1005 1006 1007 1008 1009 1010
  @param[in] max_fl         0 for MIN(field) / 1 for MAX(field)
  @param[in] ref            Reference to the key value and info
  @param[in] field          Field used the MIN/MAX expression
  @param[in] cond           WHERE condition
  @param[in] range_fl       Says whether there is a condition to to be checked
  @param[in] prefix_len     Length of the constant part of the key
1011

unknown's avatar
unknown committed
1012
  @retval
1013
    0        ok
unknown's avatar
unknown committed
1014
  @retval
1015 1016 1017 1018 1019 1020
    1        WHERE was not true for the found row
*/

static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
                            COND *cond, uint range_fl, uint prefix_len)
{
unknown's avatar
unknown committed
1021
  if (key_cmp_if_same(field->table, ref->key_buff, ref->key, prefix_len))
1022 1023
    return 1;
  if (!cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
unknown's avatar
unknown committed
1024
    return 0;
1025 1026
  return maxmin_in_range(max_fl, field, cond);
}
unknown's avatar
unknown committed
1027

1028

unknown's avatar
unknown committed
1029 1030
/**
  Check whether {MAX|MIN}(field) is in range specified by conditions.
1031

unknown's avatar
unknown committed
1032 1033 1034 1035 1036
  @param[in] max_fl          0 for MIN(field) / 1 for MAX(field)
  @param[in] field           Field used the MIN/MAX expression
  @param[in] cond            WHERE condition

  @retval
1037
    0        ok
unknown's avatar
unknown committed
1038
  @retval
1039 1040 1041 1042 1043 1044 1045
    1        WHERE was not true for the found row
*/

static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
{
  /* If AND/OR condition */
  if (cond->type() == Item::COND_ITEM)
unknown's avatar
unknown committed
1046
  {
1047 1048 1049
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
    Item *item;
    while ((item= li++))
unknown's avatar
unknown committed
1050
    {
1051 1052
      if (maxmin_in_range(max_fl, field, item))
        return 1;
unknown's avatar
unknown committed
1053
    }
1054
    return 0;
unknown's avatar
unknown committed
1055
  }
1056 1057 1058 1059 1060 1061 1062 1063 1064 1065

  if (cond->used_tables() != field->table->map)
    return 0;
  bool less_fl= 0;
  switch (((Item_func*) cond)->functype()) {
  case Item_func::BETWEEN:
    return cond->val_int() == 0;                // Return 1 if WHERE is false
  case Item_func::LT_FUNC:
  case Item_func::LE_FUNC:
    less_fl= 1;
1066
    /* fall through */
1067 1068 1069
  case Item_func::GT_FUNC:
  case Item_func::GE_FUNC:
  {
unknown's avatar
unknown committed
1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080
    Item *item= ((Item_func*) cond)->arguments()[1];
    /* In case of 'const op item' we have to swap the operator */
    if (!item->const_item())
      less_fl= 1-less_fl;
    /*
      We only have to check the expression if we are using an expression like
      SELECT MAX(b) FROM t1 WHERE a=const AND b>const
      not for
      SELECT MAX(b) FROM t1 WHERE a=const AND b<const
    */
    if (max_fl != less_fl)
1081
      return cond->val_int() == 0;               // Return 1 if WHERE is false
1082 1083
    return 0;
  }
1084 1085
  default:
    break;                                      // Ignore
1086 1087
  }
  return 0;
unknown's avatar
unknown committed
1088
}
1089