Optimizing database query execution by extending the relational algebra to include non-standard join operators

US11068520B1 · kind B1 · utility

Assignee

• Tableau Software, Inc. · US

Inventors

• Thomas Neumann · Munich, DE
• Viktor Leis · Munich, DE
• Alfons Kemper · Munich, DE
• Tobias Muehlbauer · Munich, DE
• Jan Finis · Munich, DE

Key dates

• Filing date: Feb 6, 2018
• Grant date: Jul 20, 2021
• Expiry date: May 23, 2040

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/334
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

A method is executed at a computer system to retrieve data from a database. Upon receiving a database query, a database engine of the computer system parses the query to form an operator tree including a plurality of join operators. For each of the plurality of clauses, the database engine adds to the operator tree a respective node that specifies a mark join operator, a single join operator, an inner join operator, or an outer join operator. Specifically, the database engine adds the mark join operator when the respective clause includes one of a predetermined set of predicate subqueries, and adds the single join operator when the respective clause includes a scalar subquery. The database engine performs one or more optimization passes on the operator tree to form an optimized execution plan, and executes the optimized execution plan to retrieve a result set from the database.