← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_sum.cc

  • Committer: Brian Aker
  • Date: 2009-10-01 22:56:26 UTC
  • mto: (1154.1.1 staging)
  • mto: This revision was merged to the branch mainline in revision 1155.
  • Revision ID: brian@gaz-20091001225626-sb1pdykpxlnkheaj
Remove Factory/make scheduler work like everything else.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/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)
49
49
 
50
50
#include <drizzled/server_includes.h>
51
51
#include <drizzled/sql_select.h>
 
52
#include <drizzled/item/sum.h>
 
53
#include <drizzled/item/cmpfunc.h>
52
54
 
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);
 
55
static bool find_key_for_maxmin(bool max_fl, table_reference_st *ref, Field* field,
 
56
                                COND *cond, uint32_t *range_fl,
 
57
                                uint32_t *key_prefix_length);
 
58
static int reckey_in_range(bool max_fl, table_reference_st *ref, Field* field,
 
59
                            COND *cond, uint32_t range_fl, uint32_t prefix_len);
58
60
static int maxmin_in_range(bool max_fl, Field* field, COND *cond);
59
61
 
60
62
 
74
76
    #                   Multiplication of number of rows in all tables
75
77
*/
76
78
 
77
 
static uint64_t get_exact_record_count(TABLE_LIST *tables)
 
