Granted Patent B2

US 12,561,303 · App. 18/772,758 · Granted Feb 24, 2026

Inventors: Bart Samwel (Oegstgeest, NL); Prakhar Jain (Sunnyvale, CA)

Assignee: Databricks, Inc.

G06F16/2246G06F16/278G06F16/285

Abstract

Claims (73)

1 . A computer system, comprising:

one or more processors; and

one or more computer-readable mediums storing instructions that, when executed by the one or more processors, cause the one or more processors to:

access a set of data having a set of keys in a data space;

identify a first splitting location corresponding to a value of a first key of the set of keys;

split the set of data at the first splitting location to generate one subset of data and another subset of data;

for the one subset of data,

identify a second splitting location corresponding to a value of a second key of the set of keys, and

split the one subset of data at the second splitting location to generate a first subset of data and a second subset of data;

for the another subset of data,

identify a third splitting location corresponding to another value of the second key, and

split the another subset of data at the third splitting location to

generate a third subset of data and a fourth subset of data;

store each of the first subset, the second subset, the third subset, and the fourth subset of data into a respective file to create a set of files, the set of files stored in a storage system;

store metadata associated with each of the set of files, the metadata including boundary information obtained from at least the first splitting location, the second splitting location, or the third splitting location in the data space, and wherein the boundary information for each file indicates boundaries for the set of keys that encompass data included in the file;

receive, from a computer system, a query requesting records with a particular range of values with respect to the set of keys;

read the metadata for the set of files to identify a subset of files in the set of files that have boundaries for the set of keys that overlap with the particular range of values for the query; and

execute, by the computer system, the query to access only the subset of files from the storage system to retrieve records from the subset of files that match the particular range of values for the query.

2 . The computer system of claim 1 , wherein the instructions further cause the one or more processors to:

identify an additional splitting location corresponding to another value of the first key; and

splitting the set of data at the additional splitting location to generate an additional subset of data, wherein values of the first key for the additional subset of data are between the value and the another value of the first key.

3 . The computer system of claim 1 , wherein

the boundary information for each file includes a minimum value and a maximum value for the respective keys associated with each file.

4 . The computer system of claim 1 , wherein boundaries for files of the set of files are non-overlapping.

5 . The computer system of claim 1 , wherein the instructions further cause the one or more processors to determine a number of splits to perform with respect to the first key before a split is performed with respect to another key of the set of keys, the number of splits being determined based at least in part on a target size of each of the set of files.

6 . The computer system of claim 1 , wherein the set of data is split with respect to the first key more times than the set of data is split with respect to another key of the set of keys.

7 . The computer system of claim 1 , wherein at least one of the first split location, the second split location, and the third split location is determined based at least in part on a distribution of a plurality of records comprised in the set of data.

8 . The computer system of claim 7 , wherein at least one of the first split location and the second split location is determined based on a plurality of weightings respectively associated with a plurality of records comprised in the set of data.

9 . A method, comprising:

accessing a set of data having a set of keys in a data space;

identifying a first splitting location corresponding to a value of a first key of the set of keys;

splitting the set of data at the first splitting location to generate one subset of data and another subset of data;

for the one subset of data:

identifying a second splitting location corresponding to a value of a second key of the set of keys, and

splitting the one subset of data at the second splitting location to generate a first subset of data and a second subset of data;

for the another subset of data:

identifying a third splitting location corresponding to another value of the second key, and

splitting the another subset of data at the third splitting location to generate a third subset of data and a fourth subset of data;

storing each of the first subset, the second subset, the third subset, and the fourth subset of data into a respective file to create a set of files, the set of files stored in a storage system;

storing metadata associated with each of the set of files, the metadata including boundary information obtained from at least the first splitting location, the second splitting location, or the third splitting location in the data space, and wherein the boundary information for each file indicates boundaries for the set of keys that encompass data included in the file;

receiving, from a computer system, a query requesting records with a particular range of values with respect to the set of keys;

reading the metadata for the set of files to identify a subset of files in the set of files that have boundaries for the set of keys that overlap with the particular range of values for the query; and

executing, by the computer system, the query to access only the subset of files from the storage system to retrieve records from the subset of files that match the particular range of values for the query.

10 . The method of claim 9 , further comprising:

identifying an additional splitting location corresponding to another value of the first key; and

splitting the set of data at the additional splitting location to generate an additional subset of data, wherein values of the first key for the additional subset of data are between the value and the another value of the first key.

11 . The method of claim 9 ,

wherein the boundary information for each file includes a minimum value and a maximum value for the respective keys associated with each of the set of files.

12 . The method of claim 9 , wherein boundaries for files of the set of files are non-overlapping.

13 . The method of claim 9 , further comprising determining a number of splits to perform with respect to the first key before a split is performed with respect to another key of the set of keys, the number of splits being determined based at least in part on a target size of each of the set of files.

14 . The method of claim 9 , wherein the set of data is split with respect to the first key more times than the set of data is split with respect to another key of the set of keys.

15 . The method of claim 9 , wherein at least one of the first split location, the second split location, and the third split location is determined based at least in part on a distribution of a plurality of records comprised in the set of data.

16 . The method of claim 15 , wherein at least one of the first split location and the second split location is determined based on a plurality of weightings respectively associated with a plurality of records comprised in the set of data.

17 . A computer-readable medium storing instructions that, when executed by one or more processors, cause the one or more processors to:

one or more processors; and

one or more computer-readable mediums storing instructions that, when executed by the one or more processors, cause the one or more processors to:

access a set of data having a set of keys in a data space;

identify a first splitting location corresponding to a value of a first key of the set of keys;

split the set of data at the first splitting location to generate one subset of data and another subset of data;

for the one subset of data,

identify a second splitting location corresponding to a value of a second key of the set of keys, and

split the one subset of data at the second splitting location to generate a first subset of data and a second subset of data;

for the another subset of data,

identify a third splitting location corresponding to another value of the second key, and

split the another subset of data at the third splitting location to generate a third subset of data and a fourth subset of data;

store each of the first subset, the second subset, the third subset, and the fourth subset of data into a respective file to create a set of files, the set of files stored in a storage system;

store metadata associated with each of the set of files, the metadata including boundary information obtained from at least the first splitting location, the second splitting location, or the third splitting location in the data space, and wherein the boundary information for each file indicates boundaries for the set of keys that encompass data included in the file;

receive, from a computer system, a query requesting records with a particular range of values with respect to the set of keys;

read the metadata for the set of files to identify a subset of files in the set of files that have boundaries for the set of keys that overlap with the particular range of values for the query; and

execute, by the computer system, the query to access only the subset of files from the storage system to retrieve records from the subset of files that match the particular range of values for the query.

18 . The computer-readable medium of claim 17 , wherein the instructions further cause the one or more processors to:

identify an additional splitting location corresponding to another value of the first key; and

splitting the set of data at the additional splitting location to generate an additional subset of data, wherein values of the first key for the additional subset of data are between the value and the another value of the first key.

Assignments (2)

Continuity (2)

References Cited (12)