Cluster Tables with a Spatial Index

WherobotsDB supports spatial filter based data skipping. This feature allows user to skip reading data files that don’t contain data that satisfy the spatial filter. Consider the following spatial range query:

SELECT * FROM <table_name> WHERE ST_Contains(ST_GeomFromWKT('POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))'), <geometry_column>);

WherobotsDB will skip reading data files that don’t contain data that satisfy the spatial filter. This feature is very useful when the table contains a large amount of data and the spatial filter is very selective. For example, if the table contains 1TB of data and the spatial filter will only select 1% of the data, ideally WherobotsDB will only read ~ 10GB of data to answer the query.

How Spatial Filter Push-down Works

WherobotsDB collects and records the spatial statistics of data files when writing data to the table. The spatial statistics includes the minimum bounding rectangle (MBR) of the geometries in the data file. When a spatial query is issued, WherobotsDB will first check the MBR of the geometries in the data file against the spatial filter. If the MBR doesn’t intersect with the spatial filter, WherobotsDB will skip reading the data file.

WherobotsDB keeps these statistics for a geometry(<srid>) column in the standard Apache Iceberg column bounds. For a geometry column with no declared CRS, it keeps them only on format-version 1 and 2 tables, so spatial filters on that column can’t skip data files on a format-version 3 table. See Upgrade Existing Geometry Tables.

The following figure shows how spatial filter push-down works. The MBRs of each data file are kept in the table metadata for pruning data files. The query window shown as the red rectangle only overlaps with the bounding box of datafile-2.parquet and datafile-4.parquet, so WherobotsDB can safely skip scanning datafile-1.parquet and datafile-3.parquet, reducing the IO cost and answer the query faster.

Spatial Filter Push-down and Data Skipping

Spatial filter push down works best when the spatial data near to each other were stored in the same file. This can be achieved by applying a proper partitioning to the table so that the data near to each other will be stored in the same partition, or sort the table to cluster the data by the geometry column.

CREATE SPATIAL INDEX statement

WherobotsDB adds the CREATE SPATIAL INDEX statement for rewriting the table to sort the records by geometry column:

CREATE SPATIAL INDEX FOR <table_name> USING hilbert(<geometry_column>, <precision> [, <minX>, <minY>, <maxX>, <maxY> ]) [ WHERE <condition> ] [ OPTIONS <options> ];

This statement will rewrite the data files of the table and cluster the data by the geometry column. Currently, WherobotsDB only supports the hilbert index strategy. hilbert will sort the data by the by the Hilbert index of specified geometry field. Hilbert index is based on a space filling curve called Hilbert curve, which is very efficient at sorting geospatial data by spatial proximity. You can specify the precision of the hilbert curve using the precision parameter. The precision parameter is the number of bits used to represent the Hilbert index. The higher the precision, the more accurate the sorting will be.

The two-argument form, hilbert(<geometry_column>, <precision>), clusters over World Geodetic System 1984 (WGS84) longitude and latitude bounds, [-180, 180] and [-90, 90]. On a geometry(<srid>) column the declared CRS is checked against those bounds, so the statement is rejected when the column is in another CRS. Pass <minX>, <minY>, <maxX>, <maxY> to cluster a column in another CRS, as described in Clustering a column that is not WGS84.

For example, we can cluster the data in table wherobots.db.test_table by the geometry column geom:

CREATE SPATIAL INDEX FOR wherobots.db.test_table USING hilbert(geom, 10);

CREATE SPATIAL INDEX FOR is actually a syntax sugar for calling rewrite_data_files procedure:

CALL wherobots.system.rewrite_data_files(
    table => 'wherobots.db.test_table',
    strategy => 'sort',
    sort_order => 'hilbert(geom, 10)',
    options => map('rewrite-all', 'true')
)

Users can apply any options supported by rewrite_data_files procedure to CREATE SPATIAL INDEX FOR statement using the OPTIONS clause. For example, we can set the target file size to 10MB:

CREATE SPATIAL INDEX FOR wherobots.db.test_table USING hilbert(geom, 10)
OPTIONS map('target-file-size-bytes', '10485760')

This is equivalent to

CALL wherobots.system.rewrite_data_files(
    table => 'wherobots.db.test_table',
    strategy => 'sort',
    sort_order => 'hilbert(geom, 10)',
    options => map('target-file-size-bytes', '10485760', 'rewrite-all', 'true')
)

Users can also specify a condition to filter the data to be rewritten. For example, we can rewrite the data files of the table containing data with state = 'CA':

CREATE SPATIAL INDEX FOR wherobots.db.test_table USING hilbert(geom, 10)
WHERE state = 'CA'

This is equivalent to

CALL wherobots.system.rewrite_data_files(
    table => 'wherobots.db.test_table',
    strategy => 'sort',
    sort_order => 'hilbert(geom, 10)',
    where => "state = 'CA'",
    options => map('rewrite-all', 'true')
)

Usually, users don’t need to specify the target-file-count option, as the CREATE SPATIAL INDEX statement will automatically determine the size of output data files based on the size of the table to balance the file size and the number of data files. If the default behavior of CREATE SPATIAL INDEX is not desirable, users can specify the following options to control the number of data files:

target-file-count: The number of output data files. This option is useful when you want to rewrite the table to an expected number of data files. The exact number of data files may be different from the expected number due to various factors such as compression, heuristics for avoiding too large data files, etc.

Clustering a column that is not WGS84

