标题： 基于量子计算机的高阶无约束二元优化的左深连接顺序选择 显示英文标题

标题： Left-Deep Join Order Selection with Higher-Order Unconstrained Binary Optimization on Quantum Computers

摘要： 连接顺序优化是最重要的查询优化问题之一，其核心地位在量子计算应用于数据库优化和数据管理的新研究领域中也显而易见。 在该领域中，连接顺序优化是最受研究的数据库问题，通常使用二次无约束二进制优化模型来解决，该模型通过各种元启发式方法求解，如量子退火、量子近似优化算法或变分量子本征求解器。 在本工作中，我们通过提出三种新颖的量子优化算法，继续开发用于连接顺序优化的量子计算技术。 这些算法基于一个高阶无约束二进制优化模型，这是二次模型的推广，此前尚未应用于数据库问题。 理论上，这些优化问题自然映射到通用量子计算机和量子退火器。 与之前的研究相比，我们的两种算法是首次精确建模连接顺序成本函数的量子算法。 我们通过证明理论界限，表明这两种方法在没有交叉乘积的情况下编码了与动态规划算法相同的计划，这提供了在交叉乘积方面的最优结果。 第三种算法在没有交叉乘积的情况下能够达到至少与贪心算法同样好的计划。 这些结果在连接顺序选择的经典和量子算法之间建立了重要的理论联系，这在以前的研究中尚未被研究。 为了展示我们算法的实际可用性，我们使用量子和经典求解器对数千个团、环、星、树和链查询图进行了实验评估。 显示英文摘要

摘要： Join order optimization is among the most crucial query optimization problems, and its central position is also evident in the new research field where quantum computing is applied to database optimization and data management. In the field, join order optimization is the most studied database problem, usually tackled with a quadratic unconstrained binary optimization model, which is solved with various meta-heuristics such as quantum annealing, quantum approximate optimization algorithm, or variational quantum eigensolver. In this work, we continue developing quantum computing techniques for join order optimization by presenting three novel quantum optimization algorithms. These algorithms are based on a higher-order unconstrained binary optimization model, which is a generalization of the quadratic model and has not previously been applied to database problems. Theoretically, these optimization problems naturally map to universal quantum computers and quantum annealers. Compared to previous research, two of our algorithms are the first quantum algorithms to precisely model the join order cost function. We prove theoretical bounds by showing that these two methods encode the same plans as the dynamic programming algorithm without cross-products, which provides the optimal result up to cross-products. The third algorithm reaches at least as good plans as the greedy algorithm without cross-products. These results set an important theoretical connection between the classical and quantum algorithms for join order selection, which has not been studied in the previous research. To demonstrate our algorithms' practical usability, we have conducted an experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using quantum and classical solvers.