1
/* Copyright (C) 2000-2006 MySQL AB
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.
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.
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 */
17
/* classes to use when handling where clause */
22
#ifdef USE_PRAGMA_INTERFACE
23
#pragma interface /* gcc class implementation */
26
typedef struct st_key_part {
28
/* See KEY_PART_INFO for meaning of the next two: */
29
uint16 store_length, length;
32
Keypart flags (0 when this structure is used by partition pruning code
33
for fake partitioning index description)
37
Field::imagetype image_type;
41
class QUICK_RANGE :public Sql_alloc {
43
uchar *min_key,*max_key;
44
uint16 min_length,max_length,flag;
45
key_part_map min_keypart_map, // bitmap of used keyparts in min_key
46
max_keypart_map; // bitmap of used keyparts in max_key
48
uint16 dummy; /* Avoid warnings on 'flag' */
50
QUICK_RANGE(); /* Full range */
51
QUICK_RANGE(const uchar *min_key_arg, uint min_length_arg,
52
key_part_map min_keypart_map_arg,
53
const uchar *max_key_arg, uint max_length_arg,
54
key_part_map max_keypart_map_arg,
56
: min_key((uchar*) sql_memdup(min_key_arg,min_length_arg+1)),
57
max_key((uchar*) sql_memdup(max_key_arg,max_length_arg+1)),
58
min_length((uint16) min_length_arg),
59
max_length((uint16) max_length_arg),
60
flag((uint16) flag_arg),
61
min_keypart_map(min_keypart_map_arg),
62
max_keypart_map(max_keypart_map_arg)
72
Quick select interface.
73
This class is a parent for all QUICK_*_SELECT and FT_SELECT classes.
75
The usage scenario is as follows:
76
1. Create quick select
77
quick= new QUICK_XXX_SELECT(...);
79
2. Perform lightweight initialization. This can be done in 2 ways:
80
2.a: Regular initialization
83
//the only valid action after failed init() call is delete
86
2.b: Special initialization for quick selects merged by QUICK_ROR_*_SELECT
87
if (quick->init_ror_merged_scan())
90
3. Perform zero, one, or more scans.
93
// initialize quick select for scan. This may allocate
94
// buffers and/or prefetch rows.
97
//the only valid action after failed reset() call is delete
105
res= quick->get_next();
109
4. Delete the select:
118
ha_rows records; /* estimate of # of records to be retrieved */
119
double read_time; /* time to perform this retrieval */
122
Index this quick select uses, or MAX_KEY for quick selects
123
that use several indexes
128
Total length of first used_key_parts parts of the key.
129
Applicable if index!= MAX_KEY.
131
uint max_used_key_length;
134
Max. number of (first) key parts this quick select uses for retrieval.
135
eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2.
136
Applicable if index!= MAX_KEY.
138
For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts.
143
virtual ~QUICK_SELECT_I(){};
146
Do post-constructor initialization.
150
init() performs initializations that should have been in constructor if
151
it was possible to return errors from constructors. The join optimizer may
152
create and then delete quick selects without retrieving any rows so init()
153
must not contain any IO or CPU intensive code.
155
If init() call fails the only valid action is to delete this quick select,
156
reset() and get_next() must not be called.
162
virtual int init() = 0;
165
Initialize quick select for row retrieval.
169
reset() should be called when it is certain that row retrieval will be
170
necessary. This call may do heavyweight initialization like buffering first
171
N records etc. If reset() call fails get_next() must not be called.
172
Note that reset() may be called several times if
173
* the quick select is executed in a subselect
174
* a JOIN buffer is used
180
virtual int reset(void) = 0;
182
virtual int get_next() = 0; /* get next record to retrieve */
184
/* Range end should be called when we have looped over the whole index */
185
virtual void range_end() {}
187
virtual bool reverse_sorted() = 0;
188
virtual bool unique_key_range() { return false; }
192
QS_TYPE_INDEX_MERGE = 1,
193
QS_TYPE_RANGE_DESC = 2,
194
QS_TYPE_FULLTEXT = 3,
195
QS_TYPE_ROR_INTERSECT = 4,
196
QS_TYPE_ROR_UNION = 5,
197
QS_TYPE_GROUP_MIN_MAX = 6
200
/* Get type of this quick select - one of the QS_TYPE_* values */
201
virtual int get_type() = 0;
204
Initialize this quick select as a merged scan inside a ROR-union or a ROR-
205
intersection scan. The caller must not additionally call init() if this
208
init_ror_merged_scan()
209
reuse_handler If true, the quick select may use table->handler,
210
otherwise it must create and use a separate handler
216
virtual int init_ror_merged_scan(bool reuse_handler)
217
{ DBUG_ASSERT(0); return 1; }
220
Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
222
virtual void save_last_pos(){};
225
Append comma-separated list of keys this quick select uses to key_names;
226
append comma-separated list of corresponding used lengths to used_lengths.
227
This is used by select_describe.
229
virtual void add_keys_and_lengths(String *key_names,
230
String *used_lengths)=0;
233
Append text representation of quick select structure (what and how is
234
merged) to str. The result is added to "Extra" field in EXPLAIN output.
235
This function is implemented only by quick selects that merge other quick
236
selects output and/or can produce output suitable for merging.
238
virtual void add_info_string(String *str) {};
240
Return 1 if any index used by this quick select
241
uses field which is marked in passed bitmap.
243
virtual bool is_keys_used(const MY_BITMAP *fields);
246
rowid of last row retrieved by this quick select. This is used only when
247
doing ROR-index_merge selects
252
Table record buffer used by this quick select.
257
Print quick select information to DBUG_FILE. Caller is responsible
258
for locking DBUG_FILE before this call and unlocking it afterwards.
260
virtual void dbug_dump(int indent, bool verbose)= 0;
265
struct st_qsel_param;
270
Quick select that does a range scan on a single key. The records are
271
returned in key order.
273
class QUICK_RANGE_SELECT : public QUICK_SELECT_I
276
bool next,dont_free,in_ror_merged_scan;
282
If true, this quick select has its "own" handler object which should be
283
closed no later then this quick select is deleted.
287
uint multi_range_count; /* copy from thd->variables.multi_range_count */
288
uint multi_range_length; /* the allocated length for the array */
289
uint multi_range_bufsiz; /* copy from thd->variables.read_rnd_buff_size */
290
KEY_MULTI_RANGE *multi_range; /* the multi-range array (allocated and
291
freed by QUICK_RANGE_SELECT) */
292
HANDLER_BUFFER *multi_range_buff; /* the handler buffer (allocated and
293
freed by QUICK_RANGE_SELECT) */
294
MY_BITMAP column_bitmap, *save_read_set, *save_write_set;
296
friend class TRP_ROR_INTERSECT;
298
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
299
struct st_table_ref *ref,
301
friend bool get_quick_keys(PARAM *param,
302
QUICK_RANGE_SELECT *quick,KEY_PART *key,
304
uchar *min_key, uint min_key_flag,
305
uchar *max_key, uint max_key_flag);
306
friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx,
309
friend class QUICK_SELECT_DESC;
310
friend class QUICK_INDEX_MERGE_SELECT;
311
friend class QUICK_ROR_INTERSECT_SELECT;
312
friend class QUICK_GROUP_MIN_MAX_SELECT;
314
DYNAMIC_ARRAY ranges; /* ordered array of range ptrs */
315
QUICK_RANGE **cur_range; /* current element in ranges */
317
QUICK_RANGE *last_range;
319
KEY_PART_INFO *key_part_info;
320
int cmp_next(QUICK_RANGE *range);
321
int cmp_prev(QUICK_RANGE *range);
322
bool row_in_ranges();
326
QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc=0,
327
MEM_ROOT *parent_alloc=NULL);
328
~QUICK_RANGE_SELECT();
334
int get_next_prefix(uint prefix_length, key_part_map keypart_map,
336
bool reverse_sorted() { return 0; }
337
bool unique_key_range();
338
int init_ror_merged_scan(bool reuse_handler);
340
{ file->position(record); }
341
int get_type() { return QS_TYPE_RANGE; }
342
void add_keys_and_lengths(String *key_names, String *used_lengths);
343
void add_info_string(String *str);
345
void dbug_dump(int indent, bool verbose);
348
/* Default copy ctor used by QUICK_SELECT_DESC */
352
class QUICK_RANGE_SELECT_GEOM: public QUICK_RANGE_SELECT
355
QUICK_RANGE_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg,
356
bool no_alloc, MEM_ROOT *parent_alloc)
357
:QUICK_RANGE_SELECT(thd, table, index_arg, no_alloc, parent_alloc)
359
virtual int get_next();
364
QUICK_INDEX_MERGE_SELECT - index_merge access method quick select.
366
QUICK_INDEX_MERGE_SELECT uses
367
* QUICK_RANGE_SELECTs to get rows
368
* Unique class to remove duplicate rows
370
INDEX MERGE OPTIMIZER
371
Current implementation doesn't detect all cases where index_merge could
372
be used, in particular:
373
* index_merge will never be used if range scan is possible (even if
374
range scan is more expensive)
376
* index_merge+'using index' is not supported (this the consequence of
377
the above restriction)
379
* If WHERE part contains complex nested AND and OR conditions, some ways
380
to retrieve rows using index_merge will not be considered. The choice
381
of read plan may depend on the order of conjuncts/disjuncts in WHERE
382
part of the query, see comments near imerge_list_or_list and
383
SEL_IMERGE::or_sel_tree_with_checks functions for details.
385
* There is no "index_merge_ref" method (but index_merge on non-first
386
table in join is possible with 'range checked for each record').
388
See comments around SEL_IMERGE class and test_quick_select for more
391
ROW RETRIEVAL ALGORITHM
393
index_merge uses Unique class for duplicates removal. index_merge takes
394
advantage of Clustered Primary Key (CPK) if the table has one.
395
The index_merge algorithm consists of two phases:
397
Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique):
400
activate 'index only';
401
while(retrieve next row for non-CPK scan)
403
if (there is a CPK scan and row will be retrieved by it)
406
put its rowid into Unique;
408
deactivate 'index only';
411
Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next
416
retrieve all rows from row pointers stored in Unique;
418
retrieve all rows for CPK scan;
422
class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I
425
QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table);
426
~QUICK_INDEX_MERGE_SELECT();
431
bool reverse_sorted() { return false; }
432
bool unique_key_range() { return false; }
433
int get_type() { return QS_TYPE_INDEX_MERGE; }
434
void add_keys_and_lengths(String *key_names, String *used_lengths);
435
void add_info_string(String *str);
436
bool is_keys_used(const MY_BITMAP *fields);
438
void dbug_dump(int indent, bool verbose);
441
bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
443
/* range quick selects this index_merge read consists of */
444
List<QUICK_RANGE_SELECT> quick_selects;
446
/* quick select that uses clustered primary key (NULL if none) */
447
QUICK_RANGE_SELECT* pk_quick_select;
449
/* true if this select is currently doing a clustered PK scan */
454
int read_keys_and_merge();
456
/* used to get rows collected in Unique */
457
READ_RECORD read_record;
462
Rowid-Ordered Retrieval (ROR) index intersection quick select.
463
This quick select produces intersection of row sequences returned
464
by several QUICK_RANGE_SELECTs it "merges".
466
All merged QUICK_RANGE_SELECTs must return rowids in rowid order.
467
QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too.
469
All merged quick selects retrieve {rowid, covered_fields} tuples (not full
471
QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used
472
by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't
473
cover needed all fields.
475
If one of the merged quick selects is a Clustered PK range scan, it is
476
used only to filter rowid sequence produced by other merged quick selects.
479
class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I
482
QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table,
483
bool retrieve_full_rows,
484
MEM_ROOT *parent_alloc);
485
~QUICK_ROR_INTERSECT_SELECT();
490
bool reverse_sorted() { return false; }
491
bool unique_key_range() { return false; }
492
int get_type() { return QS_TYPE_ROR_INTERSECT; }
493
void add_keys_and_lengths(String *key_names, String *used_lengths);
494
void add_info_string(String *str);
495
bool is_keys_used(const MY_BITMAP *fields);
497
void dbug_dump(int indent, bool verbose);
499
int init_ror_merged_scan(bool reuse_handler);
500
bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
503
Range quick selects this intersection consists of, not including
506
List<QUICK_RANGE_SELECT> quick_selects;
509
Merged quick select that uses Clustered PK, if there is one. This quick
510
select is not used for row retrieval, it is used for row retrieval.
512
QUICK_RANGE_SELECT *cpk_quick;
514
MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
515
THD *thd; /* current thread */
516
bool need_to_fetch_row; /* if true, do retrieve full table records. */
517
/* in top-level quick select, true if merged scans where initialized */
523
Rowid-Ordered Retrieval index union select.
524
This quick select produces union of row sequences returned by several
525
quick select it "merges".
527
All merged quick selects must return rowids in rowid order.
528
QUICK_ROR_UNION_SELECT will return rows in rowid order, too.
530
All merged quick selects are set not to retrieve full table records.
531
ROR-union quick select always retrieves full records.
535
class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I
538
QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table);
539
~QUICK_ROR_UNION_SELECT();
544
bool reverse_sorted() { return false; }
545
bool unique_key_range() { return false; }
546
int get_type() { return QS_TYPE_ROR_UNION; }
547
void add_keys_and_lengths(String *key_names, String *used_lengths);
548
void add_info_string(String *str);
549
bool is_keys_used(const MY_BITMAP *fields);
551
void dbug_dump(int indent, bool verbose);
554
bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
556
List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */
558
QUEUE queue; /* Priority queue for merge operation */
559
MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
561
THD *thd; /* current thread */
562
uchar *cur_rowid; /* buffer used in get_next() */
563
uchar *prev_rowid; /* rowid of last row returned by get_next() */
564
bool have_prev_rowid; /* true if prev_rowid has valid data */
565
uint rowid_length; /* table rowid length */
567
static int queue_cmp(void *arg, uchar *val1, uchar *val2);
573
Index scan for GROUP-BY queries with MIN/MAX aggregate functions.
575
This class provides a specialized index access method for GROUP-BY queries
578
SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
580
WHERE [RNG(A_1,...,A_p ; where p <= k)]
581
[AND EQ(B_1,...,B_m)]
583
[AND PA(A_i1,...,A_iq)]
584
GROUP BY A_1,...,A_k;
588
SELECT DISTINCT A_i1,...,A_ik
590
WHERE [RNG(A_1,...,A_p ; where p <= k)]
591
[AND PA(A_i1,...,A_iq)];
593
where all selected fields are parts of the same index.
594
The class of queries that can be processed by this quick select is fully
595
specified in the description of get_best_trp_group_min_max() in opt_range.cc.
597
The get_next() method directly produces result tuples, thus obviating the
598
need to call end_send_group() because all grouping is already done inside
601
Since one of the requirements is that all select fields are part of the same
602
index, this class produces only index keys, and not complete records.
605
class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I
608
handler *file; /* The handler used to get data. */
609
JOIN *join; /* Descriptor of the current query */
610
KEY *index_info; /* The index chosen for data access */
611
uchar *record; /* Buffer where the next record is returned. */
612
uchar *tmp_record; /* Temporary storage for next_min(), next_max(). */
613
uchar *group_prefix; /* Key prefix consisting of the GROUP fields. */
614
uint group_prefix_len; /* Length of the group prefix. */
615
uint group_key_parts; /* A number of keyparts in the group prefix */
616
uchar *last_prefix; /* Prefix of the last group for detecting EOF. */
617
bool have_min; /* Specify whether we are computing */
618
bool have_max; /* a MIN, a MAX, or both. */
619
bool seen_first_key; /* Denotes whether the first key was retrieved.*/
620
KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */
621
/* of all MIN/MAX functions. */
622
uint min_max_arg_len; /* The length of the MIN/MAX argument field */
623
uchar *key_infix; /* Infix of constants from equality predicates. */
625
DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */
626
uint real_prefix_len; /* Length of key prefix extended with key_infix. */
627
uint real_key_parts; /* A number of keyparts in the above value. */
628
List<Item_sum> *min_functions;
629
List<Item_sum> *max_functions;
630
List_iterator<Item_sum> *min_functions_it;
631
List_iterator<Item_sum> *max_functions_it;
634
The following two members are public to allow easy access from
635
TRP_GROUP_MIN_MAX::make_quick()
637
MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */
638
QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */
641
int next_min_in_range();
642
int next_max_in_range();
645
void update_min_result();
646
void update_max_result();
648
QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min,
649
bool have_max, KEY_PART_INFO *min_max_arg_part,
650
uint group_prefix_len, uint group_key_parts,
651
uint used_key_parts, KEY *index_info, uint
652
use_index, double read_cost, ha_rows records, uint
653
key_infix_len, uchar *key_infix, MEM_ROOT
655
~QUICK_GROUP_MIN_MAX_SELECT();
656
bool add_range(SEL_ARG *sel_range);
657
void update_key_stat();
658
void adjust_prefix_ranges();
659
bool alloc_buffers();
663
bool reverse_sorted() { return false; }
664
bool unique_key_range() { return false; }
665
int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
666
void add_keys_and_lengths(String *key_names, String *used_lengths);
668
void dbug_dump(int indent, bool verbose);
673
class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
676
QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts);
678
bool reverse_sorted() { return 1; }
679
int get_type() { return QS_TYPE_RANGE_DESC; }
681
bool range_reads_after_key(QUICK_RANGE *range);
682
int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
683
List<QUICK_RANGE> rev_ranges;
684
List_iterator<QUICK_RANGE> rev_it;
689
class SQL_SELECT :public Sql_alloc {
691
QUICK_SELECT_I *quick; // If quick-select used
692
COND *cond; // where condition
694
IO_CACHE file; // Positions to used records
695
ha_rows records; // Records in use if read from file
696
double read_time; // Time to read rows
697
key_map quick_keys; // Possible quick keys
698
key_map needed_reg; // Possible quick keys after prev tables.
699
table_map const_tables,read_tables;
705
bool check_quick(THD *thd, bool force_quick_range, ha_rows limit)
709
return test_quick_select(thd, tmp, 0, limit, force_quick_range) < 0;
711
inline bool skip_record() { return cond ? cond->val_int() == 0 : 0; }
712
int test_quick_select(THD *thd, key_map keys, table_map prev_tables,
713
ha_rows limit, bool force_quick_range);
717
class FT_SELECT: public QUICK_RANGE_SELECT {
719
FT_SELECT(THD *thd, TABLE *table, uint key) :
720
QUICK_RANGE_SELECT (thd, table, key, 1) { VOID(init()); }
721
~FT_SELECT() { file->ft_end(); }
722
int init() { return error=file->ft_init(); }
723
int reset() { return 0; }
724
int get_next() { return error=file->ft_read(record); }
725
int get_type() { return QS_TYPE_FULLTEXT; }
728
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
729
struct st_table_ref *ref,
731
uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit);
733
#ifdef WITH_PARTITION_STORAGE_ENGINE
734
bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond);
735
void store_key_image_to_rec(Field *field, uchar *ptr, uint len);
added
removed
sql/opt_range.h
