Optimizing Queries with Disjunctions
Despite decades of research into query optimization, optimizing queries with disjunctive predicate expressions remains a challenge. Solutions employed by existing systems (if any) are often simplistic and lead to much redundant work being performed by the execution engine. In this thesis, we present...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153876 |
| _version_ | 1811074103296131072 |
|---|---|
| author | Kim, Albert |
| author2 | Madden, Samuel |
| author_facet | Madden, Samuel Kim, Albert |
| author_sort | Kim, Albert |
| collection | MIT |
| description | Despite decades of research into query optimization, optimizing queries with disjunctive predicate expressions remains a challenge. Solutions employed by existing systems (if any) are often simplistic and lead to much redundant work being performed by the execution engine. In this thesis, we present a two-pronged approach to address this problem: (1) For single-table queries, we provide a formal analysis of the problem for column-oriented engines, and based on our analysis, we present several algorithms capable of generating optimal predicate evaluation plans. Our algorithms are polynomial-time (unlike existing works), theoretically proven to produce optimal plans, and can be implemented in existing systems with minimal effort. (2) For multi-table queries, we present a novel form of query execution called tagged execution, which groups tuples into subrelations based on the predicates they satisfy and tags them with that information. Query operators can take advantage of the additional context provided by tags during runtime, and this allows them to eliminate much of the redundant work performed by traditional engines and even achieve pushdown optimizations for disjunctive predicates. Both our approaches greatly outperform existing solutions, sometimes by orders of magnitude, and we believe the combination of a theoretical approach (1) and a practical approach (2) helps meet the needs of most users. |
| first_indexed | 2024-09-23T09:43:13Z |
| format | Thesis |
| id | mit-1721.1/153876 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:43:13Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1538762024-03-22T03:58:38Z Optimizing Queries with Disjunctions Kim, Albert Madden, Samuel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Despite decades of research into query optimization, optimizing queries with disjunctive predicate expressions remains a challenge. Solutions employed by existing systems (if any) are often simplistic and lead to much redundant work being performed by the execution engine. In this thesis, we present a two-pronged approach to address this problem: (1) For single-table queries, we provide a formal analysis of the problem for column-oriented engines, and based on our analysis, we present several algorithms capable of generating optimal predicate evaluation plans. Our algorithms are polynomial-time (unlike existing works), theoretically proven to produce optimal plans, and can be implemented in existing systems with minimal effort. (2) For multi-table queries, we present a novel form of query execution called tagged execution, which groups tuples into subrelations based on the predicates they satisfy and tags them with that information. Query operators can take advantage of the additional context provided by tags during runtime, and this allows them to eliminate much of the redundant work performed by traditional engines and even achieve pushdown optimizations for disjunctive predicates. Both our approaches greatly outperform existing solutions, sometimes by orders of magnitude, and we believe the combination of a theoretical approach (1) and a practical approach (2) helps meet the needs of most users. Ph.D. 2024-03-21T19:12:49Z 2024-03-21T19:12:49Z 2024-02 2024-02-21T17:18:50.996Z Thesis https://hdl.handle.net/1721.1/153876 Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) Copyright retained by author(s) https://creativecommons.org/licenses/by-sa/4.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Kim, Albert Optimizing Queries with Disjunctions |
| title | Optimizing Queries with Disjunctions |
| title_full | Optimizing Queries with Disjunctions |
| title_fullStr | Optimizing Queries with Disjunctions |
| title_full_unstemmed | Optimizing Queries with Disjunctions |
| title_short | Optimizing Queries with Disjunctions |
| title_sort | optimizing queries with disjunctions |
| url | https://hdl.handle.net/1721.1/153876 |
| work_keys_str_mv | AT kimalbert optimizingquerieswithdisjunctions |