← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/quick_index_merge_select.h

Split some classes from the range optimizer out in to their own header and implementation files.
Corrected the case on these classes also to adhere to the coding standards. Cleaned up any style
issues in any code I came across while moving code.

Show diffs side-by-side

added added

removed removed

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