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.mvstore.db; |
7 | |
8 | import java.util.Iterator; |
9 | import java.util.List; |
10 | |
11 | import org.h2.api.ErrorCode; |
12 | import org.h2.engine.Database; |
13 | import org.h2.engine.Session; |
14 | import org.h2.index.BaseIndex; |
15 | import org.h2.index.Cursor; |
16 | import org.h2.index.IndexType; |
17 | import org.h2.index.SpatialIndex; |
18 | import org.h2.index.SpatialTreeIndex; |
19 | import org.h2.message.DbException; |
20 | import org.h2.mvstore.db.TransactionStore.Transaction; |
21 | import org.h2.mvstore.db.TransactionStore.TransactionMap; |
22 | import org.h2.mvstore.db.TransactionStore.VersionedValue; |
23 | import org.h2.mvstore.db.TransactionStore.VersionedValueType; |
24 | import org.h2.mvstore.rtree.MVRTreeMap; |
25 | import org.h2.mvstore.rtree.MVRTreeMap.RTreeCursor; |
26 | import org.h2.mvstore.rtree.SpatialKey; |
27 | import org.h2.result.Row; |
28 | import org.h2.result.SearchRow; |
29 | import org.h2.result.SortOrder; |
30 | import org.h2.table.IndexColumn; |
31 | import org.h2.table.TableFilter; |
32 | import org.h2.value.Value; |
33 | import org.h2.value.ValueGeometry; |
34 | import org.h2.value.ValueLong; |
35 | |
36 | import com.vividsolutions.jts.geom.Envelope; |
37 | import com.vividsolutions.jts.geom.Geometry; |
38 | |
39 | /** |
40 | * This is an index based on a MVRTreeMap. |
41 | * |
42 | * @author Thomas Mueller |
43 | * @author Noel Grandin |
44 | * @author Nicolas Fortin, Atelier SIG, IRSTV FR CNRS 24888 |
45 | */ |
46 | public class MVSpatialIndex extends BaseIndex implements SpatialIndex, MVIndex { |
47 | |
48 | /** |
49 | * The multi-value table. |
50 | */ |
51 | final MVTable mvTable; |
52 | |
53 | private final String mapName; |
54 | private TransactionMap<SpatialKey, Value> dataMap; |
55 | private MVRTreeMap<VersionedValue> spatialMap; |
56 | |
57 | /** |
58 | * Constructor. |
59 | * |
60 | * @param db the database |
61 | * @param table the table instance |
62 | * @param id the index id |
63 | * @param indexName the index name |
64 | * @param columns the indexed columns (only one geometry column allowed) |
65 | * @param indexType the index type (only spatial index) |
66 | */ |
67 | public MVSpatialIndex( |
68 | Database db, MVTable table, int id, String indexName, |
69 | IndexColumn[] columns, IndexType indexType) { |
70 | if (columns.length != 1) { |
71 | throw DbException.getUnsupportedException( |
72 | "Can only index one column"); |
73 | } |
74 | IndexColumn col = columns[0]; |
75 | if ((col.sortType & SortOrder.DESCENDING) != 0) { |
76 | throw DbException.getUnsupportedException( |
77 | "Cannot index in descending order"); |
78 | } |
79 | if ((col.sortType & SortOrder.NULLS_FIRST) != 0) { |
80 | throw DbException.getUnsupportedException( |
81 | "Nulls first is not supported"); |
82 | } |
83 | if ((col.sortType & SortOrder.NULLS_LAST) != 0) { |
84 | throw DbException.getUnsupportedException( |
85 | "Nulls last is not supported"); |
86 | } |
87 | if (col.column.getType() != Value.GEOMETRY) { |
88 | throw DbException.getUnsupportedException( |
89 | "Spatial index on non-geometry column, " |
90 | + col.column.getCreateSQL()); |
91 | } |
92 | this.mvTable = table; |
93 | initBaseIndex(table, id, indexName, columns, indexType); |
94 | if (!database.isStarting()) { |
95 | checkIndexColumnTypes(columns); |
96 | } |
97 | mapName = "index." + getId(); |
98 | ValueDataType vt = new ValueDataType(null, null, null); |
99 | VersionedValueType valueType = new VersionedValueType(vt); |
100 | MVRTreeMap.Builder<VersionedValue> mapBuilder = |
101 | new MVRTreeMap.Builder<VersionedValue>(). |
102 | valueType(valueType); |
103 | spatialMap = db.getMvStore().getStore().openMap(mapName, mapBuilder); |
104 | dataMap = mvTable.getTransaction(null).openMap(spatialMap); |
105 | } |
106 | |
107 | @Override |
108 | public void addRowsToBuffer(List<Row> rows, String bufferName) { |
109 | throw DbException.throwInternalError(); |
110 | } |
111 | |
112 | @Override |
113 | public void addBufferedRows(List<String> bufferNames) { |
114 | throw DbException.throwInternalError(); |
115 | } |
116 | |
117 | @Override |
118 | public void close(Session session) { |
119 | // ok |
120 | } |
121 | |
122 | @Override |
123 | public void add(Session session, Row row) { |
124 | TransactionMap<SpatialKey, Value> map = getMap(session); |
125 | SpatialKey key = getKey(row); |
126 | if (indexType.isUnique()) { |
127 | // this will detect committed entries only |
128 | RTreeCursor cursor = spatialMap.findContainedKeys(key); |
129 | Iterator<SpatialKey> it = map.wrapIterator(cursor, false); |
130 | while (it.hasNext()) { |
131 | SpatialKey k = it.next(); |
132 | if (k.equalsIgnoringId(key)) { |
133 | throw getDuplicateKeyException(key.toString()); |
134 | } |
135 | } |
136 | } |
137 | try { |
138 | map.put(key, ValueLong.get(0)); |
139 | } catch (IllegalStateException e) { |
140 | throw DbException.get(ErrorCode.CONCURRENT_UPDATE_1, |
141 | e, table.getName()); |
142 | } |
143 | if (indexType.isUnique()) { |
144 | // check if there is another (uncommitted) entry |
145 | RTreeCursor cursor = spatialMap.findContainedKeys(key); |
146 | Iterator<SpatialKey> it = map.wrapIterator(cursor, true); |
147 | while (it.hasNext()) { |
148 | SpatialKey k = it.next(); |
149 | if (k.equalsIgnoringId(key)) { |
150 | if (map.isSameTransaction(k)) { |
151 | continue; |
152 | } |
153 | map.remove(key); |
154 | if (map.get(k) != null) { |
155 | // committed |
156 | throw getDuplicateKeyException(k.toString()); |
157 | } |
158 | throw DbException.get(ErrorCode.CONCURRENT_UPDATE_1, table.getName()); |
159 | } |
160 | } |
161 | } |
162 | } |
163 | |
164 | private SpatialKey getKey(SearchRow r) { |
165 | if (r == null) { |
166 | return null; |
167 | } |
168 | Value v = r.getValue(columnIds[0]); |
169 | Geometry g = ((ValueGeometry) v.convertTo(Value.GEOMETRY)).getGeometryNoCopy(); |
170 | Envelope env = g.getEnvelopeInternal(); |
171 | return new SpatialKey(r.getKey(), |
172 | (float) env.getMinX(), (float) env.getMaxX(), |
173 | (float) env.getMinY(), (float) env.getMaxY()); |
174 | } |
175 | |
176 | @Override |
177 | public void remove(Session session, Row row) { |
178 | SpatialKey key = getKey(row); |
179 | TransactionMap<SpatialKey, Value> map = getMap(session); |
180 | try { |
181 | Value old = map.remove(key); |
182 | if (old == null) { |
183 | throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1, |
184 | getSQL() + ": " + row.getKey()); |
185 | } |
186 | } catch (IllegalStateException e) { |
187 | throw DbException.get(ErrorCode.CONCURRENT_UPDATE_1, |
188 | e, table.getName()); |
189 | } |
190 | } |
191 | |
192 | @Override |
193 | public Cursor find(TableFilter filter, SearchRow first, SearchRow last) { |
194 | return find(filter.getSession()); |
195 | } |
196 | |
197 | @Override |
198 | public Cursor find(Session session, SearchRow first, SearchRow last) { |
199 | return find(session); |
200 | } |
201 | |
202 | private Cursor find(Session session) { |
203 | Iterator<SpatialKey> cursor = spatialMap.keyIterator(null); |
204 | TransactionMap<SpatialKey, Value> map = getMap(session); |
205 | Iterator<SpatialKey> it = map.wrapIterator(cursor, false); |
206 | return new MVStoreCursor(session, it); |
207 | } |
208 | |
209 | @Override |
210 | public Cursor findByGeometry(TableFilter filter, SearchRow intersection) { |
211 | Session session = filter.getSession(); |
212 | if (intersection == null) { |
213 | return find(session); |
214 | } |
215 | Iterator<SpatialKey> cursor = |
216 | spatialMap.findIntersectingKeys(getEnvelope(intersection)); |
217 | TransactionMap<SpatialKey, Value> map = getMap(session); |
218 | Iterator<SpatialKey> it = map.wrapIterator(cursor, false); |
219 | return new MVStoreCursor(session, it); |
220 | } |
221 | |
222 | private SpatialKey getEnvelope(SearchRow row) { |
223 | Value v = row.getValue(columnIds[0]); |
224 | Geometry g = ((ValueGeometry) v.convertTo(Value.GEOMETRY)).getGeometryNoCopy(); |
225 | Envelope env = g.getEnvelopeInternal(); |
226 | return new SpatialKey(row.getKey(), |
227 | (float) env.getMinX(), (float) env.getMaxX(), |
228 | (float) env.getMinY(), (float) env.getMaxY()); |
229 | } |
230 | |
231 | |
232 | /** |
233 | * Get the row with the given index key. |
234 | * |
235 | * @param key the index key |
236 | * @return the row |
237 | */ |
238 | SearchRow getRow(SpatialKey key) { |
239 | SearchRow searchRow = mvTable.getTemplateRow(); |
240 | searchRow.setKey(key.getId()); |
241 | return searchRow; |
242 | } |
243 | |
244 | @Override |
245 | public MVTable getTable() { |
246 | return mvTable; |
247 | } |
248 | |
249 | @Override |
250 | public double getCost(Session session, int[] masks, TableFilter filter, |
251 | SortOrder sortOrder) { |
252 | return getCostRangeIndex(masks, table.getRowCountApproximation(), |
253 | filter, sortOrder); |
254 | } |
255 | |
256 | @Override |
257 | protected long getCostRangeIndex(int[] masks, long rowCount, |
258 | TableFilter filter, SortOrder sortOrder) { |
259 | return SpatialTreeIndex.getCostRangeIndex(masks, rowCount, columns); |
260 | } |
261 | |
262 | @Override |
263 | public void remove(Session session) { |
264 | TransactionMap<SpatialKey, Value> map = getMap(session); |
265 | if (!map.isClosed()) { |
266 | Transaction t = mvTable.getTransaction(session); |
267 | t.removeMap(map); |
268 | } |
269 | } |
270 | |
271 | @Override |
272 | public void truncate(Session session) { |
273 | TransactionMap<SpatialKey, Value> map = getMap(session); |
274 | map.clear(); |
275 | } |
276 | |
277 | @Override |
278 | public boolean canGetFirstOrLast() { |
279 | return true; |
280 | } |
281 | |
282 | @Override |
283 | public Cursor findFirstOrLast(Session session, boolean first) { |
284 | if (!first) { |
285 | throw DbException.throwInternalError( |
286 | "Spatial Index can only be fetch in ascending order"); |
287 | } |
288 | return find(session); |
289 | } |
290 | |
291 | @Override |
292 | public boolean needRebuild() { |
293 | try { |
294 | return dataMap.sizeAsLongMax() == 0; |
295 | } catch (IllegalStateException e) { |
296 | throw DbException.get(ErrorCode.OBJECT_CLOSED, e); |
297 | } |
298 | } |
299 | |
300 | @Override |
301 | public long getRowCount(Session session) { |
302 | TransactionMap<SpatialKey, Value> map = getMap(session); |
303 | return map.sizeAsLong(); |
304 | } |
305 | |
306 | @Override |
307 | public long getRowCountApproximation() { |
308 | try { |
309 | return dataMap.sizeAsLongMax(); |
310 | } catch (IllegalStateException e) { |
311 | throw DbException.get(ErrorCode.OBJECT_CLOSED, e); |
312 | } |
313 | } |
314 | |
315 | @Override |
316 | public long getDiskSpaceUsed() { |
317 | // TODO estimate disk space usage |
318 | return 0; |
319 | } |
320 | |
321 | @Override |
322 | public void checkRename() { |
323 | // ok |
324 | } |
325 | |
326 | /** |
327 | * Get the map to store the data. |
328 | * |
329 | * @param session the session |
330 | * @return the map |
331 | */ |
332 | TransactionMap<SpatialKey, Value> getMap(Session session) { |
333 | if (session == null) { |
334 | return dataMap; |
335 | } |
336 | Transaction t = mvTable.getTransaction(session); |
337 | return dataMap.getInstance(t, Long.MAX_VALUE); |
338 | } |
339 | |
340 | /** |
341 | * A cursor. |
342 | */ |
343 | class MVStoreCursor implements Cursor { |
344 | |
345 | private final Session session; |
346 | private final Iterator<SpatialKey> it; |
347 | private SpatialKey current; |
348 | private SearchRow searchRow; |
349 | private Row row; |
350 | |
351 | public MVStoreCursor(Session session, Iterator<SpatialKey> it) { |
352 | this.session = session; |
353 | this.it = it; |
354 | } |
355 | |
356 | @Override |
357 | public Row get() { |
358 | if (row == null) { |
359 | SearchRow r = getSearchRow(); |
360 | if (r != null) { |
361 | row = mvTable.getRow(session, r.getKey()); |
362 | } |
363 | } |
364 | return row; |
365 | } |
366 | |
367 | @Override |
368 | public SearchRow getSearchRow() { |
369 | if (searchRow == null) { |
370 | if (current != null) { |
371 | searchRow = getRow(current); |
372 | } |
373 | } |
374 | return searchRow; |
375 | } |
376 | |
377 | @Override |
378 | public boolean next() { |
379 | current = it.next(); |
380 | searchRow = null; |
381 | row = null; |
382 | return current != null; |
383 | } |
384 | |
385 | @Override |
386 | public boolean previous() { |
387 | throw DbException.getUnsupportedException("previous"); |
388 | } |
389 | |
390 | } |
391 | |
392 | } |
393 | |