康瑞部落

一、问题背景

城市中超过80%的数据都与时空有关，如加油站点、出租车轨迹、交通路况等。这些数据多为半结构化和非结构化数据，并且需要管理的数据量巨大。传统的时空数据库管理海量数据时会出现性能严重下降的情况，如带有PostGIS插件的PostgresSQL。HBase等具有高可扩展性的分布式数据库又不能直接管理时空数据。为此，GeoMesa提供了大量的时空索引工具管理时空数据。但是，它支持的时空类型不够全面，并且在有些场景下它提供的索引效率很低。因此, 我们在GeoMesa的基础上研发了JUST引擎。我们提出了三种新颖索引，Z2T、XZ2T和time_range索引，加快了点时空查询、非点空间对象的时空查询，并提供了时间段范围查询。此外，我们实现了SQL接口，方便用户快速构建时空数据表和索引。我们还提供了九大时空数据模型和三个特定时空业务数据模型，并为它们默认建立了必要的时空字段和最合适的高效索引。

图1 JUST平台架构

JUST系统论文[1]已发表在ICDE会议上（数据库顶级会议之一），并且目前已落地雄安、南京、南通、宿迁等城市。您可以通过http://just.urban-computing.com/免费体验JUST公测版。

图2 论文

下面将介绍JUST系统的核心索引、数据模型、以及使用指南。

二、时空数据

随着互联网的发展，城市中产生了大量数据，其中超过80%的数据与时空有关，如空气质量报点读数、天气、出租车移动轨迹、实时路况等。这些数据都至少具有时间或者空间维度，并且可能还有其它属性维度。

基础类型

从二维地理要素的几何特征上分，空间对象可分为点（如，加油站点）、线（如，路段）、面（如，行政区域）、网（如，路网）等对象。

图3 基础空间类型

从时间维度上分，可分为时间点（如，2020年11月10日 16时03分59秒）和时间段（如，早上8点至早上10点）对象。因此，包含空间或者时间的对象可抽象出六种基础数据类型（点、线、面、网、时间点、时间段）。由这六种基础类型根据时空属性的变化情况可组合出24种既包含空间也包含时间属性的数据结构（8种静态时空类型，16种动态时空类型）（见第3节）。

三、时空索引

通常，数据库会通过时空索引来管理时空数据，而在硬件资源固定的情况下，时空索引的好坏和使用方法会影响系统性能。带有PostGIS插件的PostgresSQL利用R-tree和GiST索引管理时空数据，但是这两种索引的效率在海量数据的场景下会极大的下降。HBase等具有高可扩展性的分布式数据库能支持海量数据的存储，但它们没有直接集成管理时空数据的索引。为此，GeoMesa提供了大量的时空索引工具方便HBase管理时空数据。但是，它支持的时空类型不够全面，并且在有些场景下，如时间跨度很大的查询场景，它提供的索引效率会很低。为此，JUST引擎采用了GeoMesa提供的四种时空索引Z2、Z3、XZ2、XZ3，并自研了三种时空索引Z2T、XZ2T、time_range。此外，时空数据通常会有ID和属性。为此，JUST还提供了id索引、属性索引以及属性的二级索引。

下面，将为大家详细介绍JUST提供的时空索引（Z2、Z3、Z2T、XZ2、XZ3、XZ2T、date、time_range），以及两种非时空索引（id、attr）。其中Z2、Z3、Z2T索引用于支持点对象的空间范围查询和时空范围，它们要求对象必须有点对象。XZ2、XZ3、XZ2T索引支持非点对象的空间范围查询和时空范围查询，它们要求对象必须有非点对象。非点对象是线、面和网对象。它们具有不确定的空间形状。因此大部分空间索引都利用能包含它们最小的矩形边界来近似表达它们，再通过如R-Tree、XZ2等空间索引来进行管理。但是R-Tree不适用于分布式场景，因为JUST只提供了XZ2、XZ3、XZ2T三种适用于分布式场景的索引。date索引为时间点建立索引，它们要求对象必须时间点对象，它可以加快时间等值查询和时间范围查询。time_range索引为时间段建立索引，它们要求对象必须时间段对象，它可以加快时间段范围查询。JUST还支持两种非时空索引，id和attr索引，它们可对非时空属性建立索引。如id索引可以加快id属性的等值、大于、小于等查询，attr可以加快属性的等值、大于、小于等查询。此外，attr索引还支持二级索引，它可以加快属性+时空的条件查询。

