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

US11789988B2 · kind B2 · 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: Jul 8, 2021
• Grant date: Oct 17, 2023
• Expiry date: Jul 8, 2041

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 one 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 clause includes one of a predetermined set of predicate subqueries, and adds the single join operator when the 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.