← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to server/opt_sum.cc

  • Committer: Brian Aker
  • Date: 2008-07-13 22:45:08 UTC
  • Revision ID: brian@tangent.org-20080713224508-hb20z4okblotb39a
longlong replacement

Show diffs side-by-side

added added

removed removed

Lines of Context:
server/opt_sum.cc
18
18
  @file
19
19
 
20
20
  Optimising of MIN(), MAX() and COUNT(*) queries without 'group by' clause
21
 
  by replacing the aggregate expression with a constant.
 
21
  by replacing the aggregate expression with a constant.  
22
22
 
23
23
  Given a table with a compound key on columns (a,b,c), the following
24
24
  types of queries are optimised (assuming the table handler supports
41
41
  involved tables and return the answer without any join. Thus, the
42
42
  following query will be replaced with a row of two constants:
43
43
  @verbatim
44
 
  SELECT MAX(b), MIN(d) FROM t1,t2
 
44
  SELECT MAX(b), MIN(d) FROM t1,t2 
45
45
    WHERE a=const AND b<const AND d>const
46
46
  @endverbatim
47
47
  (assuming a index for column d of table t2 is defined)
48
48
*/
49
49
 
50
 
#include <drizzled/server_includes.h>
51
 
#include <drizzled/sql_select.h>
52
 
#include <drizzled/item/sum.h>
53
 
#include <drizzled/item/cmpfunc.h>
 
50
#include "mysql_priv.h"
 
51
#include "sql_select.h"
54
52
 
55
53
static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref, Field* field,
56
 
                                COND *cond, uint32_t *range_fl,
57
 
                                uint32_t *key_prefix_length);
 
54
                                COND *cond, uint *range_fl,
 
55
                                uint *key_prefix_length);
58
56
static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
59
 
                            COND *cond, uint32_t range_fl, uint32_t prefix_len);
 
57
                            COND *cond, uint range_fl, uint prefix_len);
60
58
static int maxmin_in_range(bool max_fl, Field* field, COND *cond);
61
59
 
62
60
 
72
70
    or HA_STATS_RECORDS_IS_EXACT
73
71
 
74
72
  RETURN
75
 
    UINT64_MAX  Error: Could not calculate number of rows
 
73
    ULONGLONG_MAX       Error: Could not calculate number of rows
76
74
    #                   Multiplication of number of rows in all tables
77
75
*/
78
76
 
79
 
static uint64_t get_exact_record_count(TableList *tables)
 
