20190803_03.md

PostgreSQL PostGIS 3 - 从min(x) 到 z-order 到 Hilbert Geometry Sorting - PostGIS空间排序算法优化

作者

digoal

日期

2019-08-03

标签

PostgreSQL , PostGIS , 空间排序 , 算法 , minx , Morton curve , Hilbert curve , 空间紧凑排序

---

背景

PostGIS 是专业的空间插件，空间数据最常见的空间排序是怎么做的呢？

1、2.4以前，空间排序使用的是x轴的最小值，算法粗糙。

2、2.4开始引入了Z-order curve (Morton curve)排序算法，

https://en.wikipedia.org/wiki/Z-order_curve

3、3 开始，使用Hilbert curve代替了Z-order curve。

https://en.wikipedia.org/wiki/Hilbert_curve

例子

1、创建离散点，如图

CREATE SEQUENCE points_seq;   
  
CREATE TABLE points AS   
SELECT (ST_Dump  
  ( ST_GeneratePoints(   
     ST_MakeEnvelope(-10000,-10000,10000,10000,3857),   
     10000)   
    )).geom AS geom,   
 nextval('points_seq') AS pk;  

2、使用min(x轴)排序，聚合成线段，如图，可以清晰的看到排序后的线段是这些离散点根据min(x轴)的值顺序描绘出来的

SELECT ST_MakeLine(geom ORDER BY ST_X(geom)) AS geom   
FROM points;  

3、使用Z-order_curve算法排序（使用PostGIS 2.5的版本排序即可），聚合成线段，如图，可以看到Z象限的顺序

SELECT ST_MakeLine(geom ORDER BY geom) AS geom   
FROM points;  

4、使用Hilbert_curve（使用PostGIS 3排序），聚合成线段，如图，可以看到顺序和hilbert wiki描述一致

SELECT ST_MakeLine(geom ORDER BY geom) AS geom   
FROM points;  

参考

https://info.crunchydata.com/blog/waiting-for-postgis-3-hilbert-geometry-sorting

https://en.wikipedia.org/wiki/Z-order_curve

https://en.wikipedia.org/wiki/Hilbert_curve

PostgreSQL 许愿链接

您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.

9.9元购买3个月阿里云RDS PostgreSQL实例

PostgreSQL 解决方案集合

德哥 / digoal's github - 公益是一辈子的事.