In database management systems (DBMSs) and data processing platforms, query optimization involves two main steps: logical transformation and cost estimation. Modern DBMSs and data processing platforms can process heterogeneous data. Each type of data requires specific considerations in its query optimization process. However, the main steps of query optimizations are always the same, regardless of the type of data being processed. The query optimizer returns a query plan with the lowest cost. A query plan is represented by a set of operators that form a query tree. The query transformer maps a query tree into equivalent query trees by following a set of rules inherited from relational algebra. The query optimizer evaluates the overall cost of each candidate plan to determine the optimal plan. The cost function considers access cost, storage cost, computation cost, and communication cost [31]. To estimate the computation cost, the query estimators compute the selectivity and cardinality through data statistics. The data statistics are extracted and compacted into data synopses, such as histograms, samples, sketches, and wavelets [9]. The I/O costs of 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 info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 17, No. 12 ISSN 2150-8097. doi:10.14778/3685800.3685846 the query execution are affected by data storage, such as partitioning and indexing. Over the past decades, extensive efforts have been made to incorporate different query optimization tasks and various query operation requirements.
AI4DB [18] becomes a very hot direction in the database community. Researchers spend efforts to improve query optimization by Artificial Intelligence (AI) techniques. Learned query optimizers beat the traditional heuristic solutions on generating more efficient query plans among the large search space [8,21,23,40,44,49,50]. Traditional synopses-based estimators rely on the Attribute Value Independence (AVI) assumption and cannot capture the attribute correlations [11,32]. To overcome this limitation, researchers propose learned-based estimators including data-driven and querydriven models. The data-driven models [2,17,26,30,34,36,41,42,46,52] learn the joint data distribution over all attributes. The query-driven models [16,20,25,28,38,41,48] learn a mapping function from queries to the corresponding cardinalities.
Existing learned-based query optimization techniques for highdimensional data cannot be directly applied to spatial data because the spatial query operators are more complicated than highdimensional vector data. Spatial data includes raster and vector formats. Raster data is represented by a grid of regularly sized pixels, while vector data uses geometry, such as points, linestrings, and polygons, defined by a set of numerical values. Due to the complexity of spatial attributes, expressing a spatial query in SQL often requires multiple inequality predicates in the WHERE clause. The classification of spatial queries is not unified. One group categorizes spatial queries into five types: basic, join, computational geometry, data mining, and raster operations [13]. The other group classifies spatial queries on vector data into five types: topologybased, metric-based, and direction-based [7,24]. Techniques for spatial query optimization differ significantly from those used for relational data query optimization. For query rewriting, due to the complex data types and user-defined functions, several heuristic rules by relational query rewriter are no longer unconditional for spatial query rewriter [31]. For cost estimators, spatial query estimations are also more complex than relational query estimations. Spatial queries involve both spatial operators and nonspatial operators. Estimating spatial operators is often associated with inequality relations, such as OVERLAP, DISTANCE, etc.
Previous tutorials present comprehensive studies about learnedbased DBMS [18], query optimizer [15], and learned-based query optimizers [33,43]; however, they missed the spatial query operators and requirements. Several tutorials discuss spatial data management [12] and spatial data applications [6,29], but none of them link to spatial query optimization in DBMS and data processing platforms. In this tutorial, we aim to review the existing methods in learning-based query plan generators and cost estimators and discuss the open problems in spatial query optimization. Additionally, we will also cover learned solutions for spatial data management, including learning spatial index and spatial partitioning, to highlight the I/O cost of spatial query execution. A tutorial [1] reviews learned multi-dimensional indexes. As a supplement to [1], we discuss newly learned spatial indexes from recent years and learned spatial partitioning techniques in this tutorial.
Figure 1 shows the outline of this tutorial. We plan to spend 90 minutes discussing techniques for spatial query optimization with learning. This tutorial targets students, researchers, and practitioners who are interested in exploring problems in spatial query optimization. In the first part, we will introduce the background of query optimization components and spatial data processing. No prior knowledge of spatial data is required for the audience. We aim to inspire the audience with the following three parts: (1) Key features of spatial data management and spatial query optimizations;
(2) Existing works on spatial query optimization; (3) Why techniques for relational query optimization cannot be directly applied to spatial query optimization; (4) Gaps for future research in spatial query optimization with learning. Figure 2 summarizes the works that will be discussed during the presentation and categorizes them based on query optimization goals.
We cover two topics about learned solutions for query optimizers: query plan optimizer [5,8,23,34,40,44,49,50] and query rewriter [4,24,39,51].
SJML [34] designs a spatial join framework based on several learning models. The proposed models predict the best spatial join algorithm and features, such as the plane-sweep direction (along the x-or y-axis). SpatialEmbedding [5] proposes a framework based on three learning models, which include an unsupervised model to capture the features of spatial datasets and two supervised models for the cost estimation of spatial operations. Optimizing the query execution plan is an important step in the DBMS and distributed data processing platforms. There are also several works [8,23,40,44,49,50] that use learned models to evaluate the query plan and select the optimal query execution plan. These works are marked with grey color in Figure 1 because they are proposed for relational data and queries. Existing spatial optimizers focus on query execution and lack of supporting in considering query plans.
Maliva [4] applies the Markov Decision Process model to rewrite the queries. The proposed model can be applied to spatial aggregation queries. SemanticQueryOpt [24] proposes a strategy for the semantic query optimization of spatial join queries. This technique aims to eliminate unnecessary spatial joins or replace expensive spatial joins with cheaper thematic joins. Since SemanticQueryOpt is not a learning solution, it is marked with a dashed border in Figure 1. We mark LearnedRewriter [51] and WeTune [39] with grey color because they are rule-based learned query rewriters for relational data. Although these works in grey are not learning-based spatial query optimization techniques, we highlight them to guide future research on rule-based spatial query rewriters.
Extensive efforts have been dedicated to learned-based cost estimation. In this subsection, we cover works related to computation cost estimation. The computation cost of the query plan relates to selectivity and cardinality. Selectivity refers to the percentage of tuples among the whole dataset that satisfies the query predicates [3]. Cardinality refers to the number of results returned by each operation [3].
Researchers usually summarize computation cost estimation learning models into two categories: query-driven and data-driven. Query-driven models treat cardinality estimation as a regression problem and learn a mapping function between the query and its cardinality on a database [16,20,25,28,38,41,48]. They use query workload as labeled training data to learn supervised query models. Data-driven models learn the join data distribution of attributes directly from the dataset [2,17,26,30,34,36,42,46,52]. Some models take data as unsupervised information to learn unsupervised data models [2,17,26,30,41,42,46,52] Some models are unsupervised data models that are directly learned from the data. Some models are supervised data models. LearningToSample [36] learns a probabilistic classifier by queries. SJML [34] learns data statistics similar to data synopses.
In spatial data processing, the statistics used to complete cardinality estimation tasks vary for different types of data. For example, estimating the cardinality of a spatial overlap-join for two sets of polygon datasets requires knowledge of the average volume and other features of the polygons. On the other hand, the cardinality of a distance-join for two sets of point datasets can be estimated using data distribution. In this part, we will highlight the types of cardinality estimation tasks each work addresses and the types of data each model can handle. SJML [34] is designed for polygon datasets and spatial join selectivity estimation. Some works are designed for high-dimensional datasets and can be applied to range query cardinality estimation for spatial point data [2,16,17,20,25,26,28,32,36,38,41,42,46,48,52]. Learning-ToSample [36] leans a classifier based on the sample of the data and can be applied to spatial point datasets. TurboReg [30] proposes a regression model for predicting the presence or absence of spatial phenomena. PivNet [2] uses a regression-based solution to estimate the k-NN queries.
Data indexing is the most important factor that affects the I/O cost of spatial data processing in DBMSs. In distributed DBMSs and platforms, the I/O cost of spatial data processing is also related to data partitioning. Most recently proposed learned spatial indexes are designed for spatial point data [10,14,19,22,27,37,47]. RW-Tree [10] and RLR-Tree [14] leverage learning-based methods from query workload to help with R-tree construction. LISA [19], SLBRIN [37], and SPRIG [47] learn spatial index based on grid cells partitioning. RSMI [27] and ELSI [22] learn spatial index based on the z-order model. There are two recent works on learned spatial partitioning. ClusterPar [45] uses K-Means clustering to partition the spatial point datasets. SpatialJoinFramework [35] uses regression models to learn the features of spatial join. The models can decide the number of partitions and choose the partitioning strategy for spatial polygon datasets.
After reviewing recently learned solutions for query optimization, we want to highlight several gaps in spatial query optimization:
(1) Query rewriting rules for optimizing the spatial operations;
(2) Models and frameworks that also consider the spatial query execution;
(3) More focus on types of spatial data beyond point datasets, such as linestrings, polygons, and spatial raster data, along with their cost estimation tasks; (4) How to apply current learned partitioning models to existing distributed platforms and integrate these learned solutions into the query optimization components of distributed platforms.
Zhang is a Ph.D. candidate in the Department of Computer Science and Engineering at the University of California, Riverside. She received her B.S. in Software Engineering from Shandong University in 2016 and her M.S. in Computer Science from Washington State University in 2018. She has interned at IBM Research, Almaden, and at Amazon AWS Redshift. Her research interests include big data management and approximate query processing. Ahmed Eldawy is an Associate Professor in Computer Science at UC Riverside. His research focuses big data management and spatial data processing. Ahmed led the research and development in many open-source projects for big spatial data exploration and visualization including UCR-Star, an interactive repository with nearly four terabytes of publicly available geospatial data. He delivered a series of tutorials on big spatial data in VLDB, ICDE, IEEE BigData, and MDM. He is a recipient of the NSF CAREER award as well as the best demo award in SIGSPATIAL 2020.