← 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

Big merge.

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_QUICK_INDEX_MERGE_SELECT_H
 
21
#define DRIZZLED_OPTIMIZER_QUICK_INDEX_MERGE_SELECT_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_QUICK_INDEX_MERGE_SELECT_H */