Nitin Nayak
Sven Groppe
ABSTRACT
The join order is one of the most important factors that impact the speed of query processing. Its optimization is known to be NP-hard, such that it is worth investigating the benefits of utilizing quantum computers for optimizing join orders. Hence in this paper, we propose to model the join order problem as quadratic unconstrained binary optimization (QUBO) problem to be solved with various quantum approaches like QAOA, VQE, simulated annealing and quantum annealing. In this paper, we will show the enhanced performance using our QUBO formulation to find valid and optimal shots for real-world queries joining three, four and five relations on D-Wave quantum annealer. The highlight of this study will demonstrate that we were able to generate valid and optimal join orders for five relations using the D-Wave quantum annealer, with values of about 12% and 0.27% respectively and we were able to find the optimal bushy join trees. Experiments for the gate-based simulations were able to produce optimized join order for three and four relations including bushy trees using QAOA and VQE algorithms.
- 2023. Row estimation examples. https://www.postgresql.org/docs/current/row-estimation-examples.htmlGoogle Scholar
- Tameem Albash and Daniel A Lidar. 2018. Adiabatic quantum computation. Reviews of Modern Physics 90, 1 (2018), 015002.Google ScholarCross Ref
- David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch. 2022. Filtering variational quantum algorithms for combinatorial optimization. Quantum Science and Technology 7, 1 (2022), 015021.Google ScholarCross Ref
- Rhonda Au-Yeung, Nicholas Chancellor, and Pascal Halffmann. 2022. NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems. arXiv 2212.10990 (2022). Google ScholarCross Ref
- Dimitris Bertsimas and John Tsitsiklis. 1993. Simulated annealing. Statistical science 8, 1 (1993), 10--15.Google Scholar
- Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. 2017. Quantum machine learning. Nature 549, 7671 (2017), 195--202.Google Scholar
- Olivier Carnal and Jürgen Mlynek. 1991. Young's double-slit experiment with atoms: A simple atom interferometer. Physical review letters 66, 21 (1991), 2689.Google Scholar
- Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. 2021. Variational quantum algorithms. Nature Reviews Physics 3, 9 (2021), 625--644.Google ScholarCross Ref
- Pablo Díez-Valle, Diego Porras, and Juan José García-Ripoll. 2021. Quantum variational optimization: The role of entanglement and problem hardness. Phys. Rev. A 104 (Dec 2021), 062426. Issue 6. Google ScholarCross Ref
- Christoph Durr and Peter Hoyer. 1996. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014 (1996).Google Scholar
- Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014).Google Scholar
- Richard P Feynman. 2018. Simulating physics with computers. In Feynman and computation. CRC Press, 133--153.Google Scholar
- Aleta Berk Finnila, Maria A Gomez, C Sebenik, Catherine Stenson, and Jimmie D Doll. 1994. Quantum annealing: A new method for minimizing multidimensional functions. Chemical physics letters 219, 5--6 (1994), 343--348.Google Scholar
- Fred Glover, Gary Kochenberger, and Yu Du. 2018. A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538 (2018).Google Scholar
- Fred Glover, Gary Kochenberger, and Yu Du. 2019. A Tutorial on Formulating and Using QUBO Models. arXiv:1811.11538 [cs.DS]Google Scholar
- David J Griffiths and Darrell F Schroeter. 2018. Introduction to quantum mechanics. Cambridge university press.Google Scholar
- Lov K Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 212--219.Google ScholarDigital Library
- Lov K Grover. 1997. Quantum mechanics helps in searching for a needle in a haystack. Physical review letters 79, 2 (1997), 325.Google Scholar
- Tadashi Kadowaki and Hidetoshi Nishimori. 1998. Quantum annealing in the transverse Ising model. Physical Review E 58, 5 (1998), 5355.Google ScholarCross Ref
- Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. 1983. Optimization by simulated annealing. science 220, 4598 (1983), 671--680.Google Scholar
- Stephen Klassen. 2011. The photoelectric effect: Reconstructing the story for the physics classroom. Science & Education 20 (2011), 719--731.Google ScholarCross Ref
- Wen-Yang Ku and J Christopher Beck. 2016. Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations Research 73 (2016), 165--173.Google ScholarDigital Library
- Mark W. Lewis and Fred W. Glover. 2017. Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis. CoRR abs/1705.09844 (2017). arXiv:1705.09844 http://arxiv.org/abs/1705.09844Google Scholar
- Nana Li, Yujuan Liu, Yongfeng Dong, and Junhua Gu. 2008. Application of ant colony optimization algorithm to multi-join query optimization. In Advances in Computation and Intelligence: Third International Symposium, ISICA 2008 Wuhan, China, December 19-21, 2008 Proceedings 3. Springer, 189--197.Google ScholarDigital Library
- Ryan Marcus and Olga Papaemmanouil. 2018. Deep reinforcement learning for join order enumeration. In Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management. 1--4.Google ScholarDigital Library
- Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan. 2019. Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Information 5, 1 (2019), 75.Google Scholar
- Xiao Mingyao and Li Xiongfei. 2015. Embedded database query optimization algorithm based on particle swarm optimization. In 2015 Seventh International Conference on Measuring Technology and Mechatronics Automation. IEEE, 429--432.Google ScholarCross Ref
- Florian Neukart, Gabriele Compostella, Christian Seidel, David Von Dollen, Sheir Yarkoni, and Bob Parney. 2017. Traffic flow optimization using a quantum annealer. Frontiers in ICT 4 (2017), 29.Google ScholarCross Ref
- Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information.Google Scholar
- Christos Papalitsas, Theodore Andronikos, Konstantinos Giannakis, Georgia Theocharopoulou, and Sofia Fanarioti. 2019. A QUBO model for the traveling salesman problem with time windows. Algorithms 12, 11 (2019), 224.Google ScholarCross Ref
- Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O'brien. 2014. A variational eigenvalue solver on a photonic quantum processor. Nature communications 5, 1 (2014), 4213.Google Scholar
- Daniel E Platt. 1992. A modern analysis of the Stern-Gerlach experiment. American Journal of Physics 60, 4 (1992), 306--308.Google ScholarCross Ref
- John Preskill. 2018. Quantum computing in the NISQ era and beyond. Quantum 2 (2018), 79.Google ScholarCross Ref
- Jun John Sakurai and Eugene D Commins. 1995. Modern quantum mechanics, revised edition.Google Scholar
- Wolfgang Scheufele and Guido Moerkotte. 1996. Constructing optimal bushy processing trees for join queries is np-hard. Technical Report. https://pi3.informatik.uni-mannheim.de/~moer/Publications/MA-96-11.pdf Technical reports, Universität Mannheim.Google Scholar
- Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. 2015. An introduction to quantum machine learning. Contemporary Physics 56, 2 (2015), 172--185.Google ScholarCross Ref
- Manuel Schönberger, Stefanie Scherzinger, and Wolfgang Mauerer. 2023. Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware. In Proceedings of ACM SIGMOD/PODS International Conference on Management of Data.Google ScholarDigital Library
- P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD international conference on Management of data. 23--34.Google ScholarDigital Library
- Peter W Shor. 1994. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science. Ieee, 124--134.Google ScholarDigital Library
- Michael Steinbrunn, Guido Moerkotte, and Alfons Kemper. 1997. Heuristic and randomized optimization for the join ordering problem. The VLDB Journal 6 (1997), 191--208.Google ScholarDigital Library
- Arun Swami and Anoop Gupta. 1988. Optimization of large join queries. In Proceedings of the 1988 ACM SIGMOD international conference on Management of data. 8--17.Google ScholarDigital Library
- Immanuel Trummer and Christoph Koch. 2015. Multiple query optimization on the D-Wave 2X adiabatic quantum computer. arXiv preprint arXiv:1510.06437 (2015).Google Scholar
- Tobias Winker, Sven Groppe, Valter Uotila, Zhengtong Yan, Jiaheng Lu, Maja Franz, and Wolfgang Mauerer. 2023. Quantum Machine Learning: Foundation, New Techniques, and Opportunities for Database Research. In Proceedings of ACM SIGMOD/PODS International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
- Tobias Winker, Umut Çalikyilmaz, Le Gruenwald, and Sven Groppe. 2023. Quantum Machine Learning for Join Order Optimization using Variational Quantum Circuits. In Proceedings of the International Workshop on Big Data in Emergent Distributed Environments (BiDEDE), Seattle, WA, USA. Google ScholarDigital Library
Recommendations
Non-commuting two-local Hamiltonians for quantum error suppression
Physical constraints make it challenging to implement and control many-body interactions. For this reason, designing quantum information processes with Hamiltonians consisting of only one- and two-local terms is a worthwhile challenge. Enabling error ...
Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
High Performance ComputingAbstractQuantum annealing (QA) and Quantum Alternating Operator Ansatz (QAOA) are both heuristic quantum algorithms intended for sampling optimal solutions of combinatorial optimization problems. In this article we implement a rigorous direct comparison ...
Duality quantum computer and the efficient quantum simulations
Duality quantum computing is a new mode of a quantum computer to simulate a moving quantum computer passing through a multi-slit. It exploits the particle wave duality property for computing. A quantum computer with n qubits and a qudit simulates a ...
Comments