ClickHouse H3缓冲区查询

背景

    缓冲区查询是非常常见的空间查询，用来查询周边的信息。本文介绍了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

参考资料：

https://www.biaodianfu.com/uber-h3.html

https://github.com/uber/h3-js#module_h3.h3Distance

https://zhuanlan.zhihu.com/p/60861179