下面是索引的详细介绍

1. 点对象索引

Z2 索引：将二维空间点编码到一维空间，进而方便存储和查询点对象，它可以加快点对象的空间范围查询。具有几何类型Point的对象可创建Z2索引。Z2采用Z-Ordering编码技术，它将空间递归分解成为更小的四个子空间，直到到达最大递归层级（resolution），分解过程中得到的四个子空间采用类似字母Z的顺序依次从0编码到3。所有的空间点都将被其所在最底层子空间的编码表示。如下图中空间点p1和p2都被“333”表示，p3被“331”表示。

图4 Z-Ordering

Z3索引：将二维空间点和时间点编码到一维空间，它可以加快点对象的时空范围查询。具有几何类型Point和时间属性的对象可以创建Z3索引。地理空间是明确的经纬度边界（-180，180），（-90，90）。但是，时间是没有边界的。因此为了能递归分解时间，我们从1970-01-01 00:00:00开始（计算纪元时间），将时间按照固定周期（time period）进行切分, 每个周期都会有确定的边界。JUST引擎可设置time period为day、week、month、year。我们用T表示一个时间周期，T.s表示该周期开始时刻，T.e表示该周期结束时刻。在一个时间周期里，Z3索引首先将T从中间(T.m)分开，如果时间点小于T.m，那么编码为0，否则编码为1。然后按同样的二分规则划分经纬度。因此，我们可用三位编码(时间在前，经纬度在后)来表示时空点所在区域。然后，递归划分子时空区域，直到达到最大递归层级。如图中所示，最大递归次数为r=3, time period为day(24小时)，时空点p（t:10,lng:-73.97,lat:40.78）在第一层r=1时处于“001” 区域（t:0，lng:0，lat:1），在第二层时处于“001” 区域的“110”子区域，最后在最大层级r=3时处于“001 110” 区域的“101” 区域。最终，我们用“001 110 101”来表示p.

图5 Z3索引

然而，通常查询的时间范围的跨度占整个时间周期的比列远大于查询的空间范围占整个地球面积(510,100,000km²)的比列，因此查询时Z3索引可能在空间的过滤效果不明显。如，查询1 km x 1km空间范围在01:00~02:00 时间范围的数据时，覆盖的时间跨度占整个时间周期的比列(2−1)/(24) >> 查询空间范围占比(1x1)/510,100,000。因此，扫描范围的key可能会覆盖到很大的不需要查询的区域。

Z2T索引：针对Z3存在的问题，我们提出了Z2T索引，，它可以加快点对象的时空范围查询。。我们先对时间分区得到不相交的time period，然后在每个time period中能单独使用Z2索引得到该时间周期中时空点的空间位置。查询时，我们首先找到与查询时间范围相交的time period，然后在每个满足条件的time period下利用构建好的Z2索引检索满足条件的数据。通常，每个time period需要查询的空间范围不会太大，因此相比于Z3索引，Z2T索引减少了大量的无用扫描。

图6 Z2T索引

2. 非点对象索引（线、面、网）

XZ2 索引：XZ2索引使用XZ-Ordering来索引非点空间对象，它可以加快非点对象的空间范围查询。XZ-Ordering是Z-Ordering的一种扩展，用于索引空间扩展的对象(即非点空间对象，如线串或多边形)。如果具有非点几何形状的对象，则可创建此索引。它用于有效地回答非点空间对象的空间查询。如下图(a)所示，XZ-Ordering的子空间（图（b））由Z-Ordering的子空间（图（a））扩大一倍得到，然后XZ-Ordering索引利用其恰好能完全包含非点空间对象的最小子空间来表示这个对象，如图（c）中，o₁由“303”表示，o₂由“033”表示。

图7XZ-Ordering

XZ3索引：xz3索引使用XZ-Ordering的三维实现来索引非点空间数据的空间位置和时间，，它可以加快非点对象的时空范围查询。如果对象具有非点几何形状和时间属性，则可创建此索引。它用于有效地回答具有非点空间和时间成分的查询。

