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

US10795887B1 · kind B1 · 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: Aug 18, 2017
• Grant date: Oct 6, 2020
• Expiry date: Jan 27, 2039

Classification

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

Abstract

A database engine receives a query and parses the query to form a first intermediate query. The engine compiles the first intermediate query to form a first executable plan that includes in-memory operators that execute within memory without swapping to secondary memory. While executing a first in-memory operator in the first executable plan, the engine detects insufficient memory and aborts execution of the first executable plan. The engine optimizes the first intermediate query to form a second intermediate query, and compiles the second intermediate query to form a second executable plan. The second plan includes spooling operators that execute within fixed memory budgets and are configured to swap to the secondary memory when needed. The engine executes the second executable plan, including the spooling operators, to retrieve results from the database that are responsive to the query. The engine then returns the retrieved results.