Duet: efficient and scalable hybriD neUral rElation undersTanding
This addresses scalability and practical application issues in database systems for improved query optimization, though it is incremental as it builds on existing hybrid methods.
The paper tackles the inefficiency and instability of learned cardinality estimation methods, particularly due to progressive sampling, by proposing Duet, a hybrid method that eliminates sampling and reduces inference complexity from O(n) to O(1) while achieving higher accuracy on high-dimensional tables.
Learned cardinality estimation methods have achieved high precision compared to traditional methods. Among learned methods, query-driven approaches have faced the workload drift problem for a long time. Although both data-driven and hybrid methods are proposed to avoid this problem, most of them suffer from high training and estimation costs, limited scalability, instability, and long-tail distribution problems on high-dimensional tables, which seriously affects the practical application of learned cardinality estimators. In this paper, we prove that most of these problems are directly caused by the widely used progressive sampling. We solve this problem by introducing predicate information into the autoregressive model and propose Duet, a stable, efficient, and scalable hybrid method to estimate cardinality directly without sampling or any non-differentiable process, which can not only reduce the inference complexity from $O(n)$ to $O(1)$ compared to Naru and UAE but also achieve higher accuracy on high cardinality and high-dimensional tables. Experimental results show that Duet can achieve all the design goals above and be much more practical. Besides, Duet even has a lower inference cost on CPU than that of most learned methods on GPU.