New AI Network Picks Faster Join Orders for Database Queries

A new study published in the journal Data Science and Engineering introduces LIGHT, a learned join order selection network that uses a dynamic graph attention mechanism to make that decision more reliably than existing approaches. According to the authors, LIGHT significantly outperformed both the native PostgreSQL optimizer and a series of state-of-the-art learning-based optimizers on two standard benchmarks, the Join Order Benchmark (JOB) and TPC-DS, in terms of query execution performance.

Join order selection is one of the key technologies inside database query optimizers. When a SQL query touches several tables, the number of possible ways to combine them grows exponentially with the number of tables, so efficiently navigating this vast search space to find a low-cost join order is a formidable computational challenge. Traditional optimizers such as System R and PostgreSQL rely on cardinality estimation and cost models, guided by dynamic programming or heuristics built on static statistics like table cardinalities and selectivities. Because these systems depend on predefined rules, they start the optimization process from scratch for each new query and repeatedly make suboptimal choices, and estimation errors can accumulate across multi-join queries.

In recent years, reinforcement learning has emerged as a promising alternative. Rather than estimating costs with handcrafted formulas, reinforcement learning formulates join order selection as a sequential decision-making problem and learns directly from execution feedback, allowing the optimizer to capture the long-term impact of early join decisions. However, the authors identify persistent weaknesses in existing learned optimizers. Methods such as ReJOIN and Neo use static query representations and fail to dynamically capture inter-table dependencies. Reinforcement learning approaches like RTOS and Balsa are highly sensitive to reward volatility, which can destabilize training, and their exploration strategies often lack sufficient diversification, making them prone to converging on local optima.

LIGHT attacks these weaknesses with three coordinated components. The first is a novel query encoder. The system builds a 16-bit one-hot encoding for each column of each table, drawing on static schema information and statistics from PostgreSQL’s pg_stats view, covering column types, the proportion of unique values, the fraction of null values, index presence, and the number of foreign keys. Query parsing through the psqlparse plugin then produces five combined vectors: selectivity predicates, join predicates, global features, one-hot table identifiers, and column features. A residual connection neural network, called ResNN, processes these vectors to obtain an initial representation of the query.

The second component is where the paper’s name comes from. LIGHT constructs a query graph in which each table is a node and join predicates between tables are edges, then applies GATv2, a graph attention network with dynamic attention. Standard graph attention networks use an attention function that is monotonic with respect to neighbor scores, which limits their expressiveness; GATv2 instead allows different key nodes to be selected for each query node. In LIGHT, the attention mechanism propagates and fuses table node vectors so that each node focuses on the features of its most relevant neighbors, enhancing the query’s vector representation before any join decision is made. The authors argue this addresses a limitation of earlier graph-based optimizers such as SOAR, LOGER and JOGGER, which typically use static attention mechanisms that cannot adjust attention weights based on varying neighbor importance across different query contexts.

The third component concerns how the system searches for plans. LIGHT uses a Deep Q-Network, with a Tree-LSTM structure depicting the join order of the plan, and a PredNN network that predicts the latency value of candidate joins. To explore the solution space more effectively, the researchers modified the classical epsilon-greedy algorithm by incorporating beam search. During exploitation, the system selects the top k actions with the smallest predicted latency values as beam candidates. For the remaining candidates, a weighted random list is used: tables that have appeared frequently in previous sub-states receive lower sampling weights, calculated as the inverse of one plus their occurrence frequency, so actions involving rarely explored tables are chosen more often. This encourages exploration of join orders that have not been tried before and mitigates the risk of falling into local optima. Notably, LIGHT does not explicitly designate join operators itself; it delegates that final selection to the expert optimizer within the database management system, reducing the likelihood of performance issues from a wrong operator choice.

Training stability is handled by a reward shaping mechanism. Because different segments of a join plan carry varying degrees of importance for execution latency, reward values can vary wildly, and inefficient join orders can produce large latency swings for the same query. LIGHT stores explored state-action pairs in an experience replay buffer initialized with join orders generated by the PostgreSQL optimizer, keeps optimal relative latency values in a separate buffer, and applies a logarithmic transformation, compressing relative latency values through the natural logarithm of one plus the value. In ablation experiments on JOB, removing the logarithmic transformation caused loss values to fluctuate between 3 and 10,000 during training, indicating prolonged convergence and less robust plans, whereas LIGHT’s loss converged to the range between 0 and 0.1.

The experimental results are the strongest part of the story. On the JOB benchmark, which is based on the real-world IMDb dataset with 113 queries, of which 33 were used for testing, LIGHT reduced Workload Relative Latency (WRL) to 0.526, compared with 0.885 for RTOS, 0.669 for Balsa, 0.807 for Robust-MSCN and 0.888 for JGMP, corresponding to relative reductions of 40.6, 21.4, 34.8 and 40.8 percent respectively against those baselines. On TPC-DS, a standard retail-scenario benchmark with 25 tables from which the authors generated 104 queries using 26 templates, LIGHT achieved a WRL of 0.636, outperforming RTOS at 0.846, Balsa at 0.811, Robust-MSCN at 0.786 and JGMP at 0.805. Since a WRL below 1 means the method beats the dynamic programming optimizer of PostgreSQL on the overall workload, LIGHT’s 0.526 and 0.636 translate to reductions of 47.4 percent on JOB and 36.4 percent on TPC-DS compared with PostgreSQL itself.

Geometric Mean Relevant Latency (GMRL), a per-query geometric mean of the latency ratio against PostgreSQL’s plans, told the same story. LIGHT reached 0.567 on JOB, ahead of RTOS at 0.911, Balsa at 0.741, Robust-MSCN at 0.936 and JGMP at 0.876, and 0.763 on TPC-DS, ahead of RTOS at 0.852, Balsa at 0.795, Robust-MSCN at 0.809 and JGMP at 0.839. A closer look at the JOB test set, whose 33 queries contain between 4 and 17 joined tables with an average of 8.88, showed that plans induced by LIGHT contained 217 nested-loop joins, 41 hash joins and 2 merge joins, compared with 226 nested-loop, 32 hash and 2 merge joins under the native PostgreSQL optimizer. The authors suggest this shift toward fewer nested-loop joins and more hash joins is associated with the latency improvements. On cost, RTOS, Robust-MSCN and JGMP retain advantages in training and inference time due to simpler model structures, but LIGHT achieves substantially better query performance than Balsa while maintaining comparable inference and training costs.

The authors are candid about limits. LIGHT is particularly suitable for multi-table join workloads with relatively stable schemas and recurring query patterns, where offline training and periodic fine-tuning are feasible. When underlying data changes but the schema stays fixed, the model can adapt by refreshing database statistics and fine-tuning on newly observed queries without full retraining, but when tables or columns are added, removed or modified, feature construction and the query graph must be rebuilt and full retraining is required. The method is less suitable for frequently changing schemas, highly volatile workloads needing immediate adaptation, or resource-constrained environments where training overhead is difficult to afford. The conclusion also acknowledges that LIGHT’s model complexity increases training costs compared with lightweight models like RTOS, and that the training process faces stability and convergence challenges. Future work, the authors write, will focus on reducing model complexity and exploring advanced reinforcement learning techniques for better stability and faster convergence. The datasets used, IMDb-based JOB and TPC-DS, are public, and the article is open access, with a correction published in October 2026.

Subject of Research: A learned join order selection network using dynamic graph attention for database query optimization

Article Title: LIGHT: A Learned Join Order Selection Network Using Dynamic Graph Attention Mechanism

Article References: Zhang, Q., Yang, J., Yan, J., Zhang, S., & Ding, Z. (2026). LIGHT: A Learned Join Order Selection Network Using Dynamic Graph Attention Mechanism. Data Science and Engineering. https://doi.org/10.1007/s41019-026-00360-y

Image Credits: AI Generated

DOI: 10.1007/s41019-026-00360-y

Keywords: databases, query optimization, join order selection, reinforcement learning, graph attention networks, PostgreSQL, deep Q-network, TPC-DS, Join Order Benchmark, reward shaping, query latency, machine learning