ClickHouse H3缓冲区查询
2021-01-21 本文已影响0人
polong
背景
缓冲区查询是非常常见的空间查询，用来查询周边的信息。本文介绍了H3来进行缓冲区查询的方案。
H3简介
H3是由Uber开源的一个六边形分层索引网格系统，也是最近几年实现数据聚合的主要趋势，在H3出现之前大部分情况采用的是Geohash算法，墨卡托投影，还有一些其他投影技术，比如Google S2地理索引。
在不同纬度的地区使用等面积、等形状的六边形地理单元可以减少指标和特征归一化的成本。另一方面，在常用的地理范围查询中，基于矩形的查询方法，存在 8 邻域到中心网格的距离不相等的问题，四边形存在两类长度不等的距离，而六边形的周围邻居到中心网格的距离却是有且仅有一个，从形状上来说更加接近于圆形。
具体思路步骤
创建表按H3来分区，分区不超过一千个最好
CREATE TABLE pntsh3 ( ) ENGINE = MergeTree() PARTITION BY (geoh3) order by (geoh3,Lon,Lat) AS select id,geoToH3( toFloat64(Lon), toFloat64(Lat),3) geoh3,toFloat64(Lon) Lon, toFloat64(Lat) Lat from pnts
image
计算需要缓冲区范围内几个该级别下几个格子可以覆盖ceil(200000/h3EdgeLengthM(3)/2+1, 0))，得到H3集合。计算公式大概就是用距离处理六边形两边和再加上一个一边长，结果向上取整
select Lon, Lat,id from pntsh3 where geoh3 in (select arrayJoin(h3kRing(geoToH3(-120.419219,34.889755999999998, 3), toInt64(ceil(200000/h3EdgeLengthM(3)/2+1, 0))))) and greatCircleDistance(Lon,Lat,-120.419219,34.889755999999998) <=200000
image
select Lon, Lat,id from pntsh3 where geoh3 in (select arrayJoin(h3kRing(geoToH3(-120.419219,34.889755999999998, 3), toInt64(ceil(200/h3EdgeLengthM(3)/2+1, 0))))) and greatCircleDistance(Lon,Lat,-120.419219,34.889755999999998) <=200
image
相对于暴力计算，无论缓冲区大小均有一定提升
select Lon, Lat,id from pntsh3 where greatCircleDistance(Lon,Lat,-120.419219,34.889755999999998) <=200000
image
select Lon, Lat,id from pntsh3 where greatCircleDistance(Lon,Lat,-120.419219,34.889755999999998) <=200
image
通过H3索引的合理使用，有效减少了全表扫描，提升查询速度
参考资料：
https://www.biaodianfu.com/uber-h3.html
https://github.com/uber/h3-js#module_h3.h3Distance
https://zhuanlan.zhihu.com/p/60861179