XZ2T索引： XZ2T索引优化了XZ3索引，非它可以加快点对象时空范围查询。类似Z2T，它在每个time period里面建立了XZ2索引。

3. 其它索引

时间索引：date索引用于支持时间查询。要求对象必须有时间字段。它用于有效地加快具有时间查询的需求。

时间段索引：time_range索引可看作是XZ-Ordering的一维实现来索引具有时间段的对象。时间段索引要求对象必须有开始时间和结束时间。如果对象具有时间段属性，则可创建此索引。它用于有效地回答加快时间段范围查询的需求。

ID索引：ID索引使用对象id作为主键。它被用于有关ID的任何查询，例如：等值、大于、小于等。另外，某些属性查询可能最终也从ID索引中检索数据。

属性索引：属性索引使用属性值作为主索引键。它允许在不使用时空查询的情况下快速检索查询。属性索引可包括一个二级时空索引，因此它可以加快使用多个条件的查询。属性索引的二级索引支持Z2、Z3、Z2T、XZ2、XZ3、XZ2T、date、time_range。如查询某辆车是否在某个区域出现过，我们就对车牌号建立属性索引，并使用Z2索引对车辆产生的轨迹点建立二级空间索引，然后我们就可以根据车牌号和空间范围快速查询对应数据了。时间索引可当作一种没有二级索引的属性索引。

表1和表2总结了索引和基础对象的对应关系，表3总结了索引可以加快的查询场景。

表1 索引表及支持对象

表2支持索引

表3 支持查询

四、数据模型

虽然第一章提到的六大基础类型能单独表示六种数据类型，并在第二章介绍了针对这些基础类型的索引。但是，六大基础类型并不能完全所有的时空数据类型，因为现实世界中还存在大量地同时具有时间和空间属性的对象。因此，我们利用六大基础类型的在空间和时间属性的变化情况，组合出了24种时空类型。如表4所示，如果对象的空间和时间属性都是静态的，那么存在8种静态时空类型。如表5和表6所示，如果对象的时空属性会动态变化，那么又可以划分出16种动态时空类型，其中8种为空间不变，读数随着时间变化的时空类型，8种为时空都在变化的时空类型。

下面是静态时空类型和动态时空类型的样例

1. 静态时空类型

表4 时空静态

样例：

时空静态点：具有空间点和时间点的数据，如：空气质量站点和其修建时间。

时空静态线：具有空间线和时间点的数据，如：道路和其修建时间。

时空静态面：具有空间面和时间点的数据，如：行政区域和其边界确定时间。

时空静态网：具有空间网和时间点的数据，如：路网和其修建完成时间。

时空段静态点：具有空间点和时间段的数据，如：加油站在下午1点至2点售出加油量。

时空段静态线：具有空间线和时间段的数据，如：某条道路在早高峰（早上8:00-早上10：00）的车流量。

时空段静态面：具有空间面和时间段的数据，如：北京大兴区早高峰人口流入总数。

时空段静态网：具有空间网和时间段的数据，如：早高峰北京路况。

2. 动态时空类型

表5 空间不变，读数随着时间变化

样例：

空间静态时间动态点：不断产生读数的空间质量站点。空气质量站点的空间位置固定，但它会动态地在不同时刻产生读数。

空间静态时间动态线：道路经过的机动车。道路位置固定，但行驶在道路上的车会动态变化。

空间静态时间动态面：区域人流量。区域固定，但里面的人流量会动态变化。

空间静态时间动态网：城市动态路况。城市路网固定，但交通路况会动态变化。

空间静态时间段动态点：智能红绿灯指示信息。红绿灯空间位置固定，但它在不同时间段颜色不一样。

空间静态时间段动态线：道路车流量。道路位置固定，道路车流量不同时间段不一样。

空间静态时间段动态面：区域人流量。区域固定，但不同时间段的人流量会动态变化。

空间静态时间段动态网：城市路况。城市路网固定，但不同时间段的交通路况会动态变化，如早高峰。

表6 空间会随着时间的变化而变化

