Thesis Defense: Albert Kim, Title: Optimizing Queries with Disjunctions

Speaker: Albert Kim , CSAIL MIT

Date: Tuesday, December 05, 2023

Time: 3:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Seminar Room G882 (Hewlett Room)

Event Type: Thesis Defense

Room Description:

Host: Sam Madden, CSAIL MIT

Contact: Albert Kim, alkim@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, dsg-active@csail.mit.edu

Reminder Subject: TALK: Thesis Defense: Albert Kim, Title: Optimizing Queries with Disjunctions

Abstract: 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.

Zoom Link: https://mit.zoom.us/j/95242352726

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Albert Kim Email at Thursday, November 16, 2023 at 11:45 AM.