XZ3 (or Z3), XZ2 (or Z2), and record indices are built by default. XZ3 or XZ2 indices are built for objects with extent, and Z3 or Z2 are used for points. Join and full attribute indices are also available.
The primary spatio-temporal index (for points) is an index over the Z3 addresses of the geometries.
The Row ID is of variable length: the first 2 bytes are the epoch if there is no split, and the first 3 bytes are the concatenation of the split number (not shown in the picture above) and the epoch if there is a split.
The split number is the modulus of the hash of the object and the number of splits.
The epoch is a 16-bit number which nominally represents the week since the Java epoch,
but can be configured to hold the day, month, or year since the epoch.
For points, X, Y, and Time are fixed at 21, 21, and 20 bits of precision, respectively. Time is considered at the resolution of 1 second, and 20 bits is just enough to count the number of seconds in one week.
This index is used for performing spatial queries that do not have a temporal constraint on points. For points, X and Y both have 31 bits of precision.
XZ3 and XZ2 are the default indices used to store objects with extent in GeoMesa 1.2.5. An extension of Z-order, XZ-order enlarges regions associated with nodes at the same level within the tree -- the tree implied by the pattern of divisions -- so that they overlap. This allows items to be associated with only one (Z-order) address, because the boundaries between neighboring nodes are now rectangles rather than lines, which resolves the problem of having to multiply-store of objects with extent. Objects with extent are indexed with a maximum resolution of 36 bits (12 divisions into eighths), while points are indexed with a maximum resolution of 24 bits (12 divisions into quarters).
This is an index over the UUIDs of the features.
There are two types of attribute indices, join and full. "Join" indices index the UUID, time, and geometry of an object, while "full" indices index all of its attributes.
The focus of this section is the Z3 index, the primary spatio-temporal index used.
featureStore.addFeatures(featureCollection);
- AccumuloFeatureStore.addFeatures
- AccumuloDataStore.getFeatureWriterAppend
- AppendAccumuloFeatureWriter constructor
- ...
- AppendAccumuloFeatureWriter.writer which is actually AccumuloFeatureWriter.writer
- AccumuloFeatureWriter.getTablesAndWriters
- Z3Table.writer
- Z3Table.getGeomRowKeys
- Z3Table.zBox
- Z3Table.zBox
- Z3Table.getZPrefixes
Items 1 through 5 in the list above follow the GeoTools API.
Points are inserted with 62 bits of precision. For objects with extent, their ranges are repeatedly subdivided until ranges with prefixes of at least 24 bits in length are found, then object is associated with each of those prefixes.
In this section we analyze the following query
FeatureIterator featureItr = featureSource.getFeatures(query).features();assuming that the SimpleFeatures that are being looked for are geometries with extent.
We also assume in what follows that the qury is fully spatio-temporal (that it does not implicate UUIDs, attributes, &c).
The result of that line is an iterator of SimpleFeatures which are responsive to the query.
Restricting attention to query planning, the line above produces the sequence below
- AccumuloFeatureSource.getFeatures
- AccumuloFeatureSource.getFeatureSource.getFeaturesNoCache
- AccumuloFeatureCollection constructor
- ...
- AccumuloFeatureCollection.reader
- AccumuloDataStore.getFeatureReader
- AccumuloFeatureReader.apply
- AccumuloFeatureReaderImpl constructor
- ...
- QueryPlanner.runQuery
- QueryPlanner.getQueryPlans
- QueryStrategyDecider.chooseStrategies
- QueryStrategyDecider.createStrategy
- Z3IdxStrategy.getQueryPlan
- Z3IdxStrategy.getQueryPlan.getRanges
- Called once per prefix, where prefixes are a function of the epoch (week) and the split
- Z3IdxStrategy.getGeomRanges
- Z3SFC.ranges
- org.locationtech.sfcurve.Z3.zranges which is actually org.locationtech.sfcurve.ZN.zranges
Items 1 through 9 in the list above follow the GeoTools API.
In the case of queries which are not (purely) spatio-temporal, indices other than the Z3 index may be used. As mentioned earlier, the Z2 index will be used for purely spatial. In the case of a search over a spatio-temporal box for objects with a particular attribute of a particular value, GeoMesa uses cost-based optimization (CBO) to determine which index to use.