77
static uint64_t get_exact_record_count(TABLE_LIST *tables)
80
78
{
81
79
  uint64_t count= 1;
82
 
  for (TableList *tl= tables; tl; tl= tl->next_leaf)
 
80
  for (TABLE_LIST *tl= tables; tl; tl= tl->next_leaf)
83
81
  {
84
82
    ha_rows tmp= tl->table->file->records();
85
83
    if ((tmp == HA_POS_ERROR))
86
 
      return UINT64_MAX;
 
84
      return ULONGLONG_MAX;
87
85
    count*= tmp;
88
86
  }
89
87
  return count;
111
109
    HA_ERR_... if a deadlock or a lock wait timeout happens, for example
112
110
*/
113
111
 
114
 
int opt_sum_query(TableList *tables, List<Item> &all_fields,COND *conds)
 
112
int opt_sum_query(TABLE_LIST *tables, List<Item> &all_fields,COND *conds)
115
113
{
116
114
  List_iterator_fast<Item> it(all_fields);
117
115
  int const_result= 1;
118
116
  bool recalc_const_item= 0;
119
117
  uint64_t count= 1;
120
 
  bool is_exact_count= true, maybe_exact_count= true;
 
118
  bool is_exact_count= TRUE, maybe_exact_count= true;
121
119
  table_map removed_tables= 0, outer_tables= 0, used_tables= 0;
122
120
  table_map where_tables= 0;
123
121
  Item *item;
130
128
    Analyze outer join dependencies, and, if possible, compute the number
131
129
    of returned rows.
132
130
  */
133
 
  for (TableList *tl= tables; tl; tl= tl->next_leaf)
 
131
  for (TABLE_LIST *tl= tables; tl; tl= tl->next_leaf)
134
132
  {
135
 
    TableList *embedded;
 
133
    TABLE_LIST *embedded;
136
134
    for (embedded= tl ; embedded; embedded= embedded->embedding)
137
135
    {
138
136
      if (embedded->on_expr)
160
158
      statistics (cheap), compute the total number of rows. If there are
161
159
      no outer table dependencies, this count may be used as the real count.
162
160
      Schema tables are filled after this function is invoked, so we can't
163
 
      get row count
 
161
      get row count 
164
162
    */
165
163
    if (!(tl->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) ||
166
164
        tl->schema_table)
205
203
        {
206
204
          if (!is_exact_count)
207
205
          {
208
 
            if ((count= get_exact_record_count(tables)) == UINT64_MAX)
 
206
            if ((count= get_exact_record_count(tables)) == ULONGLONG_MAX)
209
207
            {
210
208
              /* Error from handler in counting rows. Don't optimize count() */
211
209
              const_result= 0;
229
227
        Item *expr=item_sum->args[0];
230
228
        if (expr->real_item()->type() == Item::FIELD_ITEM)
231
229
        {
232
 
          unsigned char key_buff[MAX_KEY_LENGTH];
 
230
          uchar key_buff[MAX_KEY_LENGTH];
233
231
          TABLE_REF ref;
234
 
          uint32_t range_fl, prefix_len;
 
232
          uint range_fl, prefix_len;
235
233
 
236
234
          ref.key_buff= key_buff;
237
235
          Item_field *item_field= (Item_field*) (expr->real_item());
238
 
          Table *table= item_field->field->table;
 
236
          TABLE *table= item_field->field->table;
239
237
 
240
 
          /*
 
238
          /* 
241
239
            Look for a partial key that can be used for optimization.
242
240
            If we succeed, ref.key_length will contain the length of
243
 
            this key, while prefix_len will contain the length of
244
 
            the beginning of this key without field used in MIN().
 
241
            this key, while prefix_len will contain the length of 
 
242
            the beginning of this key without field used in MIN(). 
245
243
            Type of range for the key part for this field will be
246
244
            returned in range_fl.
247
245
          */
256
254
 
257
255
          if (!ref.key_length)
258
256
            error= table->file->index_first(table->record[0]);
259
 
          else
 
257
          else 
260
258
          {
261
259
            /*
262
260
              Use index to replace MIN/MAX functions with their values
263
261
              according to the following rules:
264
 
 
 
262
           
265
263
              1) Insert the minimum non-null values where the WHERE clause still
266
264
                 matches, or
267
265
              2) a NULL value if there are only NULL values for key_part_k.
273
271
              nullable column, test if there is an exact match for the key.
274
272
            */
275
273
            if (!(range_fl & NEAR_MIN))
276
 
              /*
 
274
              /* 
277
275
                 Closed interval: Either The MIN argument is non-nullable, or
278
276
                 we have a >= predicate for the MIN argument.
279
277
              */
290
288
                We need to scan the next bigger record first.
291
289
              */
292
290
              error= table->file->index_read_map(table->record[0],
293
 
                                                 ref.key_buff,
 
291
                                                 ref.key_buff, 
294
292
                                                 make_prev_keypart_map(ref.key_parts),
295
293
                                                 HA_READ_AFTER_KEY);
296
 
              /*
 
294
              /* 
297
295
                 If the found record is outside the group formed by the search
298
296
                 prefix, or there is no such record at all, check if all
299
297
                 records in that group have NULL in the MIN argument
323
321
            }
324
322
          }
325
323
          /* Verify that the read tuple indeed matches the search key */
326
 
          if (!error && reckey_in_range(0, &ref, item_field->field,
 
324
          if (!error && reckey_in_range(0, &ref, item_field->field, 
327
325
                                        conds, range_fl, prefix_len))
328
326
            error= HA_ERR_KEY_NOT_FOUND;
329
327
          if (table->key_read)
358
356
        }
359
357
        if (!count)
360
358
        {
361
 
          /* If count == 0, then we know that is_exact_count == true. */
 
359
          /* If count == 0, then we know that is_exact_count == TRUE. */
362
360
          ((Item_sum_min*) item_sum)->clear(); /* Set to NULL. */
363
361
        }
364
362
        else
377
375
        Item *expr=item_sum->args[0];
378
376
        if (expr->real_item()->type() == Item::FIELD_ITEM)
379
377
        {
380
 
          unsigned char key_buff[MAX_KEY_LENGTH];
 
378
          uchar key_buff[MAX_KEY_LENGTH];
381
379
          TABLE_REF ref;
382
 
          uint32_t range_fl, prefix_len;
 
380
          uint range_fl, prefix_len;
383
381
 
384
382
          ref.key_buff= key_buff;
385
383
          Item_field *item_field= (Item_field*) (expr->real_item());
386
 
          Table *table= item_field->field->table;
 
384
          TABLE *table= item_field->field->table;
387
385
 
388
 
          /*
 
386
          /* 
389
387
            Look for a partial key that can be used for optimization.
390
388
            If we succeed, ref.key_length will contain the length of
391
 
            this key, while prefix_len will contain the length of
 
389
            this key, while prefix_len will contain the length of 
392
390
            the beginning of this key without field used in MAX().
393
391
            Type of range for the key part for this field will be
394
392
            returned in range_fl.
445
443
        }
446
444
        if (!count)
447
445
        {
448
 
          /* If count != 1, then we know that is_exact_count == true. */
 
446
          /* If count != 1, then we know that is_exact_count == TRUE. */
449
447
          ((Item_sum_max*) item_sum)->clear(); /* Set to NULL. */
450
448
        }
451
449
        else
593
591
    1        We can use index to get MIN/MAX value
594
592
*/
595
593
 
596
 
static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo,
 
594
static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo, 
597
595
                          KEY_PART_INFO *field_part, COND *cond,
598
 
                          key_part_map *key_part_used, uint32_t *range_fl,
599
 
                          uint32_t *prefix_len)
 
596
                          key_part_map *key_part_used, uint *range_fl,
 
597
                          uint *prefix_len)
600
598
{
601
599
  if (!cond)
602
600
    return 1;
627
625
    return 0;                                 // Not operator, can't optimize
628
626
 
629
627
  bool eq_type= 0;                            // =, <=> or IS NULL
630
 
  bool noeq_type= 0;                          // < or >
631
 
  bool less_fl= 0;                            // < or <=
 
628
  bool noeq_type= 0;                          // < or >  
 
629
  bool less_fl= 0;                            // < or <= 
632
630
  bool is_null= 0;
633
631
  bool between= 0;
634
632
 
642
640
  case Item_func::LT_FUNC:
643
641
    noeq_type= 1;   /* fall through */
644
642
  case Item_func::LE_FUNC:
645
 
    less_fl= 1;
 
643
    less_fl= 1;      
646
644
    break;
647
645
  case Item_func::GT_FUNC:
648
646
    noeq_type= 1;   /* fall through */
657
655
  default:
658
656
    return 0;                                        // Can't optimize function
659
657
  }
660
 
 
 
658
  
661
659
  Item *args[3];
662
660
  bool inv;
663
661
 
669
667
    less_fl= 1-less_fl;                         // Convert '<' -> '>' (etc)
670
668
 
671
669
  /* Check if field is part of the tested partial key */
672
 
  unsigned char *key_ptr= ref->key_buff;
 
670
  uchar *key_ptr= ref->key_buff;
673
671
  KEY_PART_INFO *part;
674
672
  for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
675
673
 
687
685
  key_part_map org_key_part_used= *key_part_used;
688
686
  if (eq_type || between || max_fl == less_fl)
689
687
  {
690
 
    uint32_t length= (key_ptr-ref->key_buff)+part->store_length;
 
688
    uint length= (key_ptr-ref->key_buff)+part->store_length;
691
689
    if (ref->key_length < length)
692
690
    {
693
691
    /* Ultimately ref->key_length will contain the length of the search key */
694
 
      ref->key_length= length;
 
692
      ref->key_length= length;      
695
693
      ref->key_parts= (part - keyinfo->key_part) + 1;
696
694
    }
697
 
    if (!*prefix_len && part+1 == field_part)
 
695
    if (!*prefix_len && part+1 == field_part)       
698
696
      *prefix_len= length;
699
697
    if (is_field_part && eq_type)
700
698
      *prefix_len= ref->key_length;
701
 
 
 
699
  
702
700
    *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
703
701
  }
704
702
 
705
703
  if (org_key_part_used != *key_part_used ||
706
 
      (is_field_part &&
 
704
      (is_field_part && 
707
705
       (between || eq_type || max_fl == less_fl) && !cond->val_int()))
708
706
  {
709
707
    /*
710
708
      It's the first predicate for this part or a predicate of the
711
709
      following form  that moves upper/lower bounds for max/min values:
712
710
      - field BETWEEN const AND const
713
 
      - field = const
 
711
      - field = const 
714
712
      - field {<|<=} const, when searching for MAX
715
713
      - field {>|>=} const, when searching for MIN
716
714
    */
718
716
    if (is_null)
719
717
    {
720
718
      part->field->set_null();
721
 
      *key_ptr= (unsigned char) 1;
 
719
      *key_ptr= (uchar) 1;
722
720
    }
723
721
    else
724
722
    {
725
723
      store_val_in_field(part->field, args[between && max_fl ? 2 : 1],
726
724
                         CHECK_FIELD_IGNORE);
727
 
      if (part->null_bit)
728
 
        *key_ptr++= (unsigned char) test(part->field->is_null());
 
725
      if (part->null_bit) 
 
726
        *key_ptr++= (uchar) test(part->field->is_null());
729
727
      part->field->get_key_image(key_ptr, part->length, Field::itRAW);
730
728
    }
731
729
    if (is_field_part)
750
748
  }
751
749
  else if (is_field_part)
752
750
    *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
753
 
  return 1;
 
751
  return 1;  
754
752
}
755
753
 
756
754
 
764
762
     -# for each previous component f_i there is one and only one conjunct
765
763
        of the form: f_i= const_i or const_i= f_i or f_i is null
766
764
     -# references to field occur only in conjucts of the form:
767
 
        field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or
 
765
        field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or 
768
766
        field BETWEEN const1 AND const2
769
767
     -# all references to the columns from the same table as column field
770
768
        occur only in conjucts mentioned above.
796
794
    In this case ref, range_fl and prefix_len are updated
797
795
*/
798
796
 
799
 
 
 
797
      
800
798
static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
801
799
                                Field* field, COND *cond,
802
 
                                uint32_t *range_fl, uint32_t *prefix_len)
 
800
                                uint *range_fl, uint *prefix_len)
803
801
{
804
802
  if (!(field->flags & PART_KEY_FLAG))
805
803
    return 0;                                        // Not key field
806
804
 
807
 
  Table *table= field->table;
808
 
  uint32_t idx= 0;
 
805
  TABLE *table= field->table;
 
806
  uint idx= 0;
809
807
 
810
808
  KEY *keyinfo,*keyinfo_end;
811
809
  for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys ;
815
813
    KEY_PART_INFO *part,*part_end;
816
814
    key_part_map key_part_to_use= 0;
817
815
    /*
818
 
      Perform a check if index is not disabled by ALTER Table
 
816
      Perform a check if index is not disabled by ALTER TABLE
819
817
      or IGNORE INDEX.
820
818
    */
821
819
    if (!table->keys_in_use_for_query.is_set(idx))
822
820
      continue;
823
 
    uint32_t jdx= 0;
 
821
    uint jdx= 0;
824
822
    *prefix_len= 0;
825
823
    for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts ;
826
824
         part != part_end ;
851
849
            /*
852
850
              The query is on this form:
853
851
 
854
 
              SELECT MIN(key_part_k)
855
 
              FROM t1
 
852
              SELECT MIN(key_part_k) 
 
853
              FROM t1 
856
854
              WHERE key_part_1 = const and ... and key_part_k-1 = const
857
855
 
858
856
              If key_part_k is nullable, we want to find the first matching row
905
903
*/
906
904
 
907
905
static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
908
 
                            COND *cond, uint32_t range_fl, uint32_t prefix_len)
 
906
                            COND *cond, uint range_fl, uint prefix_len)
909
907
{
910
908
  if (key_cmp_if_same(field->table, ref->key_buff, ref->key, prefix_len))
911
909
    return 1;