Running the two-argument form on a column whose declared CRS is not WGS84 is rejected, and the message names both ways out:

Cannot build a Hilbert spatial index on geometry column 'geom' with the default
bounds: its CRS is 'EPSG:3857', but the two-argument hilbert(geom, resolution) form
clusters over WGS84 lon/lat bounds ([-180, 180] / [-90, 90]), which do not cover
this CRS's coordinates. Pass explicit bounds -- hilbert(geom, resolution, minX,
minY, maxX, maxY) -- or reproject to WGS84 (OGC:CRS84 / EPSG:4326) with
ST_Transform first.

To cluster in place, pass bounds that cover the column’s coordinates. For a Web Mercator column, that is the square Web Mercator extent, ±20037508.34 meters on both axes, which is longitude ±180 and latitude ±85.0511:

CREATE SPATIAL INDEX FOR wherobots.db.test_table_3857
USING hilbert(geom, 10, -20037508.34, -20037508.34, 20037508.34, 20037508.34);

Bounds have to contain every value in the column. Widen them if your data reaches beyond that square, which EPSG:3857 permits up to latitude ±85.06, or ±20048966.10 meters.

Other Ways to Index Spatial Data

Except for the CREATE SPATIAL INDEX FOR statement, there are many other ways to index geospatial data in a table. If the data you are working with has at least one columns that are closely related to the spatial property, it is usually a good idea to partition the table using that column. For example, if you are working with a table containing census data, and the data has a state column indicating the state ID of the data, you can partition the table by state:

CREATE TABLE wherobots.db.test_table (
  id bigint,
  state string,
  geom geometry(4326)
) PARTITIONED BY (state)

The state partition works well for both regular queries with filters such as state = 'some_state' and spatial queries with filters such as ST_Intersects(geom, <query_window>). For the former, WherobotsDB skips data files whose state partition doesn’t match the filter. For the latter, it skips data files using their spatial statistics.

Partitioning by spatial proximity

If your dataset does not have a field to directly partition by, you can partition the dataset by the S2 cell ID of the geometry. This requires selecting a proper S2 resolution level suited for your dataset.

CREATE TABLE wherobots.db.test_table (
  id bigint,
  s2 bigint,
  state string,
  geom geometry(4326)
) PARTITIONED BY (s2)

The data inserted into the table should have the s2 column set to the S2 cell ID of the geometry, and the values in geom have to carry the SRID of the column, as described in Matching the column CRS:

Python
Scala
Java

df.withColumn("s2", expr("array_max(ST_S2CellIds(ST_Centroid(geom), 4))"))\
    .writeTo("wherobots.db.test_table")\
    .append()

val dfWithS2 = df.withColumn("s2", expr("array_max(ST_S2CellIds(ST_Centroid(geom), 4))"))
dfWithS2.writeTo("wherobots.db.test_table").append()

Dataset<Row> dfWithS2 = df.withColumn("s2", expr("array_max(ST_S2CellIds(ST_Centroid(geom), 4))"));
dfWithS2.writeTo("wherobots.db.test_table").append();

Though the table was partitioned using S2, we don’t need to add a predicate for the s2 partitioning column to achieve data skipping. WherobotsDB will use the spatial statistics of data files and automatically skip reading data files that don’t contain data that satisfy the spatial filter.

SELECT * FROM wherobots.db.test_table WHERE ST_Intersects(geom, ST_GeomFromText('...'))
-- No need to add a predicate for the s2 partitioning column

Sorting by GeoHash

We can manually sort the table by ST_GeoHash(<geometry_column>, <precision>) to cluster the data by spatial proximity:

Python
Scala
Java

sortedDf = df.withColumn("geohash", expr("ST_GeoHash(ST_Centroid(geom), 20)"))\
    .sort(col("geohash"))\
    .drop("geohash")
sortedDf.writeTo("wherobots.db.test_table").create()

val sortedDf = df.withColumn("geohash", expr("ST_GeoHash(ST_Centroid(geom), 20)"))
    .sort(col("geohash"))
    .drop("geohash")

sortedDf.writeTo("wherobots.db.test_table").create()

Dataset<Row> sortedDf = df.withColumn("geohash", expr("ST_GeoHash(ST_Centroid(geom), 20)"))
    .sort(col("geohash"))
    .drop("geohash");

sortedDf.writeTo("wherobots.db.test_table").create();

It is generally recommended to use CREATE SPATIAL INDEX FOR for sorting the table over manually sorting the table. CREATE SPATIAL INDEX FOR will use the Hilbert curve to sort the table, which is more efficient than sorting by GeoHash.

Start here

Connect your data

Vector data

Raster data

Iceberg tables

Maps and visualization

Cluster Tables with a Spatial Index

How Spatial Filter Push-down Works

CREATE SPATIAL INDEX statement

Clustering a column that is not WGS84

Other Ways to Index Spatial Data

Partitioning by spatial proximity

Sorting by GeoHash

​How Spatial Filter Push-down Works

​CREATE SPATIAL INDEX statement

​Clustering a column that is not WGS84

​Other Ways to Index Spatial Data

​Partitioning by columns closely related to spatial property

​Partitioning by spatial proximity

​Sorting by GeoHash

How Spatial Filter Push-down Works

CREATE SPATIAL INDEX statement

Clustering a column that is not WGS84

Other Ways to Index Spatial Data

Partitioning by columns closely related to spatial property

Partitioning by spatial proximity

Sorting by GeoHash