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 | |
10 | import org.h2.api.ErrorCode; |
11 | import org.h2.engine.Database; |
12 | import org.h2.engine.DbObject; |
13 | import org.h2.engine.Session; |
14 | import org.h2.message.DbException; |
15 | import org.h2.result.Row; |
16 | import org.h2.result.SearchRow; |
17 | import org.h2.result.SortOrder; |
18 | import org.h2.schema.Schema; |
19 | import org.h2.table.Column; |
20 | import org.h2.table.IndexColumn; |
21 | import org.h2.table.RegularTable; |
22 | import org.h2.table.Table; |
23 | import org.h2.table.TableFilter; |
24 | import org.h2.value.Value; |
25 | import org.h2.value.ValueNull; |
26 | |
27 | /** |
28 | * A multi-version index is a combination of a regular index, |
29 | * and a in-memory tree index that contains uncommitted changes. |
30 | * Uncommitted changes can include new rows, and deleted rows. |
31 | */ |
32 | public class MultiVersionIndex implements Index { |
33 | |
34 | private final Index base; |
35 | private final TreeIndex delta; |
36 | private final RegularTable table; |
37 | private final Object sync; |
38 | private final Column firstColumn; |
39 | |
40 | public MultiVersionIndex(Index base, RegularTable table) { |
41 | this.base = base; |
42 | this.table = table; |
43 | IndexType deltaIndexType = IndexType.createNonUnique(false); |
44 | if (base instanceof SpatialIndex) { |
45 | throw DbException.get(ErrorCode.FEATURE_NOT_SUPPORTED_1, |
46 | "MVCC & spatial index"); |
47 | } |
48 | this.delta = new TreeIndex(table, -1, "DELTA", base.getIndexColumns(), |
49 | deltaIndexType); |
50 | delta.setMultiVersion(true); |
51 | this.sync = base.getDatabase(); |
52 | this.firstColumn = base.getColumns()[0]; |
53 | } |
54 | |
55 | @Override |
56 | public void add(Session session, Row row) { |
57 | synchronized (sync) { |
58 | base.add(session, row); |
59 | if (removeIfExists(session, row)) { |
60 | // for example rolling back an delete operation |
61 | } else if (row.getSessionId() != 0) { |
62 | // don't insert rows that are added when creating an index |
63 | delta.add(session, row); |
64 | } |
65 | } |
66 | } |
67 | |
68 | @Override |
69 | public void close(Session session) { |
70 | synchronized (sync) { |
71 | base.close(session); |
72 | } |
73 | } |
74 | |
75 | @Override |
76 | public Cursor find(TableFilter filter, SearchRow first, SearchRow last) { |
77 | synchronized (sync) { |
78 | Cursor baseCursor = base.find(filter, first, last); |
79 | Cursor deltaCursor = delta.find(filter, first, last); |
80 | return new MultiVersionCursor(filter.getSession(), this, |
81 | baseCursor, deltaCursor, sync); |
82 | } |
83 | } |
84 | |
85 | @Override |
86 | public Cursor find(Session session, SearchRow first, SearchRow last) { |
87 | synchronized (sync) { |
88 | Cursor baseCursor = base.find(session, first, last); |
89 | Cursor deltaCursor = delta.find(session, first, last); |
90 | return new MultiVersionCursor(session, this, baseCursor, deltaCursor, sync); |
91 | } |
92 | } |
93 | |
94 | @Override |
95 | public Cursor findNext(Session session, SearchRow first, SearchRow last) { |
96 | throw DbException.throwInternalError(); |
97 | } |
98 | |
99 | @Override |
100 | public boolean canFindNext() { |
101 | // TODO possible, but more complicated |
102 | return false; |
103 | } |
104 | |
105 | @Override |
106 | public boolean canGetFirstOrLast() { |
107 | return base.canGetFirstOrLast() && delta.canGetFirstOrLast(); |
108 | } |
109 | |
110 | @Override |
111 | public Cursor findFirstOrLast(Session session, boolean first) { |
112 | if (first) { |
113 | // TODO optimization: this loops through NULL elements |
114 | Cursor cursor = find(session, null, null); |
115 | while (cursor.next()) { |
116 | SearchRow row = cursor.getSearchRow(); |
117 | Value v = row.getValue(firstColumn.getColumnId()); |
118 | if (v != ValueNull.INSTANCE) { |
119 | return cursor; |
120 | } |
121 | } |
122 | return cursor; |
123 | } |
124 | Cursor baseCursor = base.findFirstOrLast(session, false); |
125 | Cursor deltaCursor = delta.findFirstOrLast(session, false); |
126 | MultiVersionCursor cursor = new MultiVersionCursor(session, this, |
127 | baseCursor, deltaCursor, sync); |
128 | cursor.loadCurrent(); |
129 | // TODO optimization: this loops through NULL elements |
130 | while (cursor.previous()) { |
131 | SearchRow row = cursor.getSearchRow(); |
132 | if (row == null) { |
133 | break; |
134 | } |
135 | Value v = row.getValue(firstColumn.getColumnId()); |
136 | if (v != ValueNull.INSTANCE) { |
137 | return cursor; |
138 | } |
139 | } |
140 | return cursor; |
141 | } |
142 | |
143 | @Override |
144 | public double getCost(Session session, int[] masks, TableFilter filter, |
145 | SortOrder sortOrder) { |
146 | return base.getCost(session, masks, filter, sortOrder); |
147 | } |
148 | |
149 | @Override |
150 | public boolean needRebuild() { |
151 | return base.needRebuild(); |
152 | } |
153 | |
154 | /** |
155 | * Check if there is an uncommitted row with the given key |
156 | * within a different session. |
157 | * |
158 | * @param session the original session |
159 | * @param row the row (only the key is checked) |
160 | * @return true if there is an uncommitted row |
161 | */ |
162 | public boolean isUncommittedFromOtherSession(Session session, Row row) { |
163 | Cursor c = delta.find(session, row, row); |
164 | while (c.next()) { |
165 | Row r = c.get(); |
166 | return r.getSessionId() != session.getId(); |
167 | } |
168 | return false; |
169 | } |
170 | |
171 | private boolean removeIfExists(Session session, Row row) { |
172 | // maybe it was inserted by the same session just before |
173 | Cursor c = delta.find(session, row, row); |
174 | while (c.next()) { |
175 | Row r = c.get(); |
176 | if (r.getKey() == row.getKey() && r.getVersion() == row.getVersion()) { |
177 | if (r != row && table.getScanIndex(session).compareRows(r, row) != 0) { |
178 | row.setVersion(r.getVersion() + 1); |
179 | } else { |
180 | delta.remove(session, r); |
181 | return true; |
182 | } |
183 | } |
184 | } |
185 | return false; |
186 | } |
187 | |
188 | @Override |
189 | public void remove(Session session, Row row) { |
190 | synchronized (sync) { |
191 | base.remove(session, row); |
192 | if (removeIfExists(session, row)) { |
193 | // added and deleted in the same transaction: no change |
194 | } else { |
195 | delta.add(session, row); |
196 | } |
197 | } |
198 | } |
199 | |
200 | @Override |
201 | public void remove(Session session) { |
202 | synchronized (sync) { |
203 | base.remove(session); |
204 | } |
205 | } |
206 | |
207 | @Override |
208 | public void truncate(Session session) { |
209 | synchronized (sync) { |
210 | delta.truncate(session); |
211 | base.truncate(session); |
212 | } |
213 | } |
214 | |
215 | @Override |
216 | public void commit(int operation, Row row) { |
217 | synchronized (sync) { |
218 | removeIfExists(null, row); |
219 | } |
220 | } |
221 | |
222 | @Override |
223 | public int compareRows(SearchRow rowData, SearchRow compare) { |
224 | return base.compareRows(rowData, compare); |
225 | } |
226 | |
227 | @Override |
228 | public int getColumnIndex(Column col) { |
229 | return base.getColumnIndex(col); |
230 | } |
231 | |
232 | @Override |
233 | public Column[] getColumns() { |
234 | return base.getColumns(); |
235 | } |
236 | |
237 | @Override |
238 | public IndexColumn[] getIndexColumns() { |
239 | return base.getIndexColumns(); |
240 | } |
241 | |
242 | @Override |
243 | public String getCreateSQL() { |
244 | return base.getCreateSQL(); |
245 | } |
246 | |
247 | @Override |
248 | public String getCreateSQLForCopy(Table forTable, String quotedName) { |
249 | return base.getCreateSQLForCopy(forTable, quotedName); |
250 | } |
251 | |
252 | @Override |
253 | public String getDropSQL() { |
254 | return base.getDropSQL(); |
255 | } |
256 | |
257 | @Override |
258 | public IndexType getIndexType() { |
259 | return base.getIndexType(); |
260 | } |
261 | |
262 | @Override |
263 | public String getPlanSQL() { |
264 | return base.getPlanSQL(); |
265 | } |
266 | |
267 | @Override |
268 | public long getRowCount(Session session) { |
269 | return base.getRowCount(session); |
270 | } |
271 | |
272 | @Override |
273 | public Table getTable() { |
274 | return base.getTable(); |
275 | } |
276 | |
277 | @Override |
278 | public int getType() { |
279 | return base.getType(); |
280 | } |
281 | |
282 | @Override |
283 | public void removeChildrenAndResources(Session session) { |
284 | synchronized (sync) { |
285 | table.removeIndex(this); |
286 | remove(session); |
287 | } |
288 | } |
289 | |
290 | @Override |
291 | public String getSQL() { |
292 | return base.getSQL(); |
293 | } |
294 | |
295 | @Override |
296 | public Schema getSchema() { |
297 | return base.getSchema(); |
298 | } |
299 | |
300 | @Override |
301 | public void checkRename() { |
302 | base.checkRename(); |
303 | } |
304 | |
305 | @Override |
306 | public ArrayList<DbObject> getChildren() { |
307 | return base.getChildren(); |
308 | } |
309 | |
310 | @Override |
311 | public String getComment() { |
312 | return base.getComment(); |
313 | } |
314 | |
315 | @Override |
316 | public Database getDatabase() { |
317 | return base.getDatabase(); |
318 | } |
319 | |
320 | @Override |
321 | public int getId() { |
322 | return base.getId(); |
323 | } |
324 | |
325 | @Override |
326 | public String getName() { |
327 | return base.getName(); |
328 | } |
329 | |
330 | @Override |
331 | public boolean isTemporary() { |
332 | return base.isTemporary(); |
333 | } |
334 | |
335 | @Override |
336 | public void rename(String newName) { |
337 | base.rename(newName); |
338 | } |
339 | |
340 | @Override |
341 | public void setComment(String comment) { |
342 | base.setComment(comment); |
343 | } |
344 | |
345 | @Override |
346 | public void setTemporary(boolean temporary) { |
347 | base.setTemporary(temporary); |
348 | } |
349 | |
350 | @Override |
351 | public long getRowCountApproximation() { |
352 | return base.getRowCountApproximation(); |
353 | } |
354 | |
355 | @Override |
356 | public long getDiskSpaceUsed() { |
357 | return base.getDiskSpaceUsed(); |
358 | } |
359 | |
360 | public Index getBaseIndex() { |
361 | return base; |
362 | } |
363 | |
364 | @Override |
365 | public Row getRow(Session session, long key) { |
366 | return base.getRow(session, key); |
367 | } |
368 | |
369 | @Override |
370 | public boolean isHidden() { |
371 | return base.isHidden(); |
372 | } |
373 | |
374 | @Override |
375 | public boolean isRowIdIndex() { |
376 | return base.isRowIdIndex() && delta.isRowIdIndex(); |
377 | } |
378 | |
379 | @Override |
380 | public boolean canScan() { |
381 | return base.canScan(); |
382 | } |
383 | |
384 | @Override |
385 | public void setSortedInsertMode(boolean sortedInsertMode) { |
386 | base.setSortedInsertMode(sortedInsertMode); |
387 | delta.setSortedInsertMode(sortedInsertMode); |
388 | } |
389 | |
390 | } |