样例：

时空动态点：GPS点。出租车产生的GPS报点，时间在变化，位置也随着变化。

时空动态线：最短路径或轨迹追踪。不同时刻，由于交通路径、天气、事故等，从A地到B地的最优路径可能在不同时刻不一样；出租车最近两分钟的行驶路线，时间在变化，行驶过的路线也随着变化。

时空动态面：火灾蔓延。火势蔓延，时间在变化，火势覆盖面积也会发生变化。

时空动态网：人口迁移网。人口迁移的地点可能会随着时间的变化而变化，进而可能会产生动态的网。

时间段动态点：停留点。停留的地点在发生变化，并且需要记录进入和离开停留点的时间。

时间段动态线：轨迹段。分段后的轨迹，每条轨迹段都具有线特性，并且都有开始和结束时间。

时间段动态面：驻留区域。驻留的地点在发生变化，并且需要记录进入和离开停留点的时间。

时间段动态网：铁路运行图。不同时间段的铁路运行图不同。

五、JUST插件类型

虽然第三章提到六种基础类型和24种既有空间又有时间的时空类型。但是实际的业务应用场景中，只有12种类型会经常使用，如表7九大常用时空类型和表8三种特定业务时空类型。参考表1、表2和表3，我们可以找出时空类型适合建立的索引以及可以加快的查询。但是，用户如果对它们的对应关系不熟悉的话，极容易创建错误的索引。因此，为了方便用户创建这些复杂的常用时空对象，JUST封装了9大常用时空类型和三种特定业务类型插件表，并为它们指定了合适的默认索引。表7和表8是JUST提供的插件表类型、名称以及创建的默认索引的参照表。

表7 九大常用时空类型

表8 三种特定类型

六、使用指南

为了方便用户快速管理时空数据，JUST提供了易用的SQL引擎，它可以让用户通过很简单的SQL语句建立时空数据表和时空索引。在建表时，JUST会根据表中包含的对象类型，自动创建对应表的所有默认索引，如创建时空点表时，JUST则会为该表创建Z2、Z3、Z2T、attr(attr+z3),id共三种索引。但是，索引表会占用磁盘空间，而且有些应用场景可能不需要某些查询功能，且在某些应用场景中，可能需要创建默认索引类型以外的索引。因此JUST支持通过userdata（用户自定义表参数）来需要创建指定的索引。注意，如果表中出现多个空间或者时间字段，默认使用建表语句中的第一个空间和时间字段建立索引。

下面是创建各种时空表的示例

1. 创建默认空间表

create table [表名](

  [字段名] [空间类型],

  …

)

例子：

create table point(

  pPoint

)

2. 创建默认时空表

create table [表名](

  [字段名] [空间类型],

  [字段名] [时间类型],

  …

)

例子：

create table non_point_time(

  poly Polygon,

  time Date

)

3. 创建指定索引表

create table [表名](

  [字段名] [空间类型],

  [字段名] [时间类型],

  …

) userdata{

 "geomesa.indices.enabled":"[索引名]"

}

例子

create table non_point_index(

  poly polygon,

  time Date

) userdata {

         "geomesa.indices.enabled":"xz2t"

}

4. 创建时间索引表

create table date_table(

   [字段名]Date:index=true,

   …

)

5. 创建时间段索引表

create table [表名](

   [开始时间字段名] Date:index=true,

   [结束时间字段名] Date,

   …

) userdata {

         "geomesa.indices.enabled":"attr",

         "geomesa.attr.type":"time_range ",

         "geomesa.xz3.timerange.key":"[用于查询时间段字段名]",

         "geomesa.xz3.timerange.start":"[开始时间字段名]",

         "geomesa.xz3.timerange.end":"[结束时间字段名]"

}

6. 创建空间时间段索引表

create table [表名](

[字段名] [空间类型],

   [开始时间字段名]Date,

   [结束时间字段名] Date,

   …

) userdata {

         "geomesa.indices.enabled":"attr",

         "geomesa.attr.type":"time_range ",

         "geomesa.xz3.timerange.key":"[用于查询时间段字段名]",

         "geomesa.xz3.timerange.start":"[开始时间字段名]",

         "geomesa.xz3.timerange.end":"[结束时间字段名]"

}

例子

create table st_time_range_table(

      p Point,

    ts Date,

    te Date

) userdata {

         "geomesa.indices.enabled":"z3",

         "geomesa.xz3.timerange.key":"time_range",

         "geomesa.xz3.timerange.start":"ts",

         "geomesa.xz3.timerange.end":"te"

}

7. 创建ID索引

create table [表名](

      [id字段名] [类型]:primarykey,

    …

)

注：如果在userdata中设置了"geomesa.indices.enabled"，则必须加上”id”索引

例子

create table id_table(

      fid string:primary key

)

8. 创建属性表

create table [表名] (

      [属性字段名] [类型]:index=true

         [非必要字段名] [空间类型],

[非必要字段名] [时间类型],

…

)userdata {

         "geomesa.indices.enabled":"attr",

“geomesa.attr.type”:”[二级索引类型]”

}

例子

给属性a建立属性+点空间索引（z2）

create table attr_point_table(

   astring:index=true,

  geo Point,

  time Date

) userdata {            

         "geomesa.indices.enabled":"attr",

         "geomesa.attr.type":"z2"

}

给属性a建立属性+点时空索引（z2t）

create table attr_st_table(

   astring:index=true,

  geo Point,

  time Date

) userdata {            

         "geomesa.indices.enabled":"attr",

         "geomesa.attr.type":"z2t"

}

给属性a建立属性+非点空间索引（xz2）

create table attr_npoint_table(

   astring:index=true,

  geo Polygon,

  time Date

) userdata {            

         "geomesa.indices.enabled":"attr",

         "geomesa.attr.type":"xz2"

}

给属性a建立属性+非点时空索引（xz2t）

create table attr_nst_table(

   astring:index=true,

  geo Polygon,

  time Date

) userdata {            

         "geomesa.indices.enabled":"attr",

         "geomesa.attr.type":"xz2t"

}

给属性a建立属性+时间段索引（time_range）

create table attr_timerange_table(

   astring:index=true,

   tsDate,

   teDate

) userdata {            

         "geomesa.indices.enabled":"attr",

         "geomesa.attr.type":"time_range",

"geomesa.xz3.timerange.key":"time_range",

         "geomesa.xz3.timerange.start":"ts",

         "geomesa.xz3.timerange.end":"te"

}

9. 创建插件表

（1）创建非SD插件类型表：SS表和DD表

--(pluginName = SSPoint/SSLine/SSRegion/DDPoint/DDLine/DDRegion)

create table <table_name> as<pluginName>

(

metaName1 dataType,

metaName2 dataType

)

[(

readingName1 dataType,

readingName2 dataType

)]

[userdata{"key":"value","key":"value"}]

插入时空静态插件类型（SS）：SSPoint/SSRegion/SSLine

• 默认字段：idString, oid String, geom Point/Polygon/LineString；
• 自定义字段：

meta属性：表示静态空间对象的附加信息， 如LineString的长度；

reading属性(可选)：表示表示空间对象的每个点的数据信息，如LineString的每个点的属性；

• 示例：

create sspoint_table as sspoint (meta1String, meta2 Double)

• 注意：在创建表的时候最多两个括号，第一个括号里面是自定义meta字段，第二个括号里面是自定义reading字段；如果只有一个括号则认为是meta自定义字段，如果没有括号则认为没有用户自定义字段。SSPoint插件类型没有reading属性。

时空动态插件类型（DD）：DDPoint/DDRegion/DDLine

• 默认字段：idString, oid String, geom Point/Polygon/LineString, time Timestamp；
• 自定义字段：

mete属性：表示整个空间对象随时间变化的读数信息。

reading属性(可选)：表示空间对象的每个点上的读数信息。

• 示例 1：

create ddline_table as ddline (lengthDouble) (point_deriction Double)

• 示例2：

create ddregion_table as ddregion (areaDouble, regionName String)

• 注意：DDPoint插件类型没有reading属性

（2）SD插件类型表

--(pluginName = SDPoint/SDLine/SDRegion)

create table <table_name> as<pluginName>

(

 metaName1 dataType,

 metaName2 dataType

)

(

readingName1 dataType,

  readingName2 dataType

)

[userdata{"key":"value","key":"value"}]

• 默认字段：idString, oid String, geom Point/Polygon/LineString, time Timestamp;
• 自定义字段:

mete表示空间对象不随时间变化的信息；

reading表示空间对象随时间变化的读数信息；

• 示例：

create sdregion_table as sdregion (meta1String, meta2 Double) (reading1 Integer, reading2 Float)

（3）特定业务应用表

--(pluginName = Trajectory/RoadNetwork/RouteOfTrajectory)

create table <table_name> as<pluginName>

[( 

metaName1 dataType,

  metaName2 dataType 

)] 

[(

  readingName1 dataType,

readingName2 dataType

)]

路网插件类型（RoadNetwork）

• 自定义meta字段：startidInteger, endid Integer, direction Integer, maxlanes Integer, level Integer,speedlimit Double, road_length Double
• 用户还可以继续扩展meta字段。
• 示例：

create roadnetwork_table as RoadNetwork (weightDouble, name String)

注意：在创建表时最多能有一个括号来扩展meta字段。

轨迹插件类型（Trajectory）

• 自定义meta字段如下：endtimeTimestamp, tid String, timeseries TimeSeries, startposition Point, endpositionPoint, point_number Integer, length Double, speed Double, signature Bytes
• 用户还可以继续扩展meta字段，比如区分是出租车轨迹还是行人轨迹，并且可以扩展自定义reading字段用来表示每个轨迹点的瞬时速度、方向、是否载客等信息。 
• 示例：

create trajectory_table as Trajectory (trajectorytypeInteger) (direction Double)

注意：在创建表的时候最多两个括号，第一个括号里面是自定义meta字段，第二个括号里面是自定义reading字段；如果只有一个括号则认为是meta自定义字段，如果没有括号则认为没有用户自定义字段。

RouteOfTrajectory插件类型（RouteOfTrajectory）

• 自定义meta字段如下：endtimeTimestamp, startposition Point, end_position Point, tid String, routesArray[RouteInTrajectory]
• 用户还可以继续扩展自定义meta字段，比如routeoftrajectory的长度、平均速度。
• 示例：

create route_of_trajectory_table as RouteOfTrajectory(length Double, avg_speed Double)

注意：在创建表时最多能有一个括号来扩展meta字段。

七、查询需求

JUST为时空表提供了大量的时空索引和非时空索引，可以加快时空查询和一些非时空查询的效率。

下面是JUST使用范围和属性查询的示例：

1. RangeQuery

（1）时间范围查询

select

  *

from

 date_table

where

 time >= to_timestamp('2020-11-12 00:00:00') and time <=to_timestamp('2020-11-13 00:00:00')

（2）空间范围查询

select

  *

from

 point

where

  pwithin st_makeBBox(110.0, 30.0, 110.7, 30.8)

（3）时空范围查询

select

  *

from

 non_point_time

where

  polywithin st_makeBBox(110.0, 30.0, 110.7, 30.8) and time >=to_timestamp('2020-11-12 00:00:00') and time <= to_timestamp('2020-11-1300:00:00')

（4）时间段范围查询

select

  *

from

 time_range_table

where

 time_range between to_timestamp('2020-11-12 00:00:00') andto_timestamp('2020-11-13 00:00:00')

或

st_ecql("time_range during2020-11-12T00:00:00/2020-11-13T00:00:00",time_range_table,local)

（5）空间时间段范围查询

st_ecql("bbox(p,110.0, 30.0, 110.7,30.8) and time_range during2020-11-12T00:00:00/2020-11-13T00:00:00",time_range_table,local)

2. 属性查询

select

  *

from

 attr_st_table

WHERE

  a ="xxx" and geo within st_makeBBox(110.0, 30.0, 110.7, 30.8) and time>= to_timestamp('2020-11-12 00:00:00') and time <=to_timestamp('2020-11-13 00:00:00')

参考文献：

[1] Li, Ruiyuan, et al. "Just: Jd urbanspatio-temporal data engine." 2020 IEEE 36th InternationalConference on Data Engineering (ICDE). IEEE, 2020.