城市中超过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种既包含空间也包含时间属性的数据结构(见第3节)。
通常,数据库会利用时空索引来管理时空数据。因此,在硬件资源固定的情况下,时空索引的好坏和使用方法会影响系统性能。JUST系统采用了GeoMesa提供的四种时空索引Z2、Z3、XZ2、XZ3,并自研了三种时空索引Z2T、XZ2T、time_range。此外,时空数据通常会有ID和属性。为此,JUST还提供了id索引、属性索引以及属性的二级索引。
二. 时空索引
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” 区域,在第二层时处于“001” 区域的“110”子区域,最后在最大层级r=3时处于“001110” 区域的“101” 区域。最终,我们用“001 110 101”来表示p.
图5 Z3索引
Z2T索引:然而,通常查询的时间范围的跨度占整个时间周期的比列远大于查询的空间范围占整个地球面积的比列,因此查询时Z3索引可能在空间的过滤效果不明显。如,查询1 km x 1km空间范围在01:00~02:00 时间范围的数据时,覆盖的时间跨度占整个时间周期的比列(2−1)/(24) >> 查询空间范围占比
(1x1)/510,100,000。因此,扫描范围的key可能会覆盖到很大的不需要查询的区域。针对Z3存在的问题,我们提出了Z2T索引,我们先对时间分区得到不相交的time period,然后在每个time period中能单独使用Z2索引得到该时间周期中时空点的空间位置。查询时,我们首先找到与查询时间范围相交的time period,然后在每个满足条件的time period下利用构建好的Z2索引检索满足条件的数据。通常,每个time period需要查询的空间范围不会太大,因此相比于Z3索引,Z2T索引减少了大量的无用扫描。
图6 Z2T索引
2. 非点对象索引(线、面、网)
由于线、面等非点空间对象具有不确定的空间形状,因此大部分空间索引都利用能包含它们最小的矩形边界来近似表达它们。然后,利用空间索引如R-Tree、XZ2等管理这些空间对象。网对象通常会覆盖很大的空间范围,并且具有复杂的结构。因此JUST会将网对象存储成由边和节点组成的表,我们只对网对象的边建立索引。
XZ2 索引:XZ2索引使用XZ-Ordering来索引非点空间对象。XZ-Ordering是Z-Ordering的一种扩展,用于索引空间扩展的对象(即非点空间对象,如线串或多边形)。如果具有非点几何形状的对象,则可创建此索引。它用于有效地回答非点空间对象的空间查询。如下图(a)所示,XZ-Ordering的子空间(图(b))由Z-Ordering的子空间(图(a))扩大一倍得到,然后XZ-Ordering索引利用其恰好能完全包含非点空间对象的最小子空间来表示这个对象,如图(c)中,o1由“303”表示,o2由“033”表示。
图7
XZ-Ordering
XZ3索引:xz3索引使用XZ-Ordering的三维实现来索引非点空间数据的空间位置和时间。如果对象具有非点几何形状和时间属性,则可创建此索引。它用于有效地回答具有非点空间和时间成分的查询。
XZ2T索引:类似Z2T,XZ2T索引优化了XZ3索引。它在每个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 索引表及支持对象
索引 |
支持对象 |
Z2 |
具有几何类型Point的对象 |
Z3 |
具有几何类型Point和时间属性的对象 |
Z2T |
具有几何类型Point和时间属性的对象 |
XZ2 |
具有非点几何形状的对象 |
XZ3 |
具有非点几何形状和时间的对象 |
XZ2T |
具有非点几何形状和时间的对象 |
date |
具有时间属性的对象 |
time_range |
具有时间段属性(必须有开始时间,结束时间)的对象 |
id |
具有id属性对象 |
attr |
具有属性的对象,并且支持二级时空索引(用于时空过滤)。 |
表2 支持查询
索引 |
支持查询 |
Z2 |
点空间范围查询 |
Z3 |
点时空范围查询 |
Z2T |
点时空范围查询 |
XZ2 |
非点空间范围查询 |
XZ3 |
非点时空范围查询 |
XZ2T |
非点时空范围查询 |
date |
时间范围查询 |
time_range |
时间段查询 |
id |
id查询 |
attr |
属性查询,属性+时空查询 |
表3支持索引
对象 |
支持时空索引 |
静态点 |
Z2 |
时空点 |
Z2,Z3,Z2T |
静态非点 |
XZ2 |
非点时空 |
XZ2,XZ3,XZ2T |
时间 |
date |
时间段(开始时间,结束时间) |
time_range |
三.
1. 静态类型
现实世界中大量的对象都同时具有时间和空间属性,如果一个对象只具有唯一的空间属性和时间属性,那么我们可以根据基础类型组合出8种时空数据类型。
表4 时空静态
|
点 |
线 |
面 |
网 |
时间点 |
时空静态点 |
时空静态线 |
时空静态面 |
时空静态网 |
时间段 |
时间段静态点 |
时间段静态线 |
时间段静态面 |
时间段静态网 |
样例:
时空静态点:具有空间点和时间点的数据,如:空气质量站点和其修建时间。
时空静态线:具有空间线和时间点的数据,如:道路和其修建时间。
时空静态面:具有空间面和时间点的数据,如:行政区域和其边界确定时间。
时空静态网:具有空间网和时间点的数据,如:路网和其修建完成时间。
时空段静态点:具有空间点和时间段的数据,如:加油站在下午1点至2点售出加油量。
时空段静态线:具有空间线和时间段的数据,如:某条道路在早高峰(早上8:00-早上10:00)的车流量。
时空段静态面:具有空间面和时间段的数据,如:北京大兴区早高峰人口流入总数。
时空段静态网:具有空间网和时间段的数据,如:早高峰北京路况。
2. 动态类型
还存在一些对象,它们的属性可能会动态变化,因此,根据空间或者时间上的变化,我们又可以组合出16种数据类型。
表5 空间不变,读数随着时间变化
|
点 |
线 |
面 |
网 |
时间点 |
空间静态时间动态点 |
空间静态时间动态线 |
空间静态时间动态面 |
空间静态时间动态网 |
时间段 |
空间静态时间段动态点 |
空间静态时间段动态线 |
空间静态时间段动态面 |
空间静态时间段动态网 |
样例:
空间静态时间动态点:不断产生读数的空间质量站点。空气质量站点的空间位置固定,但它会动态地在不同时刻产生读数。
空间静态时间动态线:道路经过的机动车。道路位置固定,但行驶在道路上的车会动态变化。
空间静态时间动态面:区域人流量。区域固定,但里面的人流量会动态变化。
空间静态时间动态网:城市动态路况。城市路网固定,但交通路况会动态变化。
空间静态时间段动态点:智能红绿灯指示信息。红绿灯空间位置固定,但它在不同时间段颜色不一样。
空间静态时间段动态线:道路车流量。道路位置固定,道路车流量不同时间段不一样。
空间静态时间段动态面:区域人流量。区域固定,但不同时间段的人流量会动态变化。
空间静态时间段动态网:城市路况。城市路网固定,但不同时间段的交通路况会动态变化,如早高峰。
表6 空间会随着时间的变化而变化
|
点 |
线 |
面 |
网 |
时间点 |
时空动态点 |
时空动态线 |
时空动态面 |
时空动态网 |
时间段 |
时间段动态点 |
时间段动态线 |
时间段动态面 |
时间段动态网 |
样例:
时空动态点:GPS点。出租车产生的GPS报点,时间在变化,位置也随着变化。
时空动态线:最短路径或轨迹追踪。不同时刻,由于交通路径、天气、事故等,从A地到B地的最优路径可能在不同时刻不一样;出租车最近两分钟的行驶路线,时间在变化,行驶过的路线也随着变化。
时空动态面:火灾蔓延。火势蔓延,时间在变化,火势覆盖面积也会发生变化。
时空动态网:人口迁移网。人口迁移的地点可能会随着时间的变化而变化,进而可能会产生动态的网。
时间段动态点:停留点。停留的地点在发生变化,并且需要记录进入和离开停留点的时间。
时间段动态线:轨迹段。分段后的轨迹,每条轨迹段都具有线特性,并且都有开始和结束时间。
时间段动态面:驻留区域。驻留的地点在发生变化,并且需要记录进入和离开停留点的时间。
时间段动态网:铁路运行图。不同时间段的铁路运行图不同。
四. JUST插件类型
为了方便用户创建复杂的时空对象,JUST为用户提供了9大常用时空类型和三种特定业务类型,并默认指定了合适的索引。
表7 九大常用时空类型
时空类型 |
插件表 |
默认索引 |
时空静态点 |
SSPoint |
z2,z2t,attr(attr+z3),id |
时空静态线 |
SSLine |
xz2,xz2t, attr(attr+xz3),id |
时空静态面 |
SSRegion |
xz2,xz2t,attr, attr(attr+xz3),id |
空间静态时间动态点 |
SDPoint |
z2,z2t,attr(attr+z3),id |
空间静态时间动态线 |
SDLine |
xz2,xz2t, attr(attr+xz3),id |
空间静态时间动态面 |
SDRegion |
xz2,xz2t,attr, attr(attr+xz3),id |
时空动态点 |
SSPoint |
z2,z2t,attr(attr+z3),id |
时空动态线 |
SSLine |
xz2,xz2t, attr(attr+xz3),id |
时空动态面 |
SSRegion |
xz2,xz2t,attr, attr(attr+xz3),id |
表8 三种特定类型
特定场景 |
时空类型 |
插件名 |
默认索引 |
轨迹 |
时间段动态线 |
Trajectory |
xz2,xz2t,attr(time_range),id |
路网 |
时空静态网 |
RoadNetwork |
xz2,xz2t,attr(xz3),id |
地图匹配后的轨迹 |
时间段动态线 |
RouteOfTrajectory |
xz2,xz2t,attr(time_range),id |
五. 使用指南
JUST会根据数据集包含的对象类型,默认创建所有索引,如时空点表将创建Z2、Z3、Z2T三种索引。但是,索引表会占用磁盘空间,而且有些应用场景可能不需要某些查询功能。另外,在某些应用场景中,可能需要创建默认索引类型以外的索引。因此JUST可通过userdata指定需要的索引。注意,如果表中出现多个空间或者时间字段,默认使用建表语句中的第一个空间和时间字段建立索引。
1. 创建默认空间表
create table [表名](
[字段名] [空间类型],
…
)
例子:
create table point(
p
Point
)
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字段名] [类型]:primary
key,
…
)
注:如果在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(
a
string:index=true,
geo Point,
time Date
) userdata {
"geomesa.indices.enabled":"attr",
"geomesa.attr.type":"z2"
}
给属性a建立属性+点时空索引(z2t)
create table attr_st_table(
a
string:index=true,
geo Point,
time Date
) userdata {
"geomesa.indices.enabled":"attr",
"geomesa.attr.type":"z2t"
}
给属性a建立属性+非点空间索引(xz2)
create table attr_npoint_table(
a
string:index=true,
geo Polygon,
time Date
) userdata {
"geomesa.indices.enabled":"attr",
"geomesa.attr.type":"xz2"
}
给属性a建立属性+非点时空索引(xz2t)
create table attr_nst_table(
a string:index=true,
geo Polygon,
time Date
) userdata {
"geomesa.indices.enabled":"attr",
"geomesa.attr.type":"xz2t"
}
给属性a建立属性+时间段索引(time_range)
create table attr_timerange_table(
a
string:index=true,
ts
Date,
te
Date
) 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
Ø 默认字段:id
String, oid String, geom Point/Polygon/LineString;
Ø 自定义字段:
meta属性:表示静态空间对象的附加信息, 如LineString的长度;
reading属性(可选):表示表示空间对象的每个点的数据信息,如LineString的每个点的属性;
Ø 示例:
create sspoint_table as sspoint (meta1
String, meta2 Double)
Ø 注意:在创建表的时候最多两个括号,第一个括号里面是自定义meta字段,第二个括号里面是自定义reading字段;如果只有一个括号则认为是meta自定义字段,如果没有括号则认为没有用户自定义字段。SSPoint插件类型没有reading属性。
时空动态插件类型(DD):DDPoint/DDRegion/DDLine
Ø 默认字段:id
String, oid String, geom Point/Polygon/LineString, time Timestamp;
Ø 自定义字段:
mete属性:表示整个空间对象随时间变化的读数信息。
reading属性(可选):表示空间对象的每个点上的读数信息。
Ø 示例 1:
create ddline_table as ddline (length
Double) (point_deriction Double)
Ø 示例2:
create ddregion_table as ddregion (area
Double, 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"}]
Ø 默认字段:id
String, oid String, geom Point/Polygon/LineString, time Timestamp;
Ø 自定义字段:
mete表示空间对象不随时间变化的信息;
reading表示空间对象随时间变化的读数信息;
Ø 示例:
create sdregion_table as sdregion (meta1
String, 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字段:startid
Integer, endid Integer, direction Integer, maxlanes Integer, level Integer,
speedlimit Double, road_length Double
Ø 用户还可以继续扩展meta字段。
Ø 示例:
create roadnetwork_table as RoadNetwork (weight
Double, name String)
注意:在创建表时最多能有一个括号来扩展meta字段。
轨迹插件类型(Trajectory)
Ø 自定义meta字段如下:endtime
Timestamp, tid String, timeseries TimeSeries, startposition Point, endposition
Point, point_number Integer, length Double, speed Double, signature Bytes
Ø 用户还可以继续扩展meta字段,比如区分是出租车轨迹还是行人轨迹,并且可以扩展自定义reading字段用来表示每个轨迹点的瞬时速度、方向、是否载客等信息。
Ø 示例:
create trajectory_table as Trajectory (trajectorytype
Integer) (direction Double)
注意:在创建表的时候最多两个括号,第一个括号里面是自定义meta字段,第二个括号里面是自定义reading字段;如果只有一个括号则认为是meta自定义字段,如果没有括号则认为没有用户自定义字段。
RouteOfTrajectory插件类型(RouteOfTrajectory)
Ø 自定义meta字段如下:endtime
Timestamp, startposition Point, end_position Point, tid String, routes
Array[RouteInTrajectory]
Ø 用户还可以继续扩展自定义meta字段,比如routeoftrajectory的长度、平均速度。
Ø 示例:
create route_of_trajectory_table as RouteOfTrajectory
(length Double, avg_speed Double)
注意:在创建表时最多能有一个括号来扩展meta字段。
六. 查询需求
1. Range
Query
(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
p
within st_makeBBox(110.0, 30.0, 110.7, 30.8)
(3)时空范围查询
select
*
from
non_point_time
where
poly
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')
(4)时间段范围查询
select
*
from
time_range_table
where
time_range between to_timestamp('2020-11-12 00:00:00') and
to_timestamp('2020-11-13 00:00:00')
或
st_ecql("time_range during
2020-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 during 2020-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 urban
spatio-temporal data engine." 2020 IEEE 36th International
Conference on Data Engineering (ICDE). IEEE, 2020.