1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
*
* Copyright (C) 2008-2009 Sun Microsystems, Inc.
*
* 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
* the Free Software Foundation; version 2 of the License.
*
* 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.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#pragma once
#include <drizzled/optimizer/range.h>
#include <drizzled/records.h>
#include <boost/dynamic_bitset.hpp>
#include <vector>
namespace drizzled
{
namespace optimizer
{
/**
@class QuickIndexMergeSelect - index_merge access method quick select.
QuickIndexMergeSelect uses
* QuickRangeSelects to get rows
* Unique class to remove duplicate rows
INDEX MERGE OPTIMIZER
Current implementation doesn't detect all cases where index_merge could
be used, in particular:
* index_merge will never be used if range scan is possible (even if
range scan is more expensive)
* index_merge+'using index' is not supported (this the consequence of
the above restriction)
* If WHERE part contains complex nested AND and OR conditions, some ways
to retrieve rows using index_merge will not be considered. The choice
of read plan may depend on the order of conjuncts/disjuncts in WHERE
part of the query, see comments near imerge_list_or_list and
SEL_IMERGE::or_sel_tree_with_checks functions for details.
* There is no "index_merge_ref" method (but index_merge on non-first
table in join is possible with 'range checked for each record').
See comments around SEL_IMERGE class and test_quick_select for more
details.
ROW RETRIEVAL ALGORITHM
index_merge uses Unique class for duplicates removal. index_merge takes
advantage of Clustered Primary Key (CPK) if the table has one.
The index_merge algorithm consists of two phases:
Phase 1 (implemented in QuickIndexMergeSelect::prepare_unique):
prepare()
{
activate 'index only';
while(retrieve next row for non-CPK scan)
{
if (there is a CPK scan and row will be retrieved by it)
skip this row;
else
put its rowid into Unique;
}
deactivate 'index only';
}
Phase 2 (implemented as sequence of QuickIndexMergeSelect::get_next
calls):
fetch()
{
retrieve all rows from row pointers stored in Unique;
free Unique;
retrieve all rows for CPK scan;
}
*/
class QuickIndexMergeSelect : public QuickSelectInterface
{
public:
QuickIndexMergeSelect(Session *session, Table *table);
~QuickIndexMergeSelect();
int init();
int reset(void);
/**
* Get next row for index_merge.
* NOTES
* The rows are read from
* 1. rowids stored in Unique.
* 2. QuickRangeSelect with clustered primary key (if any).
* The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
*/
int get_next();
bool reverse_sorted() const
{
return false;
}
bool unique_key_range() const
{
return false;
}
int get_type() const
{
return QS_TYPE_INDEX_MERGE;
}
void add_keys_and_lengths(std::string *key_names, std::string *used_lengths);
void add_info_string(std::string *str);
bool is_keys_used(const boost::dynamic_bitset<>& fields);
void push_quick_back(QuickRangeSelect *quick_sel_range);
/* range quick selects this index_merge read consists of */
std::vector<QuickRangeSelect *> quick_selects;
/* quick select that uses clustered primary key (NULL if none) */
QuickRangeSelect *pk_quick_select;
/* true if this select is currently doing a clustered PK scan */
bool doing_pk_scan;
memory::Root alloc;
Session *session;
/**
* Perform key scans for all used indexes (except CPK), get rowids and merge
* them into an ordered non-recurrent sequence of rowids.
*
* The merge/duplicate removal is performed using Unique class. We put all
* rowids into Unique, get the sorted sequence and destroy the Unique.
*
* If table has a clustered primary key that covers all rows (true for bdb
* and innodb currently) and one of the index_merge scans is a scan on PK,
* then rows that will be retrieved by PK scan are not put into Unique and
* primary key scan is not performed here, it is performed later separately.
*
* RETURN
* @retval 0 OK
* @retval other error
*/
int read_keys_and_merge();
/* used to get rows collected in Unique */
ReadRecord read_record;
};
} /* namespace optimizer */
} /* namespace drizzled */
|