# US 2024/0256543 A1 · Adaptive Approach to Lazy Materialization in Database Scans using Pushed Filters

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

- Number: US 2024/0256543 A1
- Document ID: US20240256543A1
- Status: Published application
- Kind: A1
- Application number: 18/160,861
- Filed: 2023-01-27
- Published: 2024-08-01
- Earliest claimed: 2023-01-27
- Assignees: Databricks, Inc.
- Applicants: Databricks, Inc.
- Inventors: Shoumik Palkar; Alexander Behm; Mostafa Mokhtar; Sriram Krishnamurthy
- Web page: https://patentgrep.com/patent/US20240256543A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 11/3409: {for performance assessment}
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed herein is a method for determining whether to apply a lazy materialization technique to a query run. A data processing service receives a request to perform a query identifying a filter column and a non-filter column in a columnar database. The data processing service accesses a first task of contiguous rows in the filter column from a cloud-based object storage. The data processing service applies a filter defined by the query to the first task. The data processing service generates filter results for the first task that may include a percentage of the first task discarded and a run-time. The data processing service determines, based on the filter results for the first task, a likelihood value that indicates a likelihood of gaining a performance benefit by applying the lazy materialization technique to a second task of the query.

## Claims

### Claim 1

A method comprising:
receiving a request to perform a query, the query identifying a filter column and a non-filter column in a columnar database having a plurality of columns and a plurality of rows, the plurality of rows comprising at least a first task of contiguous rows in the filter column of the columnar database and a second task of contiguous rows in the filter column of the columnar database;
accessing, from a cloud-based object storage, the first task of contiguous rows in the filter column of the columnar database;
applying a filter defined by the query to the first task of contiguous rows using a first approach;
generating filter results for the first task of contiguous rows, the filter results comprising an amount of data discarded after applying the filter to the first task of contiguous rows;
determining, based on the filter results for the first task of contiguous rows, a likelihood value indicating a likelihood of gaining a performance benefit by applying a second approach to the second task of contiguous rows in the filter column of the columnar database, wherein the second approach is a lazy materialization technique; and
applying the second approach to the second task of contiguous rows based on the likelihood value meeting or exceeding a threshold value.

### Claim 2

(canceled)

### Claim 3 (depends on 1)

The method of claim 1, wherein the likelihood value is calculated based on an equation:
EstRuntime
=
FractionFilterBytes
×
P
Success
+
Penalty
×
(
1
-
P
Success
)
.

### Claim 4 (depends on 1)

The method of claim 1, wherein the filter results include a run-time.

### Claim 5 (depends on 1)

The method of claim 1, wherein the likelihood value is generated by a machine-learned cost model trained on a plurality of query runs with known filter results and estimated run-times.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
applying the first approach to the second task of the query based on the likelihood value being below the threshold value.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
generating filter results from the second task of the query;
determining, based on the filter results for the second task, a second likelihood value indicating a likelihood of gaining a performance benefit by applying the second approach to a third task of the query, the third task associated with a third set of contiguous rows of the filter column; and
applying the second approach to the third task based on the likelihood value meeting or exceeding the threshold value.

### Claim 8

A system comprising:
at least one processor configured to execute instructions;
at least one memory comprising stored instructions, the instructions when executed cause the at least one processor to:
receive a request to perform a query, the query identifying a filter column and a non-filter column in a columnar database having a plurality of columns and a plurality of rows, the plurality of rows comprising at least a first task of contiguous rows in the filter column of the columnar database and a second task of contiguous rows in the filter column of the columnar database;
access, from a cloud-based object storage, the first task of contiguous rows in the filter column of the columnar database;
apply a filter defined by the query to the first task of contiguous rows using a first approach;
generate filter results for the first task of contiguous rows, the filter results comprising an amount of data discarded after applying the filter to the first task of contiguous rows;
determine, based on the filter results for the first task of contigupus rows, a likelihood value indicating a likelihood of gaining a performance benefit by applying a second approach to the second task of contiguous rows in the filter column of the columnar database, wherein the second approach is a lazy materialization technique; and
apply the second approach to the second task of contiguous rows based on the likelihood value meeting or exceeding a threshold value.

### Claim 9

(canceled)

### Claim 10 (depends on 8)

The system of claim 8, wherein the likelihood value is calculated based on an equation:
EstRuntime
=
FractionFilterBytes
×
P
Success
+
Penalty
×
(
1
-
P
Success
)
.

### Claim 11 (depends on 8)

The system of claim 8, wherein the filter results include a run-time.

### Claim 12 (depends on 8)

The system of claim 8, wherein the likelihood value is generated by a machine-learned cost model trained on a plurality of query runs with known filter results and estimated run-times.

### Claim 13 (depends on 8)

The system of claim 8, wherein the at least one memory further comprises instructions that when executed causes the at least one processor to:
apply the first approach to the second task of the query based on the likelihood value being below the threshold value.

### Claim 14 (depends on 8)

The system of claim 8, wherein the at least one memory further comprises instructions that when executed causes the at least one processor to:
generate filter results from the second task of the query;
determine, based on the filter results for the second task, a second likelihood value indicating a likelihood of gaining a performance benefit by applying the second approach to a third task of the query, the third task associated with a third set of contiguous rows of the filter column; and
apply the second approach to the third task based on the likelihood value meeting or exceeding the threshold value.

### Claim 15

A non-transitory computer readable medium having instructions encoded thereon that, when executed by a processor, cause at least one processor to:
receive a request to perform a query, the query identifying a filter column and a non-filter column in a columnar database having a plurality of columns and a plurality of rows, the plurality of rows comprising at least a first task of contiguous rows in the filter column of the columnar database and a second task of contiguous rows in the filter column of the columnar database;
access, from a cloud-based object storage, the first task of contiguous rows in the filter column of the columnar database;
apply a filter defined by the query to the first task of contiguous rows using a first approach;
generate filter results for the first task of contiguous rows, the filter results comprising an amount of data discarded after applying the filter to the first task of contiguous rows;
determine, based on the filter results for the first task of contiguous rows, a likelihood value indicating a likelihood of gaining a performance benefit by applying a second approach to the second task of contiguous rows in the filter column of the columnar database, wherein the second approach is a lazy materialization technique; and
apply the second approach to the second task of contiguous rows based on the likelihood value meeting or exceeding a threshold value.

### Claim 16

(canceled)

### Claim 17 (depends on 15)

The non-transitory computer readable medium of claim 15,
wherein the filter results include a run-time.

### Claim 18 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein the likelihood value is generated by a machine-learned cost model trained on a plurality of query runs with known filter results and estimated run-times.

### Claim 19 (depends on 15)

The non-transitory computer readable medium of claim 15, further comprising stored instructions that when executed cause the at least one processor to:
apply the first approach to the second task of the query based on the likelihood value being below the threshold value.

### Claim 20 (depends on 15)

The non-transitory computer readable medium of claim 15, further comprising instructions that when executed cause the at least one processor to:
generate filter results from the second task of the query;
determine, based on the filter results for the second task, a second likelihood value indicating a likelihood of gaining a performance benefit by applying the second approach to a third task of the query, the third task associated with a third set of contiguous rows of the filter column; and
apply the second approach to the third task based on the likelihood value meeting or exceeding the threshold value.

### Claim 21 (depends on 1)

The method of claim 1, wherein the first approach is an eager technique.

### Claim 22 (depends on 8)

The system of claim 8, wherein the first approach is an eager technique.

### Claim 23 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein the first approach is an eager technique.
