ByteHouse技術詳解：基于OLAP構建高性能GIS地理空間能力
在數(shù)字化時代，地理空間分析（Geospatial Analytics）成為輔助企業(yè)市場策略洞察的重要手段。無論是精準廣告投放，還是電商物流的效率優(yōu)化，都離不開對地理空間數(shù)據(jù)的查詢、分析和可視化處理，以便助力企業(yè)更好決策。
以一家連鎖咖啡店為例：
該店想要在新城市開設分店，并希望確保新店鋪的位置能夠最大化利潤。
首先，商家通過收集新城市的地理數(shù)據(jù)，包括人口分布、交通流量等，建立了一個詳細的地理信息數(shù)據(jù)庫。然后，商家利用空間數(shù)據(jù)分析工具，對這些數(shù)據(jù)進行了深入分析。
通過人口分布數(shù)據(jù)，商家發(fā)現(xiàn)新城市的一些區(qū)域人口密集，潛在顧客群體較大。同時，交通流量數(shù)據(jù)顯示，某些區(qū)域的交通流量較大，意味著這些區(qū)域的顧客流動性較高，有利于店鋪的曝光和吸引顧客。
此外，商家還分析了同行情況競爭對手的位置，以避免在已有眾多同類型店鋪的區(qū)域開設分店。空間數(shù)據(jù)分析幫助商家識別了那些既有足夠潛在顧客，又相對較少競爭者的區(qū)域。
基于這些分析結果，商家最終確定了新店鋪的位置。開設分店后，由于選址精準，店鋪迅速吸引了大量顧客，銷售額和利潤均實現(xiàn)了預期目標。
以上案例離不開對地理空間數(shù)據(jù)庫的支持。一些傳統(tǒng)的地理信息系統(tǒng)數(shù)據(jù)庫具備豐富的地理空間對象結構、成熟的空間索引能力，在導航、旅游、智能城市等典型應用場景中被廣泛使用。
但隨著實時分析報表等OLAP市場的擴大，地理空間分析也作為新的增值特性被業(yè)界幾大OLAP主流產品所推廣。OLAP+GIS能力在滿足用戶地理空間數(shù)據(jù)分析的基礎上，還能在數(shù)據(jù)體量大、實效性要求高的情況下，滿足業(yè)務高性能查詢的需求。
作為火山引擎推出的一款OLAP引擎，ByteHouse近期發(fā)布了高性能地理空間分析GIS能力，為位置洞察、人群圈選等場景提供高性能地理數(shù)據(jù)分析服務。本篇內容將從技術實現(xiàn)角度，詳細介紹ByteHouse如何集成GIS能力，并通過benchmark測試，展示ByteHouse與市場同類產品相比（ClickHouse、StarRocks、PostGIS、DuckDB）的性能情況。
應用場景和價值
位置洞察： 例如，在給定中心點的情況下，展示半徑X公里內的圓內其他商家的同一商品的客流分布、經營情況等，有助于幫助商家客戶洞察競爭對手情況，為定價策略和市場定位提供數(shù)據(jù)支持。
作戰(zhàn)地圖： 給定特定多邊形，觀察多邊形內部商家的供給和客流量，為即時零售業(yè)務的配送優(yōu)化提供決策依據(jù)。例如：生活服務的即時零售業(yè)務需要觀察實時的配給。
經過我們對行業(yè)上相關業(yè)務場景的需求分析，商家或者銷售代理等客戶需要的是一種“對某個地理空間（多邊形/圓）內的對象進行多種業(yè)務維度的分析和決策能力”。從整個執(zhí)行鏈路來看，鏈路不僅含GIS的二維空間數(shù)據(jù)篩選，還有經典OLAP的聚合和關聯(lián)分析等邏輯，因此可以總結出一層GIS+OLAP鏈路的抽象。從性能優(yōu)化角度來看，OLAP優(yōu)化器有必要去結合GIS的特性來進行適配，提升端到端的總體性能。
詳細介紹
在關鍵性能層面，ByteHouse GIS在列式小批組織的數(shù)據(jù)結構上引入RTree等二維空間索引能力，并在CPU硬件層面實現(xiàn)了二維空間函數(shù)的性能優(yōu)化，整體提升了端到端性能。在功能層面，兼容OGC標準，支持導入標準GIS文件格式，目前已支持超過50個主流的空間函數(shù)。更值得一提的是，我們還在探索在我們自研的優(yōu)化器上結合GIS特性適配，如在高效的多表關聯(lián)上適配GIS等，以及GPU硬件層面優(yōu)化二維空間函數(shù)。
二維空間索引
回顧業(yè)務場景：給定一個查詢窗口（通常是一個多邊形或圓），返回包含在該查詢窗口中的物體。
如果要提升查詢性能，讀取的數(shù)據(jù)量通常是比較關鍵的，那取決于：
1）數(shù)據(jù)的排序方式 2）數(shù)據(jù)讀取的粒度 3）索引
社區(qū)ClickHouse數(shù)據(jù)組織
ByteHouse 是火山引擎基于開源 ClickHouse 進行了深度優(yōu)化和改造的版本。ClickHouse 社區(qū)版直接按照Order By latitude, longtitude里面的緯度進行排序，再按照經度排序。
因為經度上相距很遠的數(shù)據(jù)可能被放到一個mark，而查詢是一個多邊形和圓，查詢的模式和數(shù)據(jù)的組織不匹配從而造成嚴重的讀放大問題，導致數(shù)據(jù)局部性較弱。
ByteHouse空間索引：Google S2 + R tree
ByteHouse GIS 通過使用Google S2 [3]庫將所有的經緯度點從二維轉換轉換成一維，并排序。排序后的經緯度點效果如下圖：
圖片來源：[3]
由于ByteHouse的數(shù)據(jù)是按照列式存儲，相比于傳統(tǒng)的行級別索引，我們會對S2排序后的經緯度數(shù)據(jù)，先按照小塊粒度切分，再利用RTree來索引每個小塊數(shù)據(jù)。這樣，基于小塊粒度的RTree索引的存儲開銷更小，加載和查詢效率更高。給定一個查詢的多邊形或圓，RTree能快速索引到匹配的數(shù)據(jù)塊。由于每個數(shù)據(jù)塊內的經緯度數(shù)據(jù)是按照二維層面聚集，這樣使得相鄰的點在二維空間上更加緊密，數(shù)據(jù)局部性更好。
ByteHouse GIS索引結構
針對某個具體場景中給出的一個圈選范圍，需要返回范圍內的所有POI (Point of Interest)點。下面兩幅圖分別展示了傳統(tǒng)經緯度排序方式（Order By latitude, longitude）和ByteHouse GIS索引排序方式（Order By point）的圈選效果。其中，圖中黑色的框代表了所有數(shù)據(jù)塊，紅色部分代表了圈選命中的數(shù)據(jù)塊。
從結果中看出，傳統(tǒng)經緯度排序命中的范圍會橫跨很廣的緯度，造成讀取許多無用的數(shù)據(jù)。而按照ByteHouse GIS索引搜索出的數(shù)據(jù)塊只集中在北京地域，正好滿足圈選所需的最小數(shù)據(jù)塊集合。
傳統(tǒng)經緯度排序方式的搜索效果
ByteHouse GIS排序方式的搜索效果
兼容OGC標準
數(shù)據(jù)類型
按照OGC標準，新增7種幾何類型，包括Point、LineString, Polygon, MultiPoint, MultiLineString, MultiPolygon, GeometryCollection。
存儲層面上，傳統(tǒng)GIS數(shù)據(jù)庫（例如，PostGIS）將幾何數(shù)據(jù)序列化為Blob類型，讀取時需要額外花費反序列化的開銷。而ByteHouse GIS則按照數(shù)值數(shù)組和列式方式存儲，減少存儲量、序列化和反序列化開銷。
空間函數(shù)
功能上，ByteHouse GIS目前已支持超過50個通用的空間函數(shù)，下面表格列舉了幾大函數(shù)分類。另外，我們針對個別高頻使用的空間函數(shù)進行了基于列式數(shù)據(jù)存儲格式的性能優(yōu)化。
存量數(shù)據(jù)遷移
同時，ByteHouse GIS也支持常見數(shù)據(jù)格式的導入與導出，包括WKT、WKB、GeoJson、ShapeFile、Parquet、CSV和Arrow等文件格式。
Benchmark 測試
標準NYC Taxi數(shù)據(jù)集
為了說明性能效果，我們基于兩個關鍵的 GIS 函數(shù)，使用 NYC Taxi 數(shù)據(jù)集，選取紐約的 3 個地理區(qū)域，將ByteHouse、ClickHouse、StarRocks、PostGIS、DuckDB進行了性能對比（以上對比的版本參照發(fā)文日期的最新版本）。
在本次測試中，我們選取了兩個關鍵的 GIS 函數(shù)：ST_DistanceSphere 和 ST_Within；并使用 NYC Taxi 數(shù)據(jù)集（Size：21GB；條數(shù)：169,001,162），數(shù)據(jù)集將紐約拆分成多個地理區(qū)域（比如 Brooklyn，Manhattan），本實驗選取其中 3 個不同大小的地理區(qū)域（按照過濾度區(qū)分：zone 1、zone 2、zone 3）進行了性能對比。
- ST_Within 函數(shù)性能對比：在
ST_Within函數(shù)的測試中，從查詢延遲來看，OLAP引擎的整體查詢延時低于1s，由于二維空間索引和向量化的數(shù)據(jù)處理方式，ByteHouse查詢延時最低；當前版本的DuckDB由于沒有空間索引，同時采用了BLOB的存儲方式，數(shù)據(jù)掃描和反序列化開銷比較大，查詢性能不好；采用行存的PostGIS在大范圍搜索的情況下（zone3），雖然有索引加持，依然會有較重的讀放大，查詢延時超過6s。從每秒吞吐量來看，ByteHouse通過索引降低了數(shù)據(jù)讀取和反序列化開銷，展現(xiàn)出明顯優(yōu)勢，其次為PostGIS，在小范圍搜索（zone1和zone2）情況下表現(xiàn)優(yōu)秀。
ST_Within函數(shù)性能對比
ST_Within每秒處理空間查詢數(shù)
- ST_DistanceSphere 函數(shù)性能對比：在
ST_DistanceSphere函數(shù)的測試中，在處理相同數(shù)據(jù)集和查詢時，ByteHouse具備二維空間索引過濾和向量化計算的優(yōu)勢，性能控制在0.1s以內。ClickHouse和StarRocks同樣具備較好的0.1s-1s內的較好性能表現(xiàn)。
ST_DistanceSphere 函數(shù)性能對比
基于標準數(shù)據(jù)集的測試結果來看，對比傳統(tǒng)的PostGIS：
- ByteHouse GIS將OLAP和GIS結合了起來。在OLAP層面，ByteHouse對比PostGIS已經有計算優(yōu)勢。
- 在GIS層面，空間數(shù)據(jù)對象按照列的方式存儲，而非序列化成字節(jié)數(shù)組，在存儲上能夠做到更加緊湊并節(jié)省空間，在計算上能夠充分發(fā)揮向量化的優(yōu)勢。
- 特別是在空間函數(shù)層面，可以利用硬件的并行化能力提速。
對比社區(qū)ClickHouse：
- ByteHouse GIS兼容OGC標準，場景上能夠水平替換之前PostGIS的場景。
- 另外，空間索引能力可以大大減少ClickHouse的讀放大的現(xiàn)象。
- 還有，ByteHouse自研的優(yōu)化器同樣具備適配GIS特性的能力。
業(yè)務數(shù)據(jù)集
在電商場景中，ByteHouse GIS能力不僅滿足平臺商家運營快速分析商家經營狀態(tài)、管理商家的需求，還將數(shù)據(jù)讀取量減少超過50%，進一步降低了磁盤IO以及計算帶來的CPU開銷。
總結
本文具體拆解了ByteHouse GIS能力的技術實現(xiàn)方案，并將ByteHouse、ClickHouse、StarRocks、PostGIS、DuckDB五款數(shù)據(jù)庫產品的性能進行分析和比較。
結論總結如下：ByteHouse在ST_DistanceSphere 函數(shù)及ST_Within 函數(shù)的查詢延遲低于其他產品，查詢吞吐量更高，具備比較明顯的性能優(yōu)勢。
需要注意的是，性能測試結果取決于多個因素，在實際應用中，需要綜合考慮各種因素，如數(shù)據(jù)規(guī)模、可擴展性、易用性、穩(wěn)定性、安全性以及是否需要與其他系統(tǒng)集成等其他因素進行綜合選擇，并對數(shù)據(jù)庫進行合理的配置和優(yōu)化，以獲得最佳的性能表現(xiàn)。
對于專注于地理空間數(shù)據(jù)分析的項目，PostGIS能提供了全面的地理空間功能支持，是一個比較好的選擇。然而，如果地理空間數(shù)據(jù)只是大數(shù)據(jù)分析的一部分，且如果性能是首要考慮因素，那么ByteHouse、ClickHouse、StarRocks、DuckDB是合適的選擇，其中ByteHouse GIS 功能不僅提供了高性能的地理空間分析能力，還具有易于使用、實時分析和云原生等特點，這使得企業(yè)可以更靈活、更高效地利用地理空間數(shù)據(jù)。
參考
- PostGIS: https://postgis.net/
- OGC: https://www.ogc.org/standard/sfs/
- Google S2: https://s2geometry.io/
- Geos: https://libgeos.org/
- https://clickhouse.com/docs/en/sql-reference/functions/geo/coordinates
- Cuda: https://developer.nvidia.com/cuda-toolkit
- https://github.com/rapidsai/cuspatial
- https://github.com/arctern-io/arctern
- https://halfrost.com/go_spatial_search/
