Geomesa 索引

在之前的文章中，已经对Geomesa的基本功能和基本查询与写入操作做了介绍。我们了解到Geomesa是一个分布式地理大数据存储框架，它通过与许多分布式数据库整合，并提供标准化的接口，使得用户能方便、高效地在这些分布式数据库中查询、检索、处理时空大数据。在使用时，我们只需调用Geomesa提供的接口，而无需关心数据在底层数据库中的存储方式。但是，理解Geomesa数据存储方式，特别是其建立索引的方式，对我们更好的设计数据表结构，从而获得更高效的性能是很有帮助的。

Geomesa索引类别

GeoMesa提供多种索引以满足不同类型数据的检索需要：

image.png

Z2与Z3索引

Z2与Z3索引分别使用二维和三维的Z曲线进行时空索引。Z曲线是一种空间填充曲线，可以将高维的空间用一维的折线表示。下图展示了二维和三维Z曲线的示意图：

image.png
Geohash是Z曲线的一种实现，它的原理简单来说就是将经纬度划分并用二进制表示，经度和纬度的二进制交错合并，形成每一个区块的编号，将这些区块的中心按编号从小到大连接起来，就形成了Z曲线，而这些编号，就是各个区块的Geohash编码。
image.png
三维的Z曲线也类似，只不过Geomesa将第三维用来存储时间，将连续的时间也按处理经纬度那样进行划分，和经纬度一起编码、存储，这样，当使用时间+空间的条件查询时，就能利用三维Z曲线的编码，加快查询速度。

XZ2和XZ3索引

对于点（Point）类型空间数据的存储，使用Z曲线能够实现高效的索引。但是对于复杂的空间数据（要素），如折线（Line）、多边形（Polygon）等，它们由若干个点通过不同的连接方式构成，如果要对其建立索引，最原始的方法就是对组成他们的各个点使用Geohash构建索引，但这样做会造成大量的冗余，而且在检索时需要比较每个点的位置，造成不必要的开销；另一种One-value方法，该方法首先计算要素的最小包围盒，再以能够包含该最小包围盒的最细粒度的Geohash格网编码作为该要素的索引，这样每个要素就有唯一的索引值了，但这种方法的缺点也很明显，当要素跨越了Geohash格网划分线时，就需要使用上一级的Geohash格网编码，造成编码长度过短，索引效果不好的情况，极端情况下，还会出现编码为空的可能（即要素只能被第0级Geohash格网完全包含）；针对以上方法的缺点，有人提出了一种Extended Z-ordering的方法，该方法解决了One-value方法中，某些图形编码长度短，甚至编码为空的问题，提高表示精度，减小表示误差，同时还提出一种复杂的编码模式，将非定长的编码转化为定长编码，最后设计了一种对应于该编码的高效查询算法，具体细节请参考原始论文：

Böhm, Klump, and Kriegel. “XZ-ordering: a space-filling curve for objects with spatial extension” 6th. Int. Symposium on Large Spatial Databases (SSD), 1999, Hong Kong, China.

下图是这三种方法的示意图，可以看出XZ索引（Extended Z-ordering）表示的范围更加精细，且减少了存储冗余。

image.png

Geomesa就采用了XZ索引方法构建复杂要素的索引，与Z2和Z3类似，XZ2用于只含空间属性的数据，XZ3则用于同时包含时间和空间属性的数据。

ID 索引

Geomesa中存储的每条数据都对应一个ID，这个ID可由Geomesa自动生成，也可以是自定义的，类似于关系数据库中的主键。Geomesa会单独为ID构建一个索引，这意味着我们可以使用ID作为查询条件来快速的查询数据。

属性索引

空间数据往往带有若干个属性字段，属性索引就是用来对这些属性字段建立索引的。

Geomesa定义表结构

Geomesa使用SimpleFeatureType定义表结构，在SimpleFeatureType中指定了表中各个字段的列名、数据类型、是否建立索引等信息，还可以在SimpleFeatureType中设置字段级和表级的用户数据（user-data），以满足不同数据存储的需要。

