Z-ordered Range Refinement for Multi-dimensional Range Queries

Kento Sugiura, Yoshiharu IshikawaarXiv 2023 · DOI · arXiv

Abstract

Multi-dimensional range queries are essential for modern data applications but face indexing challenges. Z-order curves map multi-dimensional data to a single dimension, enabling the use of standard 1D indices. However, converting multi-dimensional query boxes into 1D ranges often includes significant "wasteful regions." This paper proposes a lightweight, pluggable refinement method combining a novel "jump-out" algorithm with a surface-area-based approximation strategy. Evaluation on synthetic datasets shows that this approach caps refinement overhead and significantly improves query efficiency compared to traditional spatial indices.

Introduction

Multi-dimensional data is ubiquitous, yet indexing it efficiently remains a challenge. A popular technique is the Z-order curve (or Morton order), which maps multi-dimensional coordinates onto a single dimension. This mapping allows developers to leverage highly optimized 1D data structures, such as B-trees or Key-Value stores, to handle complex spatial and temporal queries.

Z-order curve mapping 2D coordinates to a 1D sequence.

Despite its utility, Z-order curves are "leaky." When a multi-dimensional query box is converted into Z-values, the resulting 1D ranges often encompass "wasteful regions"—data points that reside within the 1D range but fall outside the actual query boundaries. To maintain performance, these ranges must be refined into precise sub-ranges. However, calculating these sub-ranges is computationally intensive, particularly as dimensionality increases, often becoming a bottleneck in systems like Amazon DynamoDB.

Proposed Methods

The authors introduce a two-pronged approach to accelerate the refinement process:

1. The Jump-out Algorithm

While traditional "jump-in" algorithms identify the next valid starting point within a query region, the proposed "jump-out" algorithm quickly determines the next endpoint where the Z-curve exits the region. By utilizing both, the system can "leapfrog" over both the query interior and wasteful external regions, avoiding bit-by-bit scanning.

2. Z-ordered Range Approximation

Calculating a perfect set of sub-ranges is slow for high-dimensional data. The authors suggest an approximation strategy that slightly expands the query region. They employ a cost function based on the "surface area" of the hyper-rectangle to decide which ranges to expand. This trade-off allows for minor wasteful regions in exchange for a significant reduction in range calculation time.

Refinement and sub-range identification within a Z-order grid.

3. Pluggable Implementation

The method was implemented using PL/pgSQL in PostgreSQL. This demonstrates its "pluggable" nature, allowing it to be integrated into existing database systems without modifying core source code.

Evaluation

The researchers evaluated their approach using synthetic datasets comprising 10 million tuples across two to six dimensions. Values were randomly assigned within a range of [-512, 512]. Benchmarks included standard PostgreSQL/PostGIS indices such as independent column indices, multi-column indices, and spatial indices like GiST and SPGiST.

Key Results

  • Refinement Speed: The approximation method capped refinement time at approximately 10ms, regardless of dimensionality. In contrast, exact refinement methods experienced exponential growth in execution time as dimensions increased.
  • Efficiency: While approximation includes some wasteful tuples, it still suppresses the vast majority. The proposed method reduced extracted tuples by several orders of magnitude compared to unrefined Z-ranges.
  • Competitive Performance: For low-selectivity queries, the Z-order approach outperformed or matched traditional multi-column and spatial indices.

Discussion and Insights

A critical insight from this work is that for high-dimensional data, the time spent calculating query ranges can exceed the time spent executing the query. The authors observed that the number of "jumps" required for refinement is proportional to the surface area of the query's hyper-rectangle. By expanding ranges along dimensions with the largest surface area, they drastically reduce computational overhead.

Limitations and Future Work

The approximation method's performance can degrade for high-selectivity queries (covering large data portions) as wasteful regions grow. Additionally, the cost function threshold was determined empirically and may require tuning for different environments. Future research will explore parallelization and testing on massive-scale key-value stores like RocksDB.

Summary updated

Abstract

The z-order curve is a space-filling curve and is now attracting the interest of developers because of its simple and useful features. In the case of key-value stores, because the z-order curve achieves multi-dimensional range queries in one-dimensional z-ordered space, its use has been proposed for both academic and industrial purposes. However, z-ordered range queries suffer from wasteful query regions due to the properties of the z-order curve. Although previous studies have proposed refining z-ordered ranges, doing so is computationally expensive. In this paper, we propose z-ordered range refinement based on jump-in/out algorithms, and then we approximate z-ordered query regions to achieve efficient range refinement. Because the proposed method is lightweight and pluggable, it can be applied to various databases. We implemented our approach using PL/pgSQL in PostgreSQL and evaluated the performance of range refinement and multi-dimensional range queries. The experimental results demonstrate the effectiveness and efficiency of the proposed method.
BibTeX
@misc{sugiura2023z,
  author = {Kento Sugiura and Yoshiharu Ishikawa},
  title = {{Z-ordered Range Refinement for Multi-dimensional Range Queries}},
  year = {2023},
  eprint = {2305.12732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.12732},
}
Figure