Granted Patent B2

US 12,210,528 · App. 18/162,607 · Granted Jan 28, 2025

Inventors: Utkarsh Agarwal (San Francisco, CA); Shoumik Palkar (San Francisco, CA); Alexander Behm (San Francisco, CA); Sriram Krishnamurthy (San Francisco, CA)

Assignee: Databricks, Inc.

G06F16/24558G06F11/3409G06F16/221

Abstract

Claims (54)

1. A method comprising:

receiving a first request to perform a first query for a columnar dataset stored on cloud storage, the first query comprising an operator to evaluate within a column in the columnar dataset, wherein the column in the columnar dataset is based on a dictionary that maps one or more values for the column to one or more respective identifiers;

determining whether to perform dictionary filtering for the first query by calculating a metric based on one or more factors comprising at least a size of the dictionary and an estimated cost of executing the first query;

performing one of:

retrieving the column associated with the dictionary and evaluating the operator on the column when the metric is equal to or above a threshold; and

executing dictionary filtering when the metric is below the threshold, wherein performing dictionary filtering comprises:

determining whether a value of interest is present in the dictionary, and

evaluating, responsive to a determination that the value of interest is present in the dictionary, the operator on one or more values of the dictionary;

generating, responsive to the evaluation of the operator on the one or more values of the dictionary, an updated dictionary comprising updated values;

receiving a second request to perform a second query, the second query comprising a filter to evaluate within the column in the columnar dataset, the column in the columnar dataset based on the updated dictionary; and

evaluating the filter on the updated dictionary.

2. The method of claim 1 , wherein the first query comprises a binary expression with two inputs, wherein each input is a column in the columnar dataset based on the dictionary.

3. The method of claim 1 , further comprising:

decoding dictionary-encoded values of the column, for each row in the column, based on the updated dictionary.

4. The method of claim 1 , wherein evaluating the operator on the one or more values of the dictionary comprises capitalizing the one or more values of the dictionary.

5. The method of claim 1 , wherein the first query further comprises a request to return information about the value of interest in the columnar dataset stored on the cloud storage.

6. The method of claim 1 , further comprising determining whether to perform dictionary filtering for the second query by calculating a metric based on one or more factors comprising at least the size of the dictionary and an estimated cost of executing the second query.

7. A system comprising:

at least one processor;

at least one memory comprising stored instructions, the instructions when executed cause the at least one processor to:

receive a first request to perform a first query for a columnar dataset stored on cloud storage, the first query comprising an operator to evaluate within a column in the columnar dataset, wherein the column in the columnar dataset is based on a dictionary that maps one or more values for the column to one or more respective identifiers;

determine whether to perform dictionary filtering for the first query by calculating a metric based on one or more factors comprising at least dictionary size and an estimated cost of executing the first query;

perform one of:

retrieve the column associated with the dictionary and evaluating the operator on the column when the metric is equal to or above a threshold; and

execute dictionary filtering when the metric is below the threshold, wherein the instructions that when executed cause the at least one processor to perform dictionary filtering comprises instructions that when executed cause the at least one processor to:

determine whether a value of interest is present in the dictionary, and

evaluate, responsive to a determination that the value of interest is present in the dictionary, the operator on one or more values of the dictionary;

generate, after the evaluation of the operator on the one or more values of the dictionary, an updated dictionary comprising updated values;

receive a second request to perform a second query, the second query comprising a filter to evaluate within the column in the columnar dataset, the column in the columnar dataset based on the updated dictionary; and

evaluate the filter on the updated dictionary.

8. The system of claim 7 , wherein the first query comprises a binary expression with two inputs, wherein each input is a column in the columnar dataset based on the dictionary.

9. The system of claim 7 , wherein the at least one memory further comprises instructions that when executed further cause the at least one processor to:

decode dictionary-encoded values of the column, for each row in the column, based on the updated dictionary.

10. The system of claim 7 , wherein the instructions that when executed cause the at least one processor to evaluate the operator on the one or more values of the dictionary comprise instructions that when executed cause the at least one processor to capitalize the one or more values of the dictionary.

11. The system of claim 7 , wherein the first query further comprises a request to return information about the value of interest in the columnar dataset stored on the cloud storage.

12. The system of claim 7 , wherein the at least one memory further comprises instructions that when executed further cause the at least one processor to:

determine whether to perform dictionary filtering for the second query by calculating a metric based on one or more factors comprising at least the dictionary size and an estimated cost of executing the second query.

13. A non-transitory computer readable medium comprising stored instructions encoded thereon that, when executed by at least one processor, cause the at least one processor to:

receive a first request to perform a first query for a columnar dataset stored on cloud storage, the first query comprising an operator to evaluate within a column in the columnar dataset, wherein the column in the columnar dataset is based on a dictionary that maps one or more values for the column to one or more respective identifiers;

determine whether to perform dictionary filtering for the first query by calculating a metric based on one or more factors comprising at least dictionary size and an estimated cost of executing the first query;

perform one of:

retrieve the column associated with the dictionary and evaluating the operator on the column when the metric is equal to or above a threshold; and

execute dictionary filtering when the metric is below the threshold, wherein the instructions that when executed cause the at least one processor to perform dictionary filtering comprises instructions that when executed cause the at least one processor to:

determine whether a value of interest is present in the dictionary, and

evaluate, responsive to a determination that the value of interest is present in the dictionary, the operator on one or more values of the dictionary;

generate, responsive to the evaluation of the operator on the one or more values of the dictionary, an updated dictionary comprising updated values;

receive a second request to perform a second query, the second query comprising a filter to evaluate within the column in the columnar dataset, the column in the columnar dataset based on the updated dictionary; and

evaluate the filter on the updated dictionary.

14. The non-transitory computer readable medium of claim 13 , wherein the first query comprises a binary expression with two inputs, wherein each input is a column in the columnar dataset based on the dictionary.

15. The non-transitory computer readable medium of claim 13 , wherein the at least one memory further comprises instructions that when executed further cause the at least one processor to:

decode dictionary-encoded values of the column, for each row in the column, based on the updated dictionary.

16. The non-transitory computer readable medium of claim 13 , wherein the first query further comprises a request to return information about the value of interest in the columnar dataset stored on the cloud storage.

17. The non-transitory computer readable medium of claim 13 , wherein the at least one memory further comprises instructions that when executed further cause the at least one processor to:

determine whether to perform dictionary filtering for the second query by calculating a metric based on one or more factors comprising at least the dictionary size and an estimated cost of executing the second query.

Assignments (2)

Continuity (1)

References Cited (19)