79
static uint64_t get_exact_record_count(TableList *tables)
78
80
{
79
81
  uint64_t count= 1;
80
 
  for (TABLE_LIST *tl= tables; tl; tl= tl->next_leaf)
 
82
  for (TableList *tl= tables; tl; tl= tl->next_leaf)
81
83
  {
82
84
    ha_rows tmp= tl->table->file->records();
83
85
    if ((tmp == HA_POS_ERROR))
109
111
    HA_ERR_... if a deadlock or a lock wait timeout happens, for example
110
112
*/
111
113
 
112
 
int opt_sum_query(TABLE_LIST *tables, List<Item> &all_fields,COND *conds)
 
114
int opt_sum_query(TableList *tables, List<Item> &all_fields,COND *conds)
113
115
{
114
116
  List_iterator_fast<Item> it(all_fields);
115
117
  int const_result= 1;
128
130
    Analyze outer join dependencies, and, if possible, compute the number
129
131
    of returned rows.
130
132
  */
131
 
  for (TABLE_LIST *tl= tables; tl; tl= tl->next_leaf)
 
133
  for (TableList *tl= tables; tl; tl= tl->next_leaf)
132
134
  {
133
 
    TABLE_LIST *embedded;
 
135
    TableList *embedded;
134
136
    for (embedded= tl ; embedded; embedded= embedded->embedding)
135
137
    {
136
138
      if (embedded->on_expr)
158
160
      statistics (cheap), compute the total number of rows. If there are
159
161
      no outer table dependencies, this count may be used as the real count.
160
162
      Schema tables are filled after this function is invoked, so we can't
161
 
      get row count 
 
163
      get row count
162
164
    */
163
165
    if (!(tl->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) ||
164
166
        tl->schema_table)
211
213
            }
212
214
            is_exact_count= 1;                  // count is now exact
213
215
          }
214
 
          ((Item_sum_count*) item)->make_const((int64_t) count);
 
216
          ((Item_sum_count*) item)->make_const_count((int64_t) count);
215
217
          recalc_const_item= 1;
216
218
        }
217
219
        else
227
229
        Item *expr=item_sum->args[0];
228
230
        if (expr->real_item()->type() == Item::FIELD_ITEM)
229
231
        {
230
 
          uchar key_buff[MAX_KEY_LENGTH];
231
 
          TABLE_REF ref;
232
 
          uint range_fl, prefix_len;
 
232
          unsigned char key_buff[MAX_KEY_LENGTH];
 
233
          table_reference_st ref;
 
234
          uint32_t range_fl, prefix_len;
233
235
 
234
236
          ref.key_buff= key_buff;
235
237
          Item_field *item_field= (Item_field*) (expr->real_item());
236
 
          TABLE *table= item_field->field->table;
 
238
          Table *table= item_field->field->table;
237
239
 
238
 
          /* 
 
240
          /*
239
241
            Look for a partial key that can be used for optimization.
240
242
            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
            this key, while prefix_len will contain the length of
 
244
            the beginning of this key without field used in MIN().
243
245
            Type of range for the key part for this field will be
244
246
            returned in range_fl.
245
247
          */
250
252
            const_result= 0;
251
253
            break;
252
254
          }
253
 
          error= table->file->ha_index_init((uint) ref.key, 1);
 
255
          error= table->file->ha_index_init((uint32_t) ref.key, 1);
254
256
 
255
257
          if (!ref.key_length)
256
258
            error= table->file->index_first(table->record[0]);
257
 
          else 
 
259
          else
258
260
          {
259
261
            /*
260
262
              Use index to replace MIN/MAX functions with their values
261
263
              according to the following rules:
262
 
           
 
264
 
263
265
              1) Insert the minimum non-null values where the WHERE clause still
264
266
                 matches, or
265
267
              2) a NULL value if there are only NULL values for key_part_k.
271
273
              nullable column, test if there is an exact match for the key.
272
274
            */
273
275
            if (!(range_fl & NEAR_MIN))
274
 
              /* 
 
276
              /*
275
277
                 Closed interval: Either The MIN argument is non-nullable, or
276
278
                 we have a >= predicate for the MIN argument.
277
279
              */
288
290
                We need to scan the next bigger record first.
289
291
              */
290
292
              error= table->file->index_read_map(table->record[0],
291
 
                                                 ref.key_buff, 
 
293
                                                 ref.key_buff,
292
294
                                                 make_prev_keypart_map(ref.key_parts),
293
295
                                                 HA_READ_AFTER_KEY);
294
 
              /* 
 
296
              /*
295
297
                 If the found record is outside the group formed by the search
296
298
                 prefix, or there is no such record at all, check if all
297
299
                 records in that group have NULL in the MIN argument
321
323
            }
322
324
          }
323
325
          /* Verify that the read tuple indeed matches the search key */
324
 
          if (!error && reckey_in_range(0, &ref, item_field->field, 
 
326
          if (!error && reckey_in_range(0, &ref, item_field->field,
325
327
                                        conds, range_fl, prefix_len))
326
328
            error= HA_ERR_KEY_NOT_FOUND;
327
329
          if (table->key_read)
375
377
        Item *expr=item_sum->args[0];
376
378
        if (expr->real_item()->type() == Item::FIELD_ITEM)
377
379
        {
378
 
          uchar key_buff[MAX_KEY_LENGTH];
379
 
          TABLE_REF ref;
380
 
          uint range_fl, prefix_len;
 
380
          unsigned char key_buff[MAX_KEY_LENGTH];
 
381
          table_reference_st ref;
 
382
          uint32_t range_fl, prefix_len;
381
383
 
382
384
          ref.key_buff= key_buff;
383
385
          Item_field *item_field= (Item_field*) (expr->real_item());
384
 
          TABLE *table= item_field->field->table;
 
386
          Table *table= item_field->field->table;
385
387
 
386
 
          /* 
 
388
          /*
387
389
            Look for a partial key that can be used for optimization.
388
390
            If we succeed, ref.key_length will contain the length of
389
 
            this key, while prefix_len will contain the length of 
 
391
            this key, while prefix_len will contain the length of
390
392
            the beginning of this key without field used in MAX().
391
393
            Type of range for the key part for this field will be
392
394
            returned in range_fl.
398
400
            const_result= 0;
399
401
            break;
400
402
          }
401
 
          error= table->file->ha_index_init((uint) ref.key, 1);
 
403
          error= table->file->ha_index_init((uint32_t) ref.key, 1);
402
404
 
403
405
          if (!ref.key_length)
404
406
            error= table->file->index_last(table->record[0]);
591
593
    1        We can use index to get MIN/MAX value
592
594
*/
593
595
 
594
 
static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo, 
 
596
static bool matching_cond(bool max_fl, table_reference_st *ref, KEY *keyinfo,
595
597
                          KEY_PART_INFO *field_part, COND *cond,
596
 
                          key_part_map *key_part_used, uint *range_fl,
597
 
                          uint *prefix_len)
 
598
                          key_part_map *key_part_used, uint32_t *range_fl,
 
599
                          uint32_t *prefix_len)
598
600
{
599
601
  if (!cond)
600
602
    return 1;
601
603
  Field *field= field_part->field;
 
604
 
 
605
  field->setWriteSet();
 
606
 
602
607
  if (!(cond->used_tables() & field->table->map))
603
608
  {
604
609
    /* Condition doesn't restrict the used table */
625
630
    return 0;                                 // Not operator, can't optimize
626
631
 
627
632
  bool eq_type= 0;                            // =, <=> or IS NULL
628
 
  bool noeq_type= 0;                          // < or >  
629
 
  bool less_fl= 0;                            // < or <= 
 
633
  bool noeq_type= 0;                          // < or >
 
634
  bool less_fl= 0;                            // < or <=
630
635
  bool is_null= 0;
631
636
  bool between= 0;
632
637
 
640
645
  case Item_func::LT_FUNC:
641
646
    noeq_type= 1;   /* fall through */
642
647
  case Item_func::LE_FUNC:
643
 
    less_fl= 1;      
 
648
    less_fl= 1;
644
649
    break;
645
650
  case Item_func::GT_FUNC:
646
651
    noeq_type= 1;   /* fall through */
655
660
  default:
656
661
    return 0;                                        // Can't optimize function
657
662
  }
658
 
  
 
663
 
659
664
  Item *args[3];
660
665
  bool inv;
661
666
 
667
672
    less_fl= 1-less_fl;                         // Convert '<' -> '>' (etc)
668
673
 
669
674
  /* Check if field is part of the tested partial key */
670
 
  uchar *key_ptr= ref->key_buff;
 
675
  unsigned char *key_ptr= ref->key_buff;
671
676
  KEY_PART_INFO *part;
672
677
  for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
673
678
 
685
690
  key_part_map org_key_part_used= *key_part_used;
686
691
  if (eq_type || between || max_fl == less_fl)
687
692
  {
688
 
    uint length= (key_ptr-ref->key_buff)+part->store_length;
 
693
    uint32_t length= (key_ptr-ref->key_buff)+part->store_length;
689
694
    if (ref->key_length < length)
690
695
    {
691
696
    /* Ultimately ref->key_length will contain the length of the search key */
692
 
      ref->key_length= length;      
 
697
      ref->key_length= length;
693
698
      ref->key_parts= (part - keyinfo->key_part) + 1;
694
699
    }
695
 
    if (!*prefix_len && part+1 == field_part)       
 
700
    if (!*prefix_len && part+1 == field_part)
696
701
      *prefix_len= length;
697
702
    if (is_field_part && eq_type)
698
703
      *prefix_len= ref->key_length;
699
 
  
 
704
 
700
705
    *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
701
706
  }
702
707
 
703
708
  if (org_key_part_used != *key_part_used ||
704
 
      (is_field_part && 
 
709
      (is_field_part &&
705
710
       (between || eq_type || max_fl == less_fl) && !cond->val_int()))
706
711
  {
707
712
    /*
708
713
      It's the first predicate for this part or a predicate of the
709
714
      following form  that moves upper/lower bounds for max/min values:
710
715
      - field BETWEEN const AND const
711
 
      - field = const 
 
716
      - field = const
712
717
      - field {<|<=} const, when searching for MAX
713
718
      - field {>|>=} const, when searching for MIN
714
719
    */
716
721
    if (is_null)
717
722
    {
718
723
      part->field->set_null();
719
 
      *key_ptr= (uchar) 1;
 
724
      *key_ptr= (unsigned char) 1;
720
725
    }
721
726
    else
722
727
    {
723
728
      store_val_in_field(part->field, args[between && max_fl ? 2 : 1],
724
729
                         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);
 
730
      if (part->null_bit)
 
731
        *key_ptr++= (unsigned char) test(part->field->is_null());
 
732
      part->field->get_key_image(key_ptr, part->length);
728
733
    }
729
734
    if (is_field_part)
730
735
    {
748
753
  }
749
754
  else if (is_field_part)
750
755
    *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
751
 
  return 1;  
 
756
  return 1;
752
757
}
753
758
 
754
759
 
762
767
     -# for each previous component f_i there is one and only one conjunct
763
768
        of the form: f_i= const_i or const_i= f_i or f_i is null
764
769
     -# references to field occur only in conjucts of the form:
765
 
        field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or 
 
770
        field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or
766
771
        field BETWEEN const1 AND const2
767
772
     -# all references to the columns from the same table as column field
768
773
        occur only in conjucts mentioned above.
794
799
    In this case ref, range_fl and prefix_len are updated
795
800
*/
796
801
 
797
 
      
798
 
static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
 
802
 
 
803
static bool find_key_for_maxmin(bool max_fl, table_reference_st *ref,
799
804
                                Field* field, COND *cond,
800
 
                                uint *range_fl, uint *prefix_len)
 
805
                                uint32_t *range_fl, uint32_t *prefix_len)
801
806
{
802
807
  if (!(field->flags & PART_KEY_FLAG))
803
808
    return 0;                                        // Not key field
804
809
 
805
 
  TABLE *table= field->table;
806
 
  uint idx= 0;
 
810
  Table *table= field->table;
 
811
  uint32_t idx= 0;
807
812
 
808
813
  KEY *keyinfo,*keyinfo_end;
809
814
  for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys ;
813
818
    KEY_PART_INFO *part,*part_end;
814
819
    key_part_map key_part_to_use= 0;
815
820
    /*
816
 
      Perform a check if index is not disabled by ALTER TABLE
 
821
      Perform a check if index is not disabled by ALTER Table
817
822
      or IGNORE INDEX.
818
823
    */
819
 
    if (!table->keys_in_use_for_query.is_set(idx))
 
824
    if (!table->keys_in_use_for_query.test(idx))
820
825
      continue;
821
 
    uint jdx= 0;
 
826
    uint32_t jdx= 0;
822
827
    *prefix_len= 0;
823
828
    for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts ;
824
829
         part != part_end ;
829
834
 
830
835
      /* Check whether the index component is partial */
831
836
      Field *part_field= table->field[part->fieldnr-1];
 
837
      part_field->setWriteSet();
 
838
 
832
839
      if ((part_field->flags & BLOB_FLAG) ||
833
840
          part->length < part_field->key_length())
834
841
        break;
849
856
            /*
850
857
              The query is on this form:
851
858
 
852
 
              SELECT MIN(key_part_k) 
853
 
              FROM t1 
 
859
              SELECT MIN(key_part_k)
 
860
              FROM t1
854
861
              WHERE key_part_1 = const and ... and key_part_k-1 = const
855
862
 
856
863
              If key_part_k is nullable, we want to find the first matching row
872
879
            The following test is false when the key in the key tree is
873
880
            converted (for example to upper case)
874
881
          */
875
 
          if (field->part_of_key.is_set(idx))
 
882
          if (field->part_of_key.test(idx))
876
883
          {
877
884
            table->key_read= 1;
878
885
            table->file->extra(HA_EXTRA_KEYREAD);
902
909
    1        WHERE was not true for the found row
903
910
*/
904
911
 
905
 
static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
906
 
                            COND *cond, uint range_fl, uint prefix_len)
 
912
static int reckey_in_range(bool max_fl, table_reference_st *ref, Field* field,
 
913
                            COND *cond, uint32_t range_fl, uint32_t prefix_len)
907
914
{
908
915
  if (key_cmp_if_same(field->table, ref->key_buff, ref->key, prefix_len))
909
916
    return 1;