Dynamic rebuilding of query execution trees and reselection of query execution operators

US11301469B2 · kind B2 · utility

Assignee

• Tableau Software, Inc. · US

Inventors

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

Key dates

• Filing date: Sep 4, 2020
• Grant date: Apr 12, 2022
• Expiry date: Sep 4, 2040

Classification

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

Abstract

A method dynamically selects query execution operators. A database engine receives a query, parses the query to form a query execution tree, and compiles the tree to form a first executable plan that includes in-memory operators. The database engine executes the first plan, including executing in-memory operators in parallel. While executing a first in-memory operator, insufficient memory is detected. In response, the database engine aborts the execution, and recompiles the query tree in two ways, forming a second executable plan that replaces the first in-memory operator with a first spooling operator. The first spooling operator executes within a fixed volatile memory budget and swaps to non-volatile memory according to the budget. A third executable plan retains the first in-memory operator, but schedules it to run serially. The database engine selects either the second plan or the third plan, and executes the selected plan to return results for the query.