SOLAR: Scalable Distributed Spatial Joins through Learning-based Optimization

Yongyi Liu, Ahmed R. Mahmood, Amr Magdy, Minyao Zhu · 2025

Read SOLAR: Scalable Distributed Spatial Joins through Learning-based Optimization by Yongyi Liu, Ahmed R. Mahmood, Amr Magdy, Minyao Zhu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-01292.txt.

Introduction

Yongyi Liu and co-authors speed up map joins with learning in a 2025 paper. A spatial join pairs objects from two map data sets by their spatial relations, a core but heavy database operation usually spread across a cluster. Existing systems repartition data from scratch for each query, wasting work when similar queries repeat.

Their system, SOLAR, learns offline how past workloads' data sets were split, then checks a new query's similarity to those workloads online. Similar enough work reuses an old partition plan; otherwise it splits fresh. On real data sets the system ran joins up to about three and a half times faster than the best rivals, with partitioning itself nearly three times quicker. Reuse turns repetition into savings.

Catalog record

CREATORYongyi Liu, Ahmed R. Mahmood, Amr Magdy, Minyao Zhu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-01292

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SOLAR: Scalable Distributed Spatial Joins through Learning-based Optimization Yongyi Liu, Ahmed R. Mahmood, Amr Magdy, Minyao Zhu Abstract . The proliferation of location-based services has led to massive spatial data generation. Spatial join is a crucial database operation that identifies pairs of objects from two spatial datasets based on spatial relationships. Due to the intensive computational demands, spatial joins are often executed in a distributed manner across clusters. However, current systems fail to recognize similarities in the partitioning of spatial data, leading to redundant computations and increased overhead. Recently, incorporating machine learning optimizations into database operations has enhanced efficiency in traditional joins by predicting optimal strategies. However, applying these optimizations to spatial joins poses challenges due to the complex nature of spatial relationships and the variability of spatial data. This paper introduces SOLAR , scalable distributed spatial joins through learning-based optimization. SOLAR operates through offline and online phases. In the offline phase, it learns balanced spatial partitioning based on the similarities between datasets in query workloads seen so far. In the online phase, when a new join query is received, SOLAR evaluates the similarity between the datasets in the new query and the already-seen workloads using the trained learning model. Then, it decides to either reuse an existing partitioner, avoiding unnecessary computational overhead, or partition from scratch. Our extensive experimental evaluation on real-world datasets demonstrates that SOLAR achieves up to 3.6X speedup in overall join runtime and 2.71X speedup in partitioning time compared to state-of-the-art systems. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/Yongyi-Liu/SOLAR . 1. Introduction A spatial join, specifically a spatial theta join, is a database operation that identifies pairs of objects from two spatial datasets that satisfy a spatial predicate. This operation is extensively applied in various fields including urban planning ( Wu, 2023 ) , i.e., overlaying demographic data over political district polygons for political districting, public safety ( Wier et al., 2009 ) , i.e., identifying vehicle-pedestrian injury in each census tract by joining the collision data with census tract, and medical imaging ( Wang et al., 2012 ) , i.e., detecting proximate cells. Given the vast amount of spatial data, spatial joins are increasingly processed in distributed computing environments to efficiently manage large-scale spatial data. Motivation: In practice, enterprise customers tend to issue similar queries repeatedly ( Teevan et al., 2007 ; Huang et al., 2024 ; Schmidt et al., 2024 ) . Huang et al. ( Huang et al., 2024 ) point out that Microsoft workloads are highly recurrent. Schmidt et al. ( Schmidt et al., 2024 ) further propose that in Amazon Redshift data warehouse, customer workloads exhibit highly similar query patterns, i.e., users and systems frequently issue the same queries. Similarly, in spatial data systems ( Eldawy and Mokbel, 2015 ; Aji et al., 2013 ; Yu et al., 2019 ; Eldawy et al., 2021 ; Xie et al., 2016 ; Tang et al., 2016 ; Tang et al., 2020 ) , users frequently perform spatial joins involving datasets with similar spatial characteristics. A critical step in executing distributed spatial joins is constructing a balanced partitioner, a data structure used to distribute spatial data fairly across worker nodes. However, this partitioning process incurs substantial computational overhead ( yan, 2020 ) . For instance, partitioning just two terabytes of spatial data can take up to five hours ( Aly et al., 2015 ) . Due to the expensive nature of constructing a partitioner and the repeating query patterns in industry workloads, once an effective spatial partitioner is established, there is no need to recompute it for each occurrence of the same or similar query. However, existing systems ( Eldawy and Mokbel, 2015 ; Aji et al., 2013 ; Yu et al., 2019 ; Eldawy et al., 2021 ; Xie et al., 2016 ; Tang et al., 2016 ; Tang et al., 2020 ) recalculate the partitioner for these frequently executed joins, which results in repeating computations for similar queries. In the meantime, spatial joins often share inherent similarities. For example, the process of joining datasets of parks with restaurants often requires a similar partitioning to those used when joining datasets of parks with cafes, due to spatial correlations between these entities. Additionally, when working with an updated version of a dataset, such as points of interest, new or deleted records may be present. However, the overall distribution is likely to remain unchanged. By recognizing and leveraging these patterns, it is possible to apply a previously determined partitioner to similar joins. In this way, the system can bypass rescanning the input data to gather distribution statistics and skip building a partitioner on-the-fly (repartition). Figure 1 . Example of SOLAR Reusing Existing Partitioners in Executinng Spatial Join Queries Challenges: Optimizing future spatial join workloads by leveraging historical spatial join workloads introduces four challenges. (1) Despite the frequent occurrence of similar queries over identical or spatially similar datasets, there is no standardized metric to quantitatively evaluate the similarity between different spatial joins and their underlying spatial join inputs, i.e., datasets. Identifying accurate similarity metrics between inherently skewed spatial datasets and expensive spatial joins is challenging. (2) Being able to learn the similarity between spatial joins and datasets calls for efficient embeddings of join queries and their corresponding datasets. This is very challenging as these embeddings must be compact for efficient storage, yet comprehensive enough to encapsulate the essential features of the queries and their corresponding inputs. (3) The utilization of historical spatial joins and their underlying spatial properties of join inputs to enhance the processing of new spatial joins adds another layer of complexity. The challenge here is that the system needs to accurately and efficiently match a new spatial join query to a pre-existing spatially similar join or dataset in its history whenever possible. (4) Making an accurate decision for an incoming spatial join that deviates from historical patterns—whether to adapt the partitioner from a historical spatial join workload or execute the new query without using historical information (i.e., repartition spatial join inputs)—is a very challenging problem. The reason is that making a wrong decision about reusing historical information could lead to poor spatial join performance, and avoiding partition reuse when needed will also incur unneeded spatial partitioning overhead. Existing work: Recently, learning-based approaches have been widely used to optimize various operations in database systems. In non-spatial joins, reinforcement learning has been used to determine the optimal join orders of multiple tables ( Krishnan et al., 2018 ; Marcus and Papaemmanouil, 2018 ; Yu et al., 2020 ; Yan et al., 2023 ; Chen et al., 2022 ) . In spatial joins, reinforcement learning has been used to find an optimal partitioner ( Hori et al., 2023 ) , and traditional

Read the complete text