{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/130706"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/130706","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Exploring learned join algorithm selection in relational database management systems","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology."],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Ryan C. Marcus and Tim Kraska."],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021","date_published":"2021","updated_at":"2026-07-22T22:22:02Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/130706","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Ryan C. Marcus and Tim Kraska."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","EECS"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-05-24T19:52:30Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-05-24T19:52:30Z"]},{"key":"dc:date.issued","label":"Date","values":["2021"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/130706"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M. Eng."]},{"key":"dc:title","label":"Title","values":["Exploring learned join algorithm selection in relational database management systems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ryan C. Marcus and Tim Kraska."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","EECS"],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Nguyen, Long Phi,M. Eng.Massachusetts Institute of Technology."],"dc:date.accessioned":["2021-05-24T19:52:30Z"],"dc:date.available":["2021-05-24T19:52:30Z"],"dc:date.issued":["2021"],"dc:description":["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)."],"dc:description.abstract":["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."],"dc:description.degree":["M. Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/130706"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Exploring learned join algorithm selection in relational database management systems"],"dc:type":["Thesis"],"thesis:degree_name":["Master"]},"updated_at":"2026-07-22T22:22:02Z"}