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_ROR_INTERSECT = 4,
195
QS_TYPE_ROR_UNION = 5,
196
QS_TYPE_GROUP_MIN_MAX = 6
199
/* Get type of this quick select - one of the QS_TYPE_* values */
200
virtual int get_type() = 0;
203
Initialize this quick select as a merged scan inside a ROR-union or a ROR-
204
intersection scan. The caller must not additionally call init() if this
207
init_ror_merged_scan()
208
reuse_handler If true, the quick select may use table->handler,
209
otherwise it must create and use a separate handler
215
virtual int init_ror_merged_scan(bool reuse_handler)
216
{ DBUG_ASSERT(0); return 1; }
219
Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
221
virtual void save_last_pos(){};
224
Append comma-separated list of keys this quick select uses to key_names;
225
append comma-separated list of corresponding used lengths to used_lengths.
226
This is used by select_describe.
228
virtual void add_keys_and_lengths(String *key_names,
229
String *used_lengths)=0;
232
Append text representation of quick select structure (what and how is
233
merged) to str. The result is added to "Extra" field in EXPLAIN output.
234
This function is implemented only by quick selects that merge other quick
235
selects output and/or can produce output suitable for merging.
237
virtual void add_info_string(String *str) {};
239
Return 1 if any index used by this quick select
240
uses field which is marked in passed bitmap.
242
virtual bool is_keys_used(const MY_BITMAP *fields);
245
rowid of last row retrieved by this quick select. This is used only when
246
doing ROR-index_merge selects
251
Table record buffer used by this quick select.
256
Print quick select information to DBUG_FILE. Caller is responsible
257
for locking DBUG_FILE before this call and unlocking it afterwards.
259
virtual void dbug_dump(int indent, bool verbose)= 0;
264
struct st_qsel_param;
270
MRR range sequence, array<QUICK_RANGE> implementation: sequence traversal
273
typedef struct st_quick_range_seq_ctx
278
} QUICK_RANGE_SEQ_CTX;
280
range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags);
281
uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
285
Quick select that does a range scan on a single key. The records are
286
returned in key order.
288
class QUICK_RANGE_SELECT : public QUICK_SELECT_I
292
DYNAMIC_ARRAY ranges; /* ordered array of range ptrs */
294
/* Members to deal with case when this quick select is a ROR-merged scan */
295
bool in_ror_merged_scan;
296
MY_BITMAP column_bitmap, *save_read_set, *save_write_set;
297
bool free_file; /* TRUE <=> this->file is "owned" by this quick select */
299
/* Range pointers to be used when not using MRR interface */
300
QUICK_RANGE **cur_range; /* current element in ranges */
301
QUICK_RANGE *last_range;
303
/* Members needed to use the MRR interface */
304
QUICK_RANGE_SEQ_CTX qr_traversal_ctx;
306
uint mrr_flags; /* Flags to be used with MRR interface */
308
uint mrr_buf_size; /* copy from thd->variables.read_rnd_buff_size */
309
HANDLER_BUFFER *mrr_buf_desc; /* the handler buffer */
311
/* Info about index we're scanning */
313
KEY_PART_INFO *key_part_info;
315
bool dont_free; /* Used by QUICK_SELECT_DESC */
317
int cmp_next(QUICK_RANGE *range);
318
int cmp_prev(QUICK_RANGE *range);
319
bool row_in_ranges();
323
QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc,
324
MEM_ROOT *parent_alloc, bool *create_err);
325
~QUICK_RANGE_SELECT();
331
int get_next_prefix(uint prefix_length, key_part_map keypart_map,
333
bool reverse_sorted() { return 0; }
334
bool unique_key_range();
335
int init_ror_merged_scan(bool reuse_handler);
337
{ file->position(record); }
338
int get_type() { return QS_TYPE_RANGE; }
339
void add_keys_and_lengths(String *key_names, String *used_lengths);
340
void add_info_string(String *str);
342
void dbug_dump(int indent, bool verbose);
345
/* Used only by QUICK_SELECT_DESC */
346
QUICK_RANGE_SELECT(const QUICK_RANGE_SELECT& org) : QUICK_SELECT_I()
348
bcopy(&org, this, sizeof(*this));
350
Use default MRR implementation for reverse scans. No table engine
351
currently can do an MRR scan with output in reverse index order.
354
mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
357
friend class TRP_ROR_INTERSECT;
359
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
360
struct st_table_ref *ref,
362
friend bool get_quick_keys(PARAM *param, QUICK_RANGE_SELECT *quick,
363
KEY_PART *key, SEL_ARG *key_tree,
364
uchar *min_key, uint min_key_flag,
365
uchar *max_key, uint max_key_flag);
366
friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx,
371
friend class QUICK_SELECT_DESC;
372
friend class QUICK_INDEX_MERGE_SELECT;
373
friend class QUICK_ROR_INTERSECT_SELECT;
374
friend class QUICK_GROUP_MIN_MAX_SELECT;
375
friend uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
376
friend range_seq_t quick_range_seq_init(void *init_param,
377
uint n_ranges, uint flags);
378
friend void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
379
bool distinct,const char *message);
384
QUICK_INDEX_MERGE_SELECT - index_merge access method quick select.
386
QUICK_INDEX_MERGE_SELECT uses
387
* QUICK_RANGE_SELECTs to get rows
388
* Unique class to remove duplicate rows
390
INDEX MERGE OPTIMIZER
391
Current implementation doesn't detect all cases where index_merge could
392
be used, in particular:
393
* index_merge will never be used if range scan is possible (even if
394
range scan is more expensive)
396
* index_merge+'using index' is not supported (this the consequence of
397
the above restriction)
399
* If WHERE part contains complex nested AND and OR conditions, some ways
400
to retrieve rows using index_merge will not be considered. The choice
401
of read plan may depend on the order of conjuncts/disjuncts in WHERE
402
part of the query, see comments near imerge_list_or_list and
403
SEL_IMERGE::or_sel_tree_with_checks functions for details.
405
* There is no "index_merge_ref" method (but index_merge on non-first
406
table in join is possible with 'range checked for each record').
408
See comments around SEL_IMERGE class and test_quick_select for more
411
ROW RETRIEVAL ALGORITHM
413
index_merge uses Unique class for duplicates removal. index_merge takes
414
advantage of Clustered Primary Key (CPK) if the table has one.
415
The index_merge algorithm consists of two phases:
417
Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique):
420
activate 'index only';
421
while(retrieve next row for non-CPK scan)
423
if (there is a CPK scan and row will be retrieved by it)
426
put its rowid into Unique;
428
deactivate 'index only';
431
Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next
436
retrieve all rows from row pointers stored in Unique;
438
retrieve all rows for CPK scan;
442
class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I
445
QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table);
446
~QUICK_INDEX_MERGE_SELECT();
451
bool reverse_sorted() { return false; }
452
bool unique_key_range() { return false; }
453
int get_type() { return QS_TYPE_INDEX_MERGE; }
454
void add_keys_and_lengths(String *key_names, String *used_lengths);
455
void add_info_string(String *str);
456
bool is_keys_used(const MY_BITMAP *fields);
458
void dbug_dump(int indent, bool verbose);
461
bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
463
/* range quick selects this index_merge read consists of */
464
List<QUICK_RANGE_SELECT> quick_selects;
466
/* quick select that uses clustered primary key (NULL if none) */
467
QUICK_RANGE_SELECT* pk_quick_select;
469
/* true if this select is currently doing a clustered PK scan */
474
int read_keys_and_merge();
476
/* used to get rows collected in Unique */
477
READ_RECORD read_record;
482
Rowid-Ordered Retrieval (ROR) index intersection quick select.
483
This quick select produces intersection of row sequences returned
484
by several QUICK_RANGE_SELECTs it "merges".
486
All merged QUICK_RANGE_SELECTs must return rowids in rowid order.
487
QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too.
489
All merged quick selects retrieve {rowid, covered_fields} tuples (not full
491
QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used
492
by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't
493
cover needed all fields.
495
If one of the merged quick selects is a Clustered PK range scan, it is
496
used only to filter rowid sequence produced by other merged quick selects.
499
class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I
502
QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table,
503
bool retrieve_full_rows,
504
MEM_ROOT *parent_alloc);
505
~QUICK_ROR_INTERSECT_SELECT();
510
bool reverse_sorted() { return false; }
511
bool unique_key_range() { return false; }
512
int get_type() { return QS_TYPE_ROR_INTERSECT; }
513
void add_keys_and_lengths(String *key_names, String *used_lengths);
514
void add_info_string(String *str);
515
bool is_keys_used(const MY_BITMAP *fields);
517
void dbug_dump(int indent, bool verbose);
519
int init_ror_merged_scan(bool reuse_handler);
520
bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
523
Range quick selects this intersection consists of, not including
526
List<QUICK_RANGE_SELECT> quick_selects;
529
Merged quick select that uses Clustered PK, if there is one. This quick
530
select is not used for row retrieval, it is used for row retrieval.
532
QUICK_RANGE_SELECT *cpk_quick;
534
MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
535
THD *thd; /* current thread */
536
bool need_to_fetch_row; /* if true, do retrieve full table records. */
537
/* in top-level quick select, true if merged scans where initialized */
543
Rowid-Ordered Retrieval index union select.
544
This quick select produces union of row sequences returned by several
545
quick select it "merges".
547
All merged quick selects must return rowids in rowid order.
548
QUICK_ROR_UNION_SELECT will return rows in rowid order, too.
550
All merged quick selects are set not to retrieve full table records.
551
ROR-union quick select always retrieves full records.
555
class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I
558
QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table);
559
~QUICK_ROR_UNION_SELECT();
564
bool reverse_sorted() { return false; }
565
bool unique_key_range() { return false; }
566
int get_type() { return QS_TYPE_ROR_UNION; }
567
void add_keys_and_lengths(String *key_names, String *used_lengths);
568
void add_info_string(String *str);
569
bool is_keys_used(const MY_BITMAP *fields);
571
void dbug_dump(int indent, bool verbose);
574
bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
576
List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */
578
QUEUE queue; /* Priority queue for merge operation */
579
MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
581
THD *thd; /* current thread */
582
uchar *cur_rowid; /* buffer used in get_next() */
583
uchar *prev_rowid; /* rowid of last row returned by get_next() */
584
bool have_prev_rowid; /* true if prev_rowid has valid data */
585
uint rowid_length; /* table rowid length */
587
static int queue_cmp(void *arg, uchar *val1, uchar *val2);
593
Index scan for GROUP-BY queries with MIN/MAX aggregate functions.
595
This class provides a specialized index access method for GROUP-BY queries
598
SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
600
WHERE [RNG(A_1,...,A_p ; where p <= k)]
601
[AND EQ(B_1,...,B_m)]
603
[AND PA(A_i1,...,A_iq)]
604
GROUP BY A_1,...,A_k;
608
SELECT DISTINCT A_i1,...,A_ik
610
WHERE [RNG(A_1,...,A_p ; where p <= k)]
611
[AND PA(A_i1,...,A_iq)];
613
where all selected fields are parts of the same index.
614
The class of queries that can be processed by this quick select is fully
615
specified in the description of get_best_trp_group_min_max() in opt_range.cc.
617
The get_next() method directly produces result tuples, thus obviating the
618
need to call end_send_group() because all grouping is already done inside
621
Since one of the requirements is that all select fields are part of the same
622
index, this class produces only index keys, and not complete records.
625
class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I
628
handler *file; /* The handler used to get data. */
629
JOIN *join; /* Descriptor of the current query */
630
KEY *index_info; /* The index chosen for data access */
631
uchar *record; /* Buffer where the next record is returned. */
632
uchar *tmp_record; /* Temporary storage for next_min(), next_max(). */
633
uchar *group_prefix; /* Key prefix consisting of the GROUP fields. */
634
uint group_prefix_len; /* Length of the group prefix. */
635
uint group_key_parts; /* A number of keyparts in the group prefix */
636
uchar *last_prefix; /* Prefix of the last group for detecting EOF. */
637
bool have_min; /* Specify whether we are computing */
638
bool have_max; /* a MIN, a MAX, or both. */
639
bool seen_first_key; /* Denotes whether the first key was retrieved.*/
640
KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */
641
/* of all MIN/MAX functions. */
642
uint min_max_arg_len; /* The length of the MIN/MAX argument field */
643
uchar *key_infix; /* Infix of constants from equality predicates. */
645
DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */
646
uint real_prefix_len; /* Length of key prefix extended with key_infix. */
647
uint real_key_parts; /* A number of keyparts in the above value. */
648
List<Item_sum> *min_functions;
649
List<Item_sum> *max_functions;
650
List_iterator<Item_sum> *min_functions_it;
651
List_iterator<Item_sum> *max_functions_it;
654
The following two members are public to allow easy access from
655
TRP_GROUP_MIN_MAX::make_quick()
657
MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */
658
QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */
661
int next_min_in_range();
662
int next_max_in_range();
665
void update_min_result();
666
void update_max_result();
668
QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min,
669
bool have_max, KEY_PART_INFO *min_max_arg_part,
670
uint group_prefix_len, uint group_key_parts,
671
uint used_key_parts, KEY *index_info, uint
672
use_index, double read_cost, ha_rows records, uint
673
key_infix_len, uchar *key_infix, MEM_ROOT
675
~QUICK_GROUP_MIN_MAX_SELECT();
676
bool add_range(SEL_ARG *sel_range);
677
void update_key_stat();
678
void adjust_prefix_ranges();
679
bool alloc_buffers();
683
bool reverse_sorted() { return false; }
684
bool unique_key_range() { return false; }
685
int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
686
void add_keys_and_lengths(String *key_names, String *used_lengths);
688
void dbug_dump(int indent, bool verbose);
693
class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
696
QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts,
699
bool reverse_sorted() { return 1; }
700
int get_type() { return QS_TYPE_RANGE_DESC; }
702
bool range_reads_after_key(QUICK_RANGE *range);
704
bool test_if_null_range(QUICK_RANGE *range, uint used_key_parts);
706
int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
707
List<QUICK_RANGE> rev_ranges;
708
List_iterator<QUICK_RANGE> rev_it;
712
class SQL_SELECT :public Sql_alloc {
714
QUICK_SELECT_I *quick; // If quick-select used
715
COND *cond; // where condition
717
IO_CACHE file; // Positions to used records
718
ha_rows records; // Records in use if read from file
719
double read_time; // Time to read rows
720
key_map quick_keys; // Possible quick keys
721
key_map needed_reg; // Possible quick keys after prev tables.
722
table_map const_tables,read_tables;
728
bool check_quick(THD *thd, bool force_quick_range, ha_rows limit)
732
return test_quick_select(thd, tmp, 0, limit, force_quick_range, FALSE) < 0;
734
inline bool skip_record() { return cond ? cond->val_int() == 0 : 0; }
735
int test_quick_select(THD *thd, key_map keys, table_map prev_tables,
736
ha_rows limit, bool force_quick_range,
737
bool ordered_output);
740
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
741
struct st_table_ref *ref,
743
uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit);
added
removed
sql/opt_range.h
