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.Iterator; |
9 | |
10 | import org.h2.engine.Constants; |
11 | import org.h2.engine.Session; |
12 | import org.h2.message.DbException; |
13 | import org.h2.mvstore.MVStore; |
14 | import org.h2.mvstore.db.MVTableEngine; |
15 | import org.h2.mvstore.rtree.MVRTreeMap; |
16 | import org.h2.mvstore.rtree.SpatialKey; |
17 | import org.h2.result.Row; |
18 | import org.h2.result.SearchRow; |
19 | import org.h2.result.SortOrder; |
20 | import org.h2.table.Column; |
21 | import org.h2.table.IndexColumn; |
22 | import org.h2.table.Table; |
23 | import org.h2.table.TableFilter; |
24 | import org.h2.value.Value; |
25 | import org.h2.value.ValueGeometry; |
26 | |
27 | import com.vividsolutions.jts.geom.Envelope; |
28 | import com.vividsolutions.jts.geom.Geometry; |
29 | |
30 | /** |
31 | * This is an index based on a MVR-TreeMap. |
32 | * |
33 | * @author Thomas Mueller |
34 | * @author Noel Grandin |
35 | * @author Nicolas Fortin, Atelier SIG, IRSTV FR CNRS 24888 |
36 | */ |
37 | public class SpatialTreeIndex extends BaseIndex implements SpatialIndex { |
38 | |
39 | private static final String MAP_PREFIX = "RTREE_"; |
40 | |
41 | private final MVRTreeMap<Long> treeMap; |
42 | private final MVStore store; |
43 | |
44 | private boolean closed; |
45 | private boolean needRebuild; |
46 | |
47 | /** |
48 | * Constructor. |
49 | * |
50 | * @param table the table instance |
51 | * @param id the index id |
52 | * @param indexName the index name |
53 | * @param columns the indexed columns (only one geometry column allowed) |
54 | * @param persistent whether the index should be persisted |
55 | * @param indexType the index type (only spatial index) |
56 | * @param create whether to create a new index |
57 | * @param session the session. |
58 | */ |
59 | public SpatialTreeIndex(Table table, int id, String indexName, |
60 | IndexColumn[] columns, IndexType indexType, boolean persistent, |
61 | boolean create, Session session) { |
62 | if (indexType.isUnique()) { |
63 | throw DbException.getUnsupportedException("not unique"); |
64 | } |
65 | if (!persistent && !create) { |
66 | throw DbException.getUnsupportedException( |
67 | "Non persistent index called with create==false"); |
68 | } |
69 | if (columns.length > 1) { |
70 | throw DbException.getUnsupportedException( |
71 | "can only do one column"); |
72 | } |
73 | if ((columns[0].sortType & SortOrder.DESCENDING) != 0) { |
74 | throw DbException.getUnsupportedException( |
75 | "cannot do descending"); |
76 | } |
77 | if ((columns[0].sortType & SortOrder.NULLS_FIRST) != 0) { |
78 | throw DbException.getUnsupportedException( |
79 | "cannot do nulls first"); |
80 | } |
81 | if ((columns[0].sortType & SortOrder.NULLS_LAST) != 0) { |
82 | throw DbException.getUnsupportedException( |
83 | "cannot do nulls last"); |
84 | } |
85 | initBaseIndex(table, id, indexName, columns, indexType); |
86 | this.needRebuild = create; |
87 | this.table = table; |
88 | if (!database.isStarting()) { |
89 | if (columns[0].column.getType() != Value.GEOMETRY) { |
90 | throw DbException.getUnsupportedException( |
91 | "spatial index on non-geometry column, " + |
92 | columns[0].column.getCreateSQL()); |
93 | } |
94 | } |
95 | if (!persistent) { |
96 | // Index in memory |
97 | store = MVStore.open(null); |
98 | treeMap = store.openMap("spatialIndex", |
99 | new MVRTreeMap.Builder<Long>()); |
100 | } else { |
101 | if (id < 0) { |
102 | throw DbException.getUnsupportedException( |
103 | "Persistent index with id<0"); |
104 | } |
105 | MVTableEngine.init(session.getDatabase()); |
106 | store = session.getDatabase().getMvStore().getStore(); |
107 | // Called after CREATE SPATIAL INDEX or |
108 | // by PageStore.addMeta |
109 | treeMap = store.openMap(MAP_PREFIX + getId(), |
110 | new MVRTreeMap.Builder<Long>()); |
111 | if (treeMap.isEmpty()) { |
112 | needRebuild = true; |
113 | } |
114 | } |
115 | } |
116 | |
117 | @Override |
118 | public void close(Session session) { |
119 | store.close(); |
120 | closed = true; |
121 | } |
122 | |
123 | @Override |
124 | public void add(Session session, Row row) { |
125 | if (closed) { |
126 | throw DbException.throwInternalError(); |
127 | } |
128 | treeMap.add(getEnvelope(row), row.getKey()); |
129 | } |
130 | |
131 | private SpatialKey getEnvelope(SearchRow row) { |
132 | Value v = row.getValue(columnIds[0]); |
133 | Geometry g = ((ValueGeometry) v.convertTo(Value.GEOMETRY)).getGeometryNoCopy(); |
134 | Envelope env = g.getEnvelopeInternal(); |
135 | return new SpatialKey(row.getKey(), |
136 | (float) env.getMinX(), (float) env.getMaxX(), |
137 | (float) env.getMinY(), (float) env.getMaxY()); |
138 | } |
139 | |
140 | @Override |
141 | public void remove(Session session, Row row) { |
142 | if (closed) { |
143 | throw DbException.throwInternalError(); |
144 | } |
145 | if (!treeMap.remove(getEnvelope(row), row.getKey())) { |
146 | throw DbException.throwInternalError("row not found"); |
147 | } |
148 | } |
149 | |
150 | @Override |
151 | public Cursor find(TableFilter filter, SearchRow first, SearchRow last) { |
152 | return find(filter.getSession()); |
153 | } |
154 | |
155 | @Override |
156 | public Cursor find(Session session, SearchRow first, SearchRow last) { |
157 | return find(session); |
158 | } |
159 | |
160 | private Cursor find(Session session) { |
161 | return new SpatialCursor(treeMap.keySet().iterator(), table, session); |
162 | } |
163 | |
164 | @Override |
165 | public Cursor findByGeometry(TableFilter filter, SearchRow intersection) { |
166 | if (intersection == null) { |
167 | return find(filter.getSession()); |
168 | } |
169 | return new SpatialCursor( |
170 | treeMap.findIntersectingKeys(getEnvelope(intersection)), table, |
171 | filter.getSession()); |
172 | } |
173 | |
174 | @Override |
175 | protected long getCostRangeIndex(int[] masks, long rowCount, |
176 | TableFilter filter, SortOrder sortOrder) { |
177 | return getCostRangeIndex(masks, rowCount, columns); |
178 | } |
179 | |
180 | /** |
181 | * Compute spatial index cost |
182 | * @param masks Search mask |
183 | * @param rowCount Table row count |
184 | * @param columns Table columns |
185 | * @return Index cost hint |
186 | */ |
187 | public static long getCostRangeIndex(int[] masks, long rowCount, Column[] columns) { |
188 | rowCount += Constants.COST_ROW_OFFSET; |
189 | long cost = rowCount; |
190 | if (masks == null) { |
191 | return cost; |
192 | } |
193 | for (Column column : columns) { |
194 | int index = column.getColumnId(); |
195 | int mask = masks[index]; |
196 | if ((mask & IndexCondition.SPATIAL_INTERSECTS) != 0) { |
197 | cost = 3 + rowCount / 4; |
198 | } |
199 | } |
200 | return 10 * cost; |
201 | } |
202 | |
203 | @Override |
204 | public double getCost(Session session, int[] masks, TableFilter filter, |
205 | SortOrder sortOrder) { |
206 | return getCostRangeIndex(masks, table.getRowCountApproximation(), |
207 | filter, sortOrder); |
208 | } |
209 | |
210 | @Override |
211 | public void remove(Session session) { |
212 | if (!treeMap.isClosed()) { |
213 | store.removeMap(treeMap); |
214 | } |
215 | } |
216 | |
217 | @Override |
218 | public void truncate(Session session) { |
219 | treeMap.clear(); |
220 | } |
221 | |
222 | @Override |
223 | public void checkRename() { |
224 | // nothing to do |
225 | } |
226 | |
227 | @Override |
228 | public boolean needRebuild() { |
229 | return needRebuild; |
230 | } |
231 | |
232 | @Override |
233 | public boolean canGetFirstOrLast() { |
234 | return true; |
235 | } |
236 | |
237 | @Override |
238 | public Cursor findFirstOrLast(Session session, boolean first) { |
239 | if (closed) { |
240 | throw DbException.throwInternalError(); |
241 | } |
242 | if (!first) { |
243 | throw DbException.throwInternalError( |
244 | "Spatial Index can only be fetch by ascending order"); |
245 | } |
246 | return find(session); |
247 | } |
248 | |
249 | @Override |
250 | public long getRowCount(Session session) { |
251 | return treeMap.sizeAsLong(); |
252 | } |
253 | |
254 | @Override |
255 | public long getRowCountApproximation() { |
256 | return treeMap.sizeAsLong(); |
257 | } |
258 | |
259 | @Override |
260 | public long getDiskSpaceUsed() { |
261 | // TODO estimate disk space usage |
262 | return 0; |
263 | } |
264 | |
265 | /** |
266 | * A cursor to iterate over spatial keys. |
267 | */ |
268 | private static final class SpatialCursor implements Cursor { |
269 | |
270 | private final Iterator<SpatialKey> it; |
271 | private SpatialKey current; |
272 | private final Table table; |
273 | private Session session; |
274 | |
275 | public SpatialCursor(Iterator<SpatialKey> it, Table table, Session session) { |
276 | this.it = it; |
277 | this.table = table; |
278 | this.session = session; |
279 | } |
280 | |
281 | @Override |
282 | public Row get() { |
283 | return table.getRow(session, current.getId()); |
284 | } |
285 | |
286 | @Override |
287 | public SearchRow getSearchRow() { |
288 | return get(); |
289 | } |
290 | |
291 | @Override |
292 | public boolean next() { |
293 | if (!it.hasNext()) { |
294 | return false; |
295 | } |
296 | current = it.next(); |
297 | return true; |
298 | } |
299 | |
300 | @Override |
301 | public boolean previous() { |
302 | return false; |
303 | } |
304 | |
305 | } |
306 | |
307 | } |
308 | |