1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.index; |
7 | |
8 | import java.util.ArrayList; |
9 | import java.util.HashSet; |
10 | import org.h2.engine.Session; |
11 | import org.h2.expression.Comparison; |
12 | import org.h2.message.DbException; |
13 | import org.h2.result.ResultInterface; |
14 | import org.h2.result.Row; |
15 | import org.h2.result.SearchRow; |
16 | import org.h2.result.SortOrder; |
17 | import org.h2.table.Column; |
18 | import org.h2.table.IndexColumn; |
19 | import org.h2.table.Table; |
20 | import org.h2.table.TableFilter; |
21 | import org.h2.value.Value; |
22 | import org.h2.value.ValueGeometry; |
23 | import org.h2.value.ValueNull; |
24 | |
25 | /** |
26 | * The filter used to walk through an index. This class supports IN(..) |
27 | * and IN(SELECT ...) optimizations. |
28 | * |
29 | * @author Thomas Mueller |
30 | * @author Noel Grandin |
31 | * @author Nicolas Fortin, Atelier SIG, IRSTV FR CNRS 24888 |
32 | */ |
33 | public class IndexCursor implements Cursor { |
34 | |
35 | private Session session; |
36 | private final TableFilter tableFilter; |
37 | private Index index; |
38 | private Table table; |
39 | private IndexColumn[] indexColumns; |
40 | private boolean alwaysFalse; |
41 | |
42 | private SearchRow start, end, intersects; |
43 | private Cursor cursor; |
44 | private Column inColumn; |
45 | private int inListIndex; |
46 | private Value[] inList; |
47 | private ResultInterface inResult; |
48 | private HashSet<Value> inResultTested; |
49 | |
50 | public IndexCursor(TableFilter filter) { |
51 | this.tableFilter = filter; |
52 | } |
53 | |
54 | public void setIndex(Index index) { |
55 | this.index = index; |
56 | this.table = index.getTable(); |
57 | Column[] columns = table.getColumns(); |
58 | indexColumns = new IndexColumn[columns.length]; |
59 | IndexColumn[] idxCols = index.getIndexColumns(); |
60 | if (idxCols != null) { |
61 | for (int i = 0, len = columns.length; i < len; i++) { |
62 | int idx = index.getColumnIndex(columns[i]); |
63 | if (idx >= 0) { |
64 | indexColumns[i] = idxCols[idx]; |
65 | } |
66 | } |
67 | } |
68 | } |
69 | |
70 | /** |
71 | * Re-evaluate the start and end values of the index search for rows. |
72 | * |
73 | * @param s the session |
74 | * @param indexConditions the index conditions |
75 | */ |
76 | public void find(Session s, ArrayList<IndexCondition> indexConditions) { |
77 | this.session = s; |
78 | alwaysFalse = false; |
79 | start = end = null; |
80 | inList = null; |
81 | inColumn = null; |
82 | inResult = null; |
83 | inResultTested = null; |
84 | intersects = null; |
85 | // don't use enhanced for loop to avoid creating objects |
86 | for (int i = 0, size = indexConditions.size(); i < size; i++) { |
87 | IndexCondition condition = indexConditions.get(i); |
88 | if (condition.isAlwaysFalse()) { |
89 | alwaysFalse = true; |
90 | break; |
91 | } |
92 | Column column = condition.getColumn(); |
93 | if (condition.getCompareType() == Comparison.IN_LIST) { |
94 | if (start == null && end == null) { |
95 | if (canUseIndexForIn(column)) { |
96 | this.inColumn = column; |
97 | inList = condition.getCurrentValueList(s); |
98 | inListIndex = 0; |
99 | } |
100 | } |
101 | } else if (condition.getCompareType() == Comparison.IN_QUERY) { |
102 | if (start == null && end == null) { |
103 | if (canUseIndexForIn(column)) { |
104 | this.inColumn = column; |
105 | inResult = condition.getCurrentResult(); |
106 | } |
107 | } |
108 | } else { |
109 | Value v = condition.getCurrentValue(s); |
110 | boolean isStart = condition.isStart(); |
111 | boolean isEnd = condition.isEnd(); |
112 | boolean isIntersects = condition.isSpatialIntersects(); |
113 | int columnId = column.getColumnId(); |
114 | if (columnId >= 0) { |
115 | IndexColumn idxCol = indexColumns[columnId]; |
116 | if (idxCol != null && (idxCol.sortType & SortOrder.DESCENDING) != 0) { |
117 | // if the index column is sorted the other way, we swap |
118 | // end and start NULLS_FIRST / NULLS_LAST is not a |
119 | // problem, as nulls never match anyway |
120 | boolean temp = isStart; |
121 | isStart = isEnd; |
122 | isEnd = temp; |
123 | } |
124 | } |
125 | if (isStart) { |
126 | start = getSearchRow(start, columnId, v, true); |
127 | } |
128 | if (isEnd) { |
129 | end = getSearchRow(end, columnId, v, false); |
130 | } |
131 | if (isIntersects) { |
132 | intersects = getSpatialSearchRow(intersects, columnId, v); |
133 | } |
134 | if (isStart || isEnd) { |
135 | // an X=? condition will produce less rows than |
136 | // an X IN(..) condition |
137 | inColumn = null; |
138 | inList = null; |
139 | inResult = null; |
140 | } |
141 | if (!session.getDatabase().getSettings().optimizeIsNull) { |
142 | if (isStart && isEnd) { |
143 | if (v == ValueNull.INSTANCE) { |
144 | // join on a column=NULL is always false |
145 | alwaysFalse = true; |
146 | } |
147 | } |
148 | } |
149 | } |
150 | } |
151 | if (inColumn != null) { |
152 | return; |
153 | } |
154 | if (!alwaysFalse) { |
155 | if (intersects != null && index instanceof SpatialIndex) { |
156 | cursor = ((SpatialIndex) index).findByGeometry(tableFilter, |
157 | intersects); |
158 | } else { |
159 | cursor = index.find(tableFilter, start, end); |
160 | } |
161 | } |
162 | } |
163 | |
164 | private boolean canUseIndexForIn(Column column) { |
165 | if (inColumn != null) { |
166 | // only one IN(..) condition can be used at the same time |
167 | return false; |
168 | } |
169 | // The first column of the index must match this column, |
170 | // or it must be a VIEW index (where the column is null). |
171 | // Multiple IN conditions with views are not supported, see |
172 | // IndexCondition.getMask. |
173 | IndexColumn[] cols = index.getIndexColumns(); |
174 | if (cols == null) { |
175 | return true; |
176 | } |
177 | IndexColumn idxCol = cols[0]; |
178 | return idxCol == null || idxCol.column == column; |
179 | } |
180 | |
181 | private SearchRow getSpatialSearchRow(SearchRow row, int columnId, Value v) { |
182 | if (row == null) { |
183 | row = table.getTemplateRow(); |
184 | } else if (row.getValue(columnId) != null) { |
185 | // if an object needs to overlap with both a and b, |
186 | // then it needs to overlap with the the union of a and b |
187 | // (not the intersection) |
188 | ValueGeometry vg = (ValueGeometry) row.getValue(columnId). |
189 | convertTo(Value.GEOMETRY); |
190 | v = ((ValueGeometry) v.convertTo(Value.GEOMETRY)). |
191 | getEnvelopeUnion(vg); |
192 | } |
193 | if (columnId < 0) { |
194 | row.setKey(v.getLong()); |
195 | } else { |
196 | row.setValue(columnId, v); |
197 | } |
198 | return row; |
199 | } |
200 | |
201 | private SearchRow getSearchRow(SearchRow row, int columnId, Value v, |
202 | boolean max) { |
203 | if (row == null) { |
204 | row = table.getTemplateRow(); |
205 | } else { |
206 | v = getMax(row.getValue(columnId), v, max); |
207 | } |
208 | if (columnId < 0) { |
209 | row.setKey(v.getLong()); |
210 | } else { |
211 | row.setValue(columnId, v); |
212 | } |
213 | return row; |
214 | } |
215 | |
216 | private Value getMax(Value a, Value b, boolean bigger) { |
217 | if (a == null) { |
218 | return b; |
219 | } else if (b == null) { |
220 | return a; |
221 | } |
222 | if (session.getDatabase().getSettings().optimizeIsNull) { |
223 | // IS NULL must be checked later |
224 | if (a == ValueNull.INSTANCE) { |
225 | return b; |
226 | } else if (b == ValueNull.INSTANCE) { |
227 | return a; |
228 | } |
229 | } |
230 | int comp = a.compareTo(b, table.getDatabase().getCompareMode()); |
231 | if (comp == 0) { |
232 | return a; |
233 | } |
234 | if (a == ValueNull.INSTANCE || b == ValueNull.INSTANCE) { |
235 | if (session.getDatabase().getSettings().optimizeIsNull) { |
236 | // column IS NULL AND column <op> <not null> is always false |
237 | return null; |
238 | } |
239 | } |
240 | if (!bigger) { |
241 | comp = -comp; |
242 | } |
243 | return comp > 0 ? a : b; |
244 | } |
245 | |
246 | /** |
247 | * Check if the result is empty for sure. |
248 | * |
249 | * @return true if it is |
250 | */ |
251 | public boolean isAlwaysFalse() { |
252 | return alwaysFalse; |
253 | } |
254 | |
255 | @Override |
256 | public Row get() { |
257 | if (cursor == null) { |
258 | return null; |
259 | } |
260 | return cursor.get(); |
261 | } |
262 | |
263 | @Override |
264 | public SearchRow getSearchRow() { |
265 | return cursor.getSearchRow(); |
266 | } |
267 | |
268 | @Override |
269 | public boolean next() { |
270 | while (true) { |
271 | if (cursor == null) { |
272 | nextCursor(); |
273 | if (cursor == null) { |
274 | return false; |
275 | } |
276 | } |
277 | if (cursor.next()) { |
278 | return true; |
279 | } |
280 | cursor = null; |
281 | } |
282 | } |
283 | |
284 | private void nextCursor() { |
285 | if (inList != null) { |
286 | while (inListIndex < inList.length) { |
287 | Value v = inList[inListIndex++]; |
288 | if (v != ValueNull.INSTANCE) { |
289 | find(v); |
290 | break; |
291 | } |
292 | } |
293 | } else if (inResult != null) { |
294 | while (inResult.next()) { |
295 | Value v = inResult.currentRow()[0]; |
296 | if (v != ValueNull.INSTANCE) { |
297 | v = inColumn.convert(v); |
298 | if (inResultTested == null) { |
299 | inResultTested = new HashSet<Value>(); |
300 | } |
301 | if (inResultTested.add(v)) { |
302 | find(v); |
303 | break; |
304 | } |
305 | } |
306 | } |
307 | } |
308 | } |
309 | |
310 | private void find(Value v) { |
311 | v = inColumn.convert(v); |
312 | int id = inColumn.getColumnId(); |
313 | if (start == null) { |
314 | start = table.getTemplateRow(); |
315 | } |
316 | start.setValue(id, v); |
317 | cursor = index.find(tableFilter, start, start); |
318 | } |
319 | |
320 | @Override |
321 | public boolean previous() { |
322 | throw DbException.throwInternalError(); |
323 | } |
324 | |
325 | } |