TESSM: Tree-based Selective State Space Models for Efficient Join Order Selection Learning

Join order optimization is pivotal in database query optimization, seeking the most efficient join sequence to reduce execution costs. As more tables join, the complexity surges, turning it into an NP-hard problem due to the exponential growth of possible orders. Deep reinforcement learning (DRL) has recently made significant strides, outperforming traditional algorithms by treating join selection as a Markov Decision Process to devise more effective strategies.Current methods struggle with integrating query semantics and plan structures, as well as encountering issues with complex joins where bottom-up learning can lead to information loss.To tackle these issues, we present the Tree-based Selective State Space Models for Efficient Join Order Selection Learning(TESSM). This framework uses the Tree Mamba architecture to integrate join pattern graphs with execution plan nodes, enhancing long-term dependency information flow. A tiered training strategy enhances the model's training precision and speed.Our approach has proven effective, as evidenced by JOB and TPC-H benchmark tests, showing TESSM's substantial improvements in query optimization efficiency and effectiveness.