SimpleFeatureType的创建方式有两种，分别是使用字符串定义和使用配置文件（TypeSafe Configuration Files）定义，如， 使用字符串定义的SimpleFeatureType：

"name:String,dtg:Date,*geom:Point:srid=4326;option.one='foo',option.two='bar'"

在这个SimpleFeatureType中，定义了类型为String的name字段，类型为Date的dtg字段，以及类型为Point的geom字段，此外，对geom字段还设置了字段级的用户数据srid=4326，用于设置该字段属性。被分号分隔的option.one='foo',option.two='bar'是表级的用户数据，用于设置整个表的属性。

上面的SimpleFeatureType也可以使用配置文件来定义：

geomesa {
  sfts {
    "mySft" = {
      attributes = [
        { name = name, type = String             }
        { name = dtg,  type = Date               }
        { name = geom, type = Point, srid = 4326 }
      ]
      user-data = {
        option.one = "foo",
        option.two = "bar"
      }
    }
  }
}

除了以上两种完整创建SimpleFeatureType的方法外，Geomesa还提供了Java函数对已经存在的SimpleFeatureType做局部修改，其中，对字段级和表级用户数据的修改方式如下：

SimpleFeatureType sft = ...
sft.getUserData().put("option.one", "foo");  // 表级
sft.getDescriptor("name").getUserData().put("index", "true");  // 字段级

Geomesa索引设置

对Geomesa表索引的设置，都是通过设置字段级和表级的用户数据来实现的。

默认索引

首先来看Geomesa构建索引的默认方法。假设数据类型中包含3个字段，类型分别是日期、几何、普通属性，那么在未指定任何索引的情况下，Geomesa会建立Z2、Z3索引（或者XZ2、XZ3索引，根据几何字段的具体类别确定）以及ID索引。

在此基础上，如果要对普通属性构建索引，则需要在SimpleFeatureType中对该属性添加index=true选项。

如果数据中存在几何类型的字段，Geomesa会使用该字段构建Z2索引（XZ2索引）。如果数据中包含日期类型的字段，Geomesa将使用该字段与几何字段共同构建Z3索引（XZ3索引）。

• 对于有多个几何字段的数据，Geomesa只会使用一个字段构建空间索引，默认是第一个几何字段，也可以用default=true选项指定。
• 对于有多个日期字段的数据，Geomesa使用其中一个（默认是第一个）与几何字段构建时空索引（Z3/XZ3），其余日期字段若设置了index=true选项，则他们将被当做普通的属性，构建属性索引。

需要注意的是，如果使用日期字段和几何字段共同构建时空索引之后，单独查询日期字段就无法使用该索引了（单独查询几何字段是可以使用索引的，因为同时建立了Z2/XZ2索引），会导致全表扫描，造成查询速度很慢。

多时空索引

如果存在多个几何和日期字段，可以手动指定他们的组合，建立多个时空索引，如：

String spec = "name:String,dtg:Date,*start:Point:srid=4326,end:Point:srid=4326";
SimpleFeatureType sft = SimpleFeatureTypes.createType("mySft", spec);
// enable a default z3 index on start + dtg
sft.getUserData().put("geomesa.indices.enabled", "z3");
// alternatively, enable a z3 index on start + dtg, end + dtg, and an attribute index on
// name with a secondary index on dtg. note that this overrides the previous configuration
sft.getUserData().put("geomesa.indices.enabled", "z3:start:dtg,z3:end:dtg,attr:name:dtg");

日期索引

要修改默认的日期索引策略，可以手动设置。

• 指定参与时空索引的日期字段：

sft1.getUserData().put("geomesa.index.dtg", "myDate")

• 不将日期字段与几何字段共同索引：

sft2.getUserData().put("geomesa.ignore.dtg", true);

