SAFE: Sampling-Assisted Fast Learned Cardinality Estimation for Dynamic Spatial Data

Cardinality estimation for spatial queries plays an important role in query scheduling and optimization. Spatial datasets are fully dynamic, and this setting necessitates an update-friendly, low-latency, and accurate cardinality estimator. However, existing cardinality estimation methods suffer from time-consuming updates and/or inefficient estimation. This work proposes SAFE (Sampling-Assisted Fast learned cardinality Estimator), which is carefully designed for dynamic spatial data. We specifically develop a sampling strategy that uses a quad-tree-based data partitioning and extracts a small subset, to enable fast training of cardinality estimation models. In addition, we employ 2-tier regression models to approximate the spatial data distribution while achieving accurate and fast cardinality estimation. We furthermore provide an incremental model update strategy to avoid re-training all models from scratch when we receive updates. We conduct experiments on real and synthetic datasets. Their results demonstrate that SAFE (i) outperforms state-of-the-art cardinality estimation models and (ii) efficiently handles data updates while ensuring accurate and low-latency estimation.