Computing domain cardinality estimates for optimizing database query execution

US10824625B1 · kind B1 · utility

Assignee

• Tableau Software, Inc. · US

Inventors

• Sebastian Hofstetter · Munich, DE
• Moritz Kaufmann · Munich, DE
• Thomas Neumann · Munich, DE
• Viktor Leis · Munich, DE
• Alfons Kemper · Munich, DE
• Tobias Muehlbauer · Munich, DE
• Jan Finis · Munich, DE
• Manuel Then · Munich, DE

Key dates

• Filing date: Dec 28, 2018
• Grant date: Nov 3, 2020
• Expiry date: Apr 24, 2039

Classification

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

Abstract

A method implements optimization of database queries by computing domain cardinality estimates. A client sends a database query to a server. The method parses the query to identify data columns. For each of the data columns, the method computes a lower bound and an upper bound of distinct data values using a pre-computed table size. The method also computes a patch factor by applying a pre-computed function to a ratio between a number of distinct data values that appear exactly once in a data sample and a number of distinct data values in the sample. Based on the patch factor, the lower bound, and the upper bound, the method computes an estimate of distinct values for each of the data columns. The method subsequently generates an execution plan for the query according to the computed estimates, executes the execution plan, and returns a result set to the client.