使用Z3/XZ3索引的日期，默认会按星期被切分为多个块，与空间数据一同构建Z3/XZ3索引。Geomesa提供了四种不同的切分粒度，分别是：day, week, month, year，应该根据具体的数据特点和查询需求而确定，设置方法为：

sft.getUserData().put("geomesa.z3.interval", "month");

ID 索引

默认情况下，Geomesa使用UUID作为每条记录的Feature ID，其格式是一个使用十六进制表示32位字符串：{8}-{4}-{4}-{4}-{12}，例如：28a12c18-e5ae-4c04-ae7b-bf7cdbfaf234。当然也可以自定义Feature ID：

// use a geotools SimpleFeatureBuilder to create our features
SimpleFeatureBuilder builder = new SimpleFeatureBuilder(getSimpleFeatureType());

builder.set("GLOBALEVENTID", record.get(0));
builder.set("Actor1Name", record.get(6));
builder.set("Actor1CountryCode", record.get(7));
......
// be sure to tell GeoTools explicitly that we want to use the ID we provided
builder.featureUserData(Hints.USE_PROVIDED_FID, java.lang.Boolean.TRUE);

// build the feature - this also resets the feature builder for the next entry
// use the GLOBALEVENTID as the feature ID
SimpleFeature feature = builder.buildFeature(record.get(0));

// Insert
FeatureWriter<SimpleFeatureType, SimpleFeature> writer = 
                      datastore.getFeatureWriterAppend(sft.getTypeName(), Transaction.AUTO_COMMIT)
SimpleFeature toWrite = writer.next();
// copy attributes
toWrite.setAttributes(feature.getAttributes());
toWrite.getUserData().put(Hints.PROVIDED_FID, feature.getID());

几何索引精度

使用precision设置几何字段的存储精度，其类型是整形，范围在【-7,7】之间，负数表示小数点左边的精度（保留十位，百位...），整数表示小数位数，小数位数达6位的经纬度坐标，其地理误差在10cm左右。设置方法为：

SimpleFeatureType sft = ...
sft.getDescriptor("geom").getUserData().put("precision", "4");

属性索引

对于属性索引，Geomesa可以显示地指定他们的“势”（Cardinality）。即该属性的唯一值数量。对于包含多个属性条件的查询，Geomesa会优先使用“势”高的属性的索引，以过滤更多的无效数据，提高查询效率。例如一个极端情况，属性1只包含两种可能取值，而属性2包含10种，那么当查询条件中同时包含这两个条件时，应该首先使用属性2的索引，再在满足属性2条件下的结果中，找出满足属性1条件的数据。要保证Geomesa优先考虑属性2的索引，则需要定义属性1的势为high，而属性2的势为low，设置方法为：

SimpleFeatureType sft = ...
sft.getDescriptor("name").getUserData().put("index", "true");
sft.getDescriptor("name").getUserData().put("cardinality", "high");

查询计划

构建好数据表结构以及相应的索引信息后，Geomesa会通过内置的方法为不同的查询条件设计不同的查询计划，使用不同的索引。但这些自动生成的查询计划不一定是最优的。我们可以输出这些计划，查看执行查询操作时具体使用了哪些索引，从而进行有针对性的改进。输出查询计划方法是在log4j.properties文件中添加：

log4j.category.org.locationtech.geomesa.index.utils.Explainer=TRACE

这样在查询过程中，就会自动输出Geomesa的查询计划，一个查询计划的例子如下：

Running query NumSources > 0 AND BBOX(geom, -120.0,30.0,-75.0,55.0)
Planning 'gdelt-quickstart' NumSources > 0 AND BBOX(geom, -120.0,30.0,-75.0,55.0)
  Original filter: NumSources > 0 AND BBOX(geom, -120.0,30.0,-75.0,55.0)
  Hints: bin[false] arrow[false] density[false] stats[false] sampling[none]
  Sort: none
  Transforms: none
  Strategy selection:
    Query processing took 1ms for 2 options
    Costs: FilterPlan[AttributeIndex(NumSources,geom,dtg)[NumSources > 0][BBOX(geom, -120.0,30.0,-75.0,55.0)]] (Cost 250 in 3ms); FilterPlan[Z2Index(geom)[BBOX(geom, -120.0,30.0,-75.0,55.0)][NumSources > 0]] (Cost 400 in 0ms)
    Filter plan selected: FilterPlan[AttributeIndex(NumSources,geom,dtg)[NumSources > 0][BBOX(geom, -120.0,30.0,-75.0,55.0)]]
    Filter plans not selected: FilterPlan[Z2Index(geom)[BBOX(geom, -120.0,30.0,-75.0,55.0)][NumSources > 0]]
    Strategy selection took 3ms for 2 options
  Strategy 1 of 1: AttributeIndex(NumSources,geom,dtg)
    Strategy filter: AttributeIndex(NumSources,geom,dtg)[NumSources > 0][BBOX(geom, -120.0,30.0,-75.0,55.0)]
    Geometries: FilterValues(List(POLYGON ((-120 30, -120 55, -75 55, -75 30, -120 30))),true,false)
    Intervals: FilterValues(List(),true,false)
    Plan: BatchScanPlan
      Tables: geomesa.test_geomesa_gdelt_2dquickstart_attr_NumSources_geom_dtg_v8
      Column Families: d
      Ranges (4): [%00;80000000%01;::%00;%ff;%ff;%ff;), [%01;80000000%01;::%01;%ff;%ff;%ff;), [%02;80000000%01;::%02;%ff;%ff;%ff;), [%03;80000000%01;::%03;%ff;%ff;%ff;)
      Iterators (1):
        name:filter-transform-iter, priority:25, class:org.locationtech.geomesa.accumulo.iterators.FilterTransformIterator, properties:{sft=GLOBALEVENTID:String,Actor1Name:String,Actor1CountryCode:String,Actor2Name:String,Actor2CountryCode:String,EventCode:String,NumMentions:Integer,NumSources:Integer,NumArticles:Integer,ActionGeo_Type:Integer,ActionGeo_FullName:String,ActionGeo_CountryCode:String,dtg:Date,*geom:Point:srid=4326;geomesa.index.dtg='dtg',geomesa.stats.enable='true',geomesa.indices='z3:6:3:geom:dtg,z2:5:3:geom,id:4:3:,attr:8:3:EventCode:geom:dtg,attr:8:3:NumSources:geom:dtg', index=attr:8:NumSources:geom:dtg, cql=BBOX(geom, -120.0,30.0,-75.0,55.0)}
    Plan creation took 7ms
  Query planning took 13ms

可以看到，本次查询使用了AttributeIndex(NumSources,geom,dtg)这一索引。

Geomesa选择索引的策略主要有两种，基于代价的策略（Cost-Based Strategy, 目前只支持Acculumo数据库）和启发式的策略（Heuristic Strategy），基于代价的策略是通过在存储数据时对数据各个字段分布的统计结果（数量、最大/最小值等），估计使用不同索引的代价，从而确定应该使用哪个索引；而启发式的策略是仅仅根据查询条件（条件字段是属性条件还是几何条件，关系是等于还是范围，属性字段对应的“势”，等等），确定应该使用的索引。设置方法为：

Query query = new Query(typeName, ECQL.toFilter(queryCQL));
query.getHints().put(QueryHints.COST_EVALUATION(), CostEvaluation$.MODULE$.Stats()); // 基于代价
query.getHints().put(QueryHints.COST_EVALUATION(), CostEvaluation$.MODULE$.Index()); // 启发式

当然还有最简单粗暴的方法，直接指定希望使用的索引名字：

Query query = new Query(typeName, ECQL.toFilter(queryCQL));
query.getHints().put(QueryHints.QUERY_INDEX(), "attr:8:rate:coord");

其中，attr:8:rate:coord就是指定索引的名字，所有可取的值可以在查询计划中找到。

结果排序

在我的使用过程中，还有一个比较重要的发现，就是当查询条件中存在排序指令时，会有大量数据通过网络下载到本地，而且所需时间与查询结果的量成正比，比不带排序命令的速度慢了许多，即便需要排序的字段已经构建了索引，也是如此。查找官方文档后，发现在数据导出模块中，有提到：

The --sort-by argument can be used to sort the output by one or more attributes. Note that for local exports, this will usually be done in-memory, so can be costly for large result sets. By default, output is sorted in ascending order; --sort-descending can be used to reverse the sort order.

也就是说，排序操作是获取了全部数据后，在本地执行的，这与我观察到的现象是吻合的。我目前还没有找到更好的办法解决该问题，这里附上我使用的排序操作的API：

// sort by
Query query = new Query(typeName, ECQL.toFilter(queryCQL));
if (!sortBy.equals("")){
    FilterFactoryImpl ff = new FilterFactoryImpl();
    query.setSortBy(new SortBy[]{new SortByImpl(
         ff.property(sortBy),
         ascend ? SortOrder.ASCENDING : SortOrder.DESCENDING
     )});
}

数据库表构成

我们可以查看数据库实际生成的表，帮助我们理解Geomesa的索引机制，这里使用Accumulo数据库为例。

我们使用Geomesa Tutorial自带的GDELTData进行试验，其SimpleFeatureType如下：

String sft = "GLOBALEVENTID:String," +
"Actor1Name:String," +
"Actor1CountryCode:String," +
"Actor2Name:String," +
"Actor2CountryCode:String," +
"EventCode:String:index=true,"+
"NumMentions:Integer," +
"NumSources:Integer:index=true," +
"NumArticles:Integer," +
"ActionGeo_Type:Integer," +
"ActionGeo_FullName:String," +
"ActionGeo_CountryCode:String," +
"dtg:Date," +
"*geom:Point:srid=4326"

该SFT定义了一个包含14个字段的数据结构，其中，geom是默认几何数据字段，dtg是默认日期字段，并且还在EventCode和NumSources两个属性字段上构建了索引。使用该数据结构最终生成的数据表如下：

image.png

可以看到，
geomesa.test_geomesa_gdelt_2dquickstart_id_v4 表，是ID索引表，
geomesa.test_geomesa_gdelt_2dquickstart_z2_geom_v5表，是使用geom字段生成的Z2索引表，
geomesa.test_geomesa_gdelt_2dquickstart_z3_geom_dtg_v6表，是使用geom字段+dtg字段生成的Z3索引表，
geomesa.test_geomesa_gdelt_2dquickstart_attr_NumSources_geom_dtg_v8 和
geomesa.test_geomesa_gdelt_2dquickstart_attr_EventCode_geom_dtg_v8两张表，分别是两个属性字段与geom字段+dtg字段生成索引表；

我们再到命令行中输出这几张表的前几行：

ID索引表
Z2索引表
Z3索引表
属性索引表

虽然大多是二进制的值，但是也不难发现几个规律：

• 所有的索引表，其存储的值都是完整的数据（列族“d”），这意味着查询只会在一个表中完成。（Geomesa可以指定一个特定的列族，该列族只存放部分字段，这样可以避免对非查询数据不必要的读取，详见Column Groups)；
• ID索引表的键就是Feature ID；
• 其他索引表的键，即为该索引的二进制值，并且键的末尾都添加了Feature ID；
• 属性索引表的键比其他Z2，Z3索引表的键都要长，结合其表名判断（如：geomesa.test_geomesa_gdelt_2dquickstart_attr_EventCode_geom_dtg_v8），应该是将属性索引拼接上Z3索引所构成的，目的应该是加快属性+时空条件查询时的速度。

结语

Geomesa的索引还有很多可以配置的选项，由于我目前还没有用到，这里就不列举了。查看全部的详细内容，请阅读官方文档用户手册。