In the release 38.0 of Siren Federate, the Adaptive Query Planner (AQP) was set as the default query planner. This takes over the previous Static Query Planner (SQP) in order to create better query plans for a majority of use cases. This post presents the general idea of AQP, while the journal paper “ Bordea, G., Campinas, S., Catena, M., & Delbru, R. (2025). Siren Federate: Bridging document, relational, and graph models for exploratory graph analysis. To appear in Computer Science and Information Systems” describes it in detail.
The query planner is the brain of the system. Among many things, it is responsible for parsing the user’s request, analyzing how joins are defined, and selecting the most performant algorithm for a given join. The algorithm selection is an essential step of the query planner to ensure that a query executes as efficiently as possible, with a small query latency.
The Static Query Planner and its Drawback
The workflow of SQP is depicted in the diagram below. SQP is a planner that works in two phases: a planner phase that associates a particular join algorithm to all joins from the search request, then an execution phase that evaluates the joins with implementations previously selected. The planner phase consists in creating the logical and physical query plans. The selection of a particular join algorithm is the responsibility of the query optimizer, which is necessary for the physical query plan creation. The query optimizer selects the least costly algorithm for the evaluation of a join, and for this relies on cost models: based on several statistics, a model quantifies the cost of evaluating a join with a particular algorithm. Once the physical query plan is defined with the selected join algorithms, it is translated into low-level tasks that can run using the Elasticsearch infrastructure.
A drawback of SQP lies in the query optimizer. A join query can be written to depend on the result of another join, with that join depending on yet another join, so on and so forth. See the example graph depicted below, where a node represents a search on some indices and an edge the join between indices. Estimating the cost of the former join (e.g., the “callee” join) involves statistics such as search cardinalities, which would require dependent joins to be already computed.
Since that is not the case, a possible solution consists then in estimating those statistics, for example with data sampling. However, the accuracy of estimations depends on the quality of the sampling, i.e., how well it represents the data. The sampling quality also degrades the more dependent joins there are: consider for example the sampling of “Person” which depends on the “author” relationship; the actual number of “Person” satisfying that relationship may be large or small. Beyond the quality of data samples, this solution would also bring some computation overhead: a join would need to be computed, even if that is a join on a small amount of data.
The accuracy of an estimation has therefore a direct impact on the accuracy of a cost model, thus on the ability of a query optimizer to select the best join algorithm for a particular use case. A bad estimation can lead to the selection of an algorithm that is not appropriate, resulting in the request’s latency to be higher than if the optimal algorithm were chosen.
Adaptive Query Planner
The main goal of AQP is to improve the query optimizer by removing the need for estimations. The rationale is that using exact statistics in a cost model would always lead to the selection of the optimal join algorithm. The diagram below depicts the evolution of the previous workflow to achieve that goal. The two planner and execution phases are now interleaved. After the creation of the logical query plan, a stages tree is created with a stage representing a single join query from the search request. Stages are then evaluated bottom-up so that joins that others depend on are first evaluated. The workflow at this point is similar to what the SQP does – but scoped to a stage. Indeed, for every stage we call the query optimizer in order to select the optimal algorithm necessary for the creation of the physical query plan. This plan is then translated into low-level Elasticsearch tasks that can be run on the Elasticsearch infrastructure. This paradigm shift from SQP allows the accurate computation of costs in the query optimizer, since all dependent joins would have been already evaluated, hence the selection of the optimal algorithm. As the term “adaptive” in AQP suggests, this enables the query planner to support efficiently a wide variety of join scenarios.
Investigations typically involve long chains of joins. The previous example linking “Call Detail Records” to “Forum posts” via “Person”, although simple, already contains two join operations. As graph patterns become more complex, so does the amount of joins. In the domains of crime or fraud investigations, data naturally takes the shape of a graph. Therefore, investigations boil down to the exploration of graphs. AQP increases the performance of relational search requests by reacting to low-selectivity joins, which can only be known for certain at execution-time for joins with many dependencies, by using more appropriate algorithms.
AQP also facilitates the implementation of future optimizations, such as joins reordering or the decision of which side to broadcast data in the cluster (as opposed to the child data being always broadcasted for algorithms like BROADCAST_JOIN). Together with AQP, we have also improved several components of the planner. For example, we have introduced the concept of logical data signature for joins in order to handle joins semantically, an important feature for the query cache. The logical data signature also allowed to reduce the space required for dependent data structures, thus reducing the load on the cluster during the evaluation of search requests. In AQP we also detect early on whether a search request involves join queries or not, in order to bypass the query planner in case no join is declared; this removes significant overhead for plain Elasticsearch requests.
Related Works
The concept of the adaptive query planner is not novel. It is applied in several commercial products and has been a research topic for some years. Microsoft added an adaptive query execution feature to SQL Server in 2017. Databricks improves the execution of SQL queries by incorporating runtime statistics. In the academia, Pavlopoulou et al for example propose an implementation of an adaptive query planner in a distributed query engine called AsterixDB. The goal is to select better join algorithms by computing more accurate statistics: instead of cardinality approximations, they employ a technique similar to the one we implemented in Siren Federate.