LSQL特性 | 基于Morton的地理位置检索

2022-06-01 00:00:00 数据算法匹配经纬度标识

地理位置检索服务在日常生活中随处可见，小到共享单车、高德地图，大到飞行航线轨迹。上述服务中很多相关功能都可以通过GeoHash来实现，Lucene/Solr中也有应用到GeoHash，通过GeoHash创建索引、查询索引以及距离的计算等等。

GeoHash编码

Lucene内部sandbox包支持地理位置检索，默认实现可以支持方形，圆形和多边形的地理位置检索。

GeoHash算法本质上是空间索引的一种方式。我们可以将整个地球设想为一个二维平面，将地球上所有区域展开平铺之后通过递归分解将该平面切分为32个模块。之后再将其中的模块再进行分块，随着范围不断缩小，位置精度也越来越高。每个分块都由一定的标识来表示该块。而地球上所有经纬度坐标都会通过GeoHash算法转变为一个的base32标识，该标识对应上述分块的标识，一层一层的确定分块位置，终便可通过标识找到具体的地理位置。

首先贴出base32编码表：

对于给定的一组经纬度数据（116.389550， 39.928167），使用二分法无限逼近。对纬度39.928167进行编码：

1）区间[-90,0),[0,90]，39.928167在右区间内，取1；

2）区间 [0,45),[45,90]，39.928167在左区间内，取0；

3）区间 [0,22.5),[22.5,45]，39.928167在右区间内，取1；

4）不断递归进行二分拆解，慢慢缩小范围（多缩小13次）...

5）终纬度编码为1 1 0 1 0 0 1 0 1 1 0 0 0 1 0；

对经度116.389550做上述操作，可得经度编码1 0 1 1 1 0 0 0 1 1 0 0 0 1 1。

得到经纬度的二进制位后需要对其进行合并。奇数位取纬度，偶数位取经度，每次取其二进制位的一位（不足为取0），终合并成一个新的二进制串：

11100 11101 00100 01111 0000 01101

每5位为一个10进制数，换算过来为28、29、4、15，0，13。通过换算过来的5个十进制数便可对照上面的base32表得到该经纬度对应的encode标识：wx4g0e。将标识编码转换为经纬度的decode算法与之相反。

经过以上过程，便可将一长串经纬度数据简化为一段短小的url标识——wx4g0e。

在得到标识之后，便可以只通过标识在地图上寻找对应的具体位置了。首先现在已分好的板块中找到W。找到W块后，再将W块进行分块，从子块之中找到X块。随后继续将X块细分，从X块的子块中找到4块。以此类推...随着不断地细分，直至找到wx4g0e对应的子块。

在该子块对应的区域内，即一定的经纬度范围内，他们的标识相同。也就是说，每一个字符串标识，都代表了而某一矩形区域。在这个矩形区域内的所有点，都共享GeoHash字符串标识，这样既可以保护隐私，又容易做缓存。

GeoHash优势

GeoHash因为是字符串查询，本身是比较耗时的。但当其做了索引之后，其查询速度是快于普通查询的，尤其是当第二次命中时查询速度比普通查询二次命中会更快。原因也很简单：单列索引、单列命中显然是高于多列的。GeoHash查询出来的仅仅是某个范围内的数据，需要对返回的数据在进行距离运算，排序后近的便是。其优化效率主要体现在范围查询上。

由上述分析可知，GeoHash是相当有用且高效的一个算法，这个算法通过无穷的细分，能确保将每一个小块的geohash值确保在一定的范围之内，这样就为灵活的周边查找和范围查找提供了可能。

GeoHash缺陷

GeoHash算法也存在一定的缺陷。由于GeoHash算法采用的是Peano空间填充曲线，虽然能够将将二维空间转换成一维曲线，但Peano空间填充曲线大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。虽然geo确实尽可能的将位置相近的点hash到了一起，可是这并不是严格意义上的(实际上也并不可能，因为毕竟多一维坐标)，例如在图中的红点虽然和上方的白点离的很近，可是它们的geohash值一定有差别，因为他们所属子块并不同；虽然在视野上红点和黑点离的很远，但他们因为同属一个子块，事实上geohash值相同。很多时候我们对geohash的值进行简单的排序比较，结果貌似真的能够找出相近的点，并且似乎还是按照距离的远近排列的，可是实际上会有一些点被漏掉了。

Morton码替代

眼下有一替代方案——morton码（莫顿码）代替GeoHash。针对现有剖分模型的不足，有效避免了传统经纬度格网模型在高纬度地区的形状退化和正多面体格网模型的面片形状不规则问题。通过morton码，实现了面片编码与传统地理坐标之间的转换和邻接关系的计算，弥补了上述GeoHash算法中因地球不规则性和纬度变化带来的缺陷。

Morton码可以将多维数据转化为一维数据编码，根据一维编码位数可确定多维数据保留精度，是一种比较常用的压缩编码方法，尤其是作为哈希表的映射算法等，加速了树结构数据的存储和访问速度。

Morton编码也叫z-order code ，因为其编码顺序按照空间z序，编码结果展现为一种Z形的填充曲线。

lucene在实现地理位置检索上的缺点

由于morton码仅能用来表达一个方形的区域，而lucene在实现圆形，多边形地理位置检索的时候是先基于morton筛选出一个大致的范围，然后对筛选出来的每一条记录进行二次验证与剪切，以达到匹配的目的。

目前lucene的二次验证采用的是DocValues实现，DocValues字段是一个面向列存储的字段，DocValues是在Lucene4.0引入的新特性，属于正向索引。它存储文档编号到字段值正向关系的索引。

基于DocValues实现二次验证和剪切存在较多的随机IO，如果命中的记录条数很多，会导致整体地理位置检索性能非常的差。

改进方法

原先采用docvalues或正排数据进行地理位置（如圆形，多边形）的二次校验，也即原先进行地理位置（如圆形，多边形）的二次校验读取的数据分布在磁盘的不同位置，不连续。如下图所示：

更改为将相同的地理位置的数据存储存储在一起，通过构造连续数据，减少随机读取的次数：

使用方法

基本使用

1. 创建实例

能支持geo查询的数据类型必须为y_geopoint_idmp。

create table geo_example(id y_string_id,geoname y_string_id,geodata y_geopoint_idmp);

2. 导入数据

(1) 数据样例

1) 每条数据一个点：

{"tablename":"geo_example","partition":"test","id":1,"geoname":"102.72242222037083,28.88523027458959 ","geodata":"102.72242222037083,28.88523027458959 "}

2) 每条数据2个点，每个点之间以空格隔开，当然写成json数组也可以：

{"tablename":"geo_example","partition":"test","id":1,"geoname":"102.72242222037083,28.88523027458959  103.72242222037083,29.88523027458959 ","geodata":"102.72242222037083,28.88523027458959  103.72242222037083,29.88523027458959 "}

(2) 导入测试数据

sh load.sh -t geo_example -p test1 -tp json -local -f /wyh/test.json

(3) 全表扫描

3. 筛选方法

(1) 圆形区域匹配

查询语句如下：

select count(*) from geo_example where partition like '%'  and SYS_JSON_QUERY@{            query_type:"geo"            ,geo_type:"circle"            ,field:"geodata"            ,list:["99.71,29.38"]            ,radius:1000        }@SYS_JSON_QUERY  limit 20;

查询结果如下图所示（查询半径不同，匹配到的结果数不同）：

(2) 方形区域匹配

查询语句如下：

select count(*) from geo_example where partition like '%'  and SYS_JSON_QUERY@{            query_type:"geo"            ,geo_type:"box"            ,field:"geodata"            ,list:["99.71,29.38"]            ,radius:10000        }@SYS_JSON_QUERY  limit 20;

查询结果如下图所示（查询半径不同，匹配到的结果数不同）：

(3) 多边形区域匹配

查询语句如下（至少4个点，且因多边形要求闭合，个与后一个点必须相同）：

select count(*) from geo_example where partition like '%'  and SYS_JSON_QUERY@{            query_type:"geo"            ,geo_type:"polygon"            ,field:"geodata"            ,list:["105.39,45.40","99.50,29.20","110.50,29.20","105.39,45.40"]        }@SYS_JSON_QUERY  limit 20;

查询结果如下图所示：

(4) Geohash网格汇聚

查询语句如下：

select geohash_s,count(*) as cnt from geo_example where partition like '%'  and SYS_GEO_QUERY@{            field:"geodata"            ,minLon:"99.50"            ,minLat:"29.20"            ,maxLon:"110.50"            ,maxLat:"45.40"             ,precision:4        }@SYS_GEO_QUERY group by geohash_s order by cnt desc limit 20;

查询结果如下图所示：

相似轨迹匹配

1. 匹配算法

Lsql的默认打分机制是根据TF/IDF算法，即词频算法。

TF：分词项在文档中出现的次数（term frequency）。
IDF：代表分词项在多少个文档中出现（inverse document frequency）。

但在进行轨迹匹配时需要按照匹配的条件个数排序，匹配个数多的排在前面。

2. 创建实例

create table geo_match(id y_string_id,geoname y_string_id,geodata y_geopoint_idmp);

3. 导入数据

测试数据如下所示（标红为几条轨迹数据的不同之处）：

{"tablename":"geo_match","partition":"test","id":1,"geoname":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 99.72242222037083,28.88523027458959 ","geodata@geo5000":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 99.72242222037083,28.88523027458959 "}{"tablename":"geo_match","partition":"test","id":2,"geoname":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 ","geodata@geo5000":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 "}{"tablename":"geo_match","partition":"test","id":3,"geoname":"102.72242222037083,28.88523027458959 120.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 ","geodata@geo5000":"102.72242222037083,28.88523027458959 120.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 "}{"tablename":"geo_match","partition":"test","id":4,"geoname":"100.72242222037083,28.88523027458959 130.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 ","geodata@geo5000":"100.72242222037083,28.88523027458959 130.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 "}

./load.sh -t geo_match -p test -tp json  -local -f /wyh/testMatch.json

导入数据后全表查询结果如下：

select * from geo_match  where partition like '%' limit 10;

4. 轨迹匹配检索

(1) 描点

轨迹匹配，需要对导入的两个经纬度之间，进行描点，以体现出轨迹匹配，lsql默认在两个经纬度点之间从两头向中间多描100个点。

注意：描完点后的经纬度的值，会很多，膨胀率较高，一般仅用于轨迹匹配，不要做其他用途。另外描点距离越近，精度越高，但膨胀率越高。

上面导入的经纬度数据是不能进行描点的。如果要进行描点，需要导入数据的时候在列名字上做特殊处理。

kafka导入

原先

{'table':'geo_match','partition':'default','id':'1','geoname':'test','geodata':'100.72242222037083,28.88523027458959 130.40751616748125,31.369586323194188 90.71391535438913,29.393961382032614'}

按照5000米描点的写法

{'table':'geo_match','partition':'default','id':'1','geoname':'test','geodata@geo5000':'100.72242222037083,28.88523027458959 130.40751616748125,31.369586323194188 90.71391535438913,29.393961382032614'}

离线导入

json写法与上述kafka导入类型，不再细述。

分隔符方式的导入以@分隔符为例

原先写法：

./load.sh -t geo_match -p default -tp txt -fl id,geoname,geodata -f /load /1.log -sp @

按照5000米描点写法：

./load.sh -t geo_match -p default -tp txt -fl id,geoname,geodata@geo5000 -f /load/1.log -sp 0x09

(2) 普通排序语法

radius为匹配半径，meters为描点距离，radius通常来说大于等于meters
percent:表示小匹配的点数，小于该值的记录不会被检索出来

select * from geo_match where partition like '%' and          SYS_JSON_QUERY@{            query_type:"geo"            ,geo_type:"track"            ,field:"geodata"            ,list:["100.72242222037083,28.88523027458959","130.72242222037083,28.88523027458959","90.72242222037083,28.88523027458959"]            ,radius:10000            ,meters:5000            ,percent:20        }@SYS_JSON_QUERY  limit 20;

查询结果如下图所示：

(3) 按匹配条件个数排序语法

select id, geoname,geodata, cl_score_y_double_d  from geo_match where partition like '%' and  SYS_SCORE_QUERY@        SYS_JSON_QUERY@{            query_type:"geo"            ,geo_type:"track"            ,field:"geodata"            ,list:["100.72242222037083,28.88523027458959","130.72242222037083,28.88523027458959","90.72242222037083,28.88523027458959"]            ,radius:10000            ,meters:5000            ,percent:20        }@SYS_JSON_QUERY @SYS_SCORE_QUERYorder by cl_score_y_double_d desc limit 20;

查询结果如下图所示：

记录匹配condition个数越多的得分越高，排名越靠前，会首先返回，而普通排序功能无此效果。

必备函数

CL_GEO_DISTANCE(tmp.geodata,6.1,8.3) as distance  //计算两点之间的距离CL_GEO_UNHASH(tmp.geodata) //用于将morton值解析出经纬度CL_GEO_HASH(lon,lat) //用于将经纬度数据解析成morton值

LSQL不仅在地理位置检索、多值列、多列联合索引上具有亮点，其检索和统计分析服务更能够满足万亿秒查，该方面的性能也是业内的佼佼者。即席查询、模糊检索、Facet统计、列簇存储、异构存储、主从集群、过载保护、权限管理... 只需要一套数据库就可以解决大数据行业内从业人员的无数痛点。

相关文章