Exploring learned join algorithm selection in relational database management systems
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, February, 2021
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/130706 |
| _version_ | 1811089659173797888 |
|---|---|
| author | Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology. |
| author2 | Ryan C. Marcus and Tim Kraska. |
| author_facet | Ryan C. Marcus and Tim Kraska. Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology. |
| author_sort | Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology. |
| collection | MIT |
| description | Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, February, 2021 |
| first_indexed | 2024-09-23T14:22:42Z |
| format | Thesis |
| id | mit-1721.1/130706 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:22:42Z |
| publishDate | 2021 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1307062022-10-04T06:03:16Z Exploring learned join algorithm selection in relational database management systems Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology. Ryan C. Marcus and Tim Kraska. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, February, 2021 Cataloged from the official PDF of thesis. Includes bibliographical references (page 81). Query optimizers, crucial components of relational database management systems, are responsible for generating efficient query execution plans. Despite many advances in the database community over the last few decades, most popular relational database management systems today still use cost-based optimizers that do not always model the underlying data's characteristics accurately. These cost-based optimizers brutally slow down a query if they make even one gross underestimate of a database table's cardinality. In this work, we improve on native cost-based optimizer performance by identifying the most ideal join algorithms for query execution plans in two popular relational database management systems, PostgreSQL and Microsoft SQL. First, we gather baseline query execution times for the entire IMDb Join Order Benchmark under different subsets of usable join algorithms to show that no subset yields high performance across all queries. We then show that it is feasible to use deep reinforcement learning to choose one of these subsets for each query seen and achieve far better performance on the intensive JOB queries. Finally, we introduce the idea of k-edits, showing results that indicate that for some queries, isolating just 1 "bad" join and changing its join algorithm can yield better performance. Our work suggests that reinforcement learning with both coarse and fine decisions shows huge potential for the future of query optimization and relational database management systems. by Long Phi Nguyen. M. Eng. M.Eng. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2021-05-24T19:52:30Z 2021-05-24T19:52:30Z 2021 2021 Thesis https://hdl.handle.net/1721.1/130706 1251800590 eng MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided. http://dspace.mit.edu/handle/1721.1/7582 81 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology. Exploring learned join algorithm selection in relational database management systems |
| title | Exploring learned join algorithm selection in relational database management systems |
| title_full | Exploring learned join algorithm selection in relational database management systems |
| title_fullStr | Exploring learned join algorithm selection in relational database management systems |
| title_full_unstemmed | Exploring learned join algorithm selection in relational database management systems |
| title_short | Exploring learned join algorithm selection in relational database management systems |
| title_sort | exploring learned join algorithm selection in relational database management systems |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/130706 |
| work_keys_str_mv | AT nguyenlongphimengmassachusettsinstituteoftechnology exploringlearnedjoinalgorithmselectioninrelationaldatabasemanagementsystems |