Elimination of query fragment duplication in complex database queries

US10795888B2 · kind B2 · utility

Assignee

• Tableau Software, Inc. · US

Inventors

• Adrian Vogelsgesang · Munich, DE
• Michael Haubenschild · Erding, DE
• Richard L. Cole · Los Gatos, US
• Jan Finis · Munich, DE
• Manuel Then · Munich, DE
• Tobias Muehlbauer · Munich, DE
• Thomas Neumann · Munich, DE

Key dates

• Filing date: Dec 21, 2018
• Grant date: Oct 6, 2020
• Expiry date: Apr 22, 2039

Classification

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

Abstract

A database engine receives a database query from a client. The database engine parses the database query to build a query operator tree that includes a plurality of query operators. The database engine performs one or more optimization passes on the query operator tree, including a deduplication optimization pass, to form an optimized execution plan. The deduplication optimization pass includes: creating a list of query operators via a first traversal of the query operator tree, determining a first query operator that is equivalent to a second query operator, based on a hash map, via a second traversal of the query operator tree, and substituting, via a third traversal of the query operator tree, the second query operator with a tree node that links to the first query operator. The database engine executes the optimized execution plan to retrieve a result set from the database, and returns the result set.