# US 2025/0156423 A1 · Evaluating expressions over dictionary data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0156423 A1
- Document ID: US20250156423A1
- Status: Published application
- Kind: A1
- Application number: 19/000,466
- Filed: 2024-12-23
- Published: 2025-05-15
- Earliest claimed: 2023-01-31
- Assignees: Databricks, Inc.
- Applicants: Databricks, Inc.
- Inventors: Utkarsh Agarwal; Shoumik Palkar; Alexander Behm; Sriram Krishnamurthy
- Web page: https://patentgrep.com/patent/US20250156423A1

## CPC

- G06F 16/24558: {Binary matching operations}
- G06F 11/3409: {for performance assessment}
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 2201/80: Database-specific techniques
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed herein is a method, system, or non-transitory computer readable medium for evaluating a query on a columnar dataset comprising one or more dictionaries associated with columns in the dataset. The method includes receiving a request to perform a query comprising at least an operator for a columnar dataset on cloud storage. At least one column in the dataset is based on a dictionary, and the dictionary maps one or more values for a column to one or more respective identifiers. The method evaluates the operator on one or more values of the dictionary to generate an updated dictionary comprising updated values. The method may decode the updated dictionary into an updated column comprising updated data values.

## Claims

### Claim 1

A method comprising:
receiving a first request to perform a first query for a first columnar dataset stored on cloud storage, wherein the columnar dataset includes one or more columns based on a dictionary;
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, responsive to the metric being below a threshold, dictionary filtering by evaluating a filter on each row group encoded in the dictionary, wherein the filter is based on a first expression in the first query; and
removing row groups that fail the dictionary filter, wherein a value in each row group that fails the dictionary filter includes at least one value that is not needed to complete the first query.

### Claim 2 (depends on 1)

The method of claim 1, wherein calculating the metric further comprises:
inputting, to a machine learning model, the size of the dictionary and the estimated cost of executing the first query, wherein the machine learning model is trained on data including diciotnary sizes and estimated costs of executing queries; and
receiving, from the machine learning model, a value representative of a recommendation of whether or not to apply dictionary filtering.

### Claim 3 (depends on 1)

The method of claim 1, wherein the metric is indicative of a probability of query regression occurring in applying dictionary filtering.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
monitoring, during performance of the dictionary filtering, query regression, wherein query regression is determined based on one or more of:
increase in processor time and duration,
a number of cloud input/output requests, and
a lack of eliminated row groups in the dictionary.

### Claim 5 (depends on 4)

The method of claim 4, further comprising aborting dictionary filtering responsive to the query regression being above a threshold percentage, wherein the threshold percentage represents one or more of increase in processor time a duration and a percentage of row groups retained after passing the filter over the dictionary.

### Claim 6 (depends on 1)

The method of claim 1, wherein the value in each row group that fails the dictionary filter is not a value of interest identified by the first expression and the first expression contains a filtering request to return information about the value of interest in the columnar dataset.

### Claim 7 (depends on 6)

The method of claim 6, wherein the requested information is one or more of a determination of a presence of the value of interest in the columnar dataset, a number of instances of the value of interest in the columnar dataset, and row locations of the value of interest in the columnar dataset.

### Claim 8 (depends on 1)

The method of claim 1, wherein the dictionary maps one or more values in one or more columns to one or more respective identifiers.

### Claim 9

A system comprising:
at least one processor; and
at least one memory comprising stored instructions, the instructions when executed cause the at least one processor to:
receive a a first request to perform a first query for a columnar dataset stored on cloud storage, the first query comprising a first expression, wherein the columnar dataset includes one or more columns based on a dictionary;
calculate 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;
perform dictionary filtering in response to the metric being below a threshold by evaluating a filter on each row group encoded in the dictionary, wherein the filter is based on the first expression in the first query; and
remove row groups that fail the dictionary filter, wherein a value in each row group that fails the dictionary filter includes at least one value that is not needed to complete the first query.

### Claim 10 (depends on 9)

The system of claim 9, wherein the instructions that cause the processor to calculate the metric further cause the processor to:
input, to a machine learning model, the size of the dictionary and the estimated cost of executing the first query, wherein the machine learning model is trained on data including diciotnary sizes and estimated costs of executing queries; and
receive, from the machine learning model, a value representative of a recommendation of whether or not to apply dictionary filtering.

### Claim 11 (depends on 9)

The system of claim 9, wherein the metric is indicative of a probability of query regression occurring in applying dictionary filtering.

### Claim 12 (depends on 9)

The system of claim 9, wherein the instructions further cause the processor to:
monitor, during performance of the dictionary filtering, query regression, wherein query regression is determined based on one or more of:
increase in processor time and duration,
a number of cloud input/output requests, and
a lack of eliminated row groups in the dictionary.

### Claim 13 (depends on 12)

The system of claim 12, further comprising instructions that when executed cause the at least one processor to abort dictionary filtering in response to the query regression being above a threshold percentage, wherein the threshold percentage represents one or more of increase in processor time a duration and a percentage of row groups retained after passing the filter over the dictionary.

### Claim 14 (depends on 9)

The system of claim 9, wherein the value in each row group that fails the dictionary filter is not a value of interest identified by the first expression and the first expression contains a filtering request to return information about the value of interest in the columnar dataset.

### Claim 15 (depends on 14)

The system of claim 14, wherein the requested information is one or more of a determination of a presence of the value of interest in the columnar dataset, a number of instances of the value of interest in the columnar dataset, and row locations of the value of interest in the columnar dataset.

### Claim 16 (depends on 9)

The system of claim 9, wherein the dictionary maps one or more values in one or more columns to one or more respective identifiers.

### Claim 17

A non-transitory computer readable medium comprising stored instructions encoded thereon that, when executed by at least one processor causes the at least one processor to:
receive a first receive a a first request to perform a first query for a columnar dataset stored on cloud storage, the first query comprising a first expression, wherein the columnar dataset includes one or more columns based on a dictionary;
calculate 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;
perform dictionary filtering in response to the metric being below a threshold by evaluating a filter on each row group encoded in the dictionary, wherein the filter is based on the first expression in the first query; and
remove row groups that fail the dictionary filter, wherein a value in each row group that fails the dictionary filter includes at least one value that is not needed to complete the first query.

### Claim 18 (depends on 17)

The non-transitory computer readable medium of claim 17, wherein the instructions that cause the processor to calculate the metric further cause the processor to:
input, to a machine learning model, the size of the dictionary and the estimated cost of executing the first query, wherein the machine learning model is trained on data including diciotnary sizes and estimated costs of executing queries; and
receive, from the machine learning model, a value representative of a recommendation of whether or not to apply dictionary filtering.

### Claim 19 (depends on 17)

The non-transitory computer readable medium of claim 17, wherein the metric is indicative of a probability of query regression occurring in applying dictionary filtering.

### Claim 20 (depends on 17)

The non-transitory computer readable medium of claim 17, wherein the instructions further cause the processor to:
monitor, during performance of the dictionary filtering, query regression, wherein query regression is determined based on one or more of:
increase in processor time and duration,
a number of cloud input/output requests, and
a lack of eliminated row groups in the dictionary.
