Database layered filtering

Patent metadata

Field	Value
Publication number	US-12153603-B2
Application number	US-202218064112-A
Country	US
Kind code	B2
Filing date	Dec 9, 2022
Priority date	Dec 9, 2022
Publication date	Nov 26, 2024
Grant date	Nov 26, 2024

Abstract

Techniques are disclosed pertaining to layered filtering. A computer system may store records in a hierarchy of levels. The computer system may receive a request to perform a key range search to locate records that fall within a key range and satisfy selection criteria. The computer system may perform the key range search. As part of processing a particular level, the computer system may receive a first set of records associated with another level and select a second set of records from the particular level that fall within the key range and satisfy the selection criteria. The computer system may merge the first and second sets of records into a third set of records, which may include not inserting, into the third set, any record of the first set of records for which there is a newer version in the particular level that does not satisfy the selection criteria.

First claim

What is claimed is:

1. A method, comprising:
storing, by a computer system, records in a log-structured merge tree (LSM tree) that comprises a hierarchy of levels;
receiving, by the computer system, a request to perform a key range search to locate records of the LSM tree that fall within a specified key range and satisfy selection criteria; and
performing, by the computer system, the key range search, including for a particular level of the hierarchy of levels:
receiving a first set of records associated with a lower level of the hierarchy than the particular level, wherein the lower level stores a greater number of records than the particular level;
selecting a second set of records of the particular level that fall within the specified key range and satisfy the selection criteria; and
merging the first set of records with the second set of records to generate a third set of records, wherein the merging includes performing a merge operation to not insert, into the third set of records, any record of the first set of records for which there is a newer version in the particular level that does not satisfy the selection criteria.

2. The method of claim 1 , wherein the first set of records includes records whose keys fall within the specified key range but were not filtered based on the selection criteria.

3. The method of claim 1 , further comprising:
obtaining, by the computer system, a total set of records that includes records returned from the hierarchy of levels;
generating, by the computer system, a result set of records from the total set of records by removing, from the total set of records, any record that does not satisfy the selection criteria; and
returning, by the computer system, the result set of records to an issuer of the request.

4. The method of claim 3 , wherein the total set of records further includes records returned from an in-memory cache of the computer system and that fall within the specified key range and satisfy the selection criteria, wherein the in-memory cache is distinct from the LSM tree.

5. The method of claim 1 , wherein the request to perform the key range search specifies a column projection to be applied, and wherein the performing of the key range search for the particular level includes applying the column projection to the second set of records.

6. The method of claim 1 , wherein the particular level is associated with a set of probabilistic structures that indicates whether a record is not included in the particular level for a key, and wherein the performing of the merge operation includes:
identifying, based on the set of probabilistic structures, a particular record of the first set of records to potentially not include in the third set of records; and
searching the particular level for a record that corresponds to a key of the particular record.

7. The method of claim 6 , wherein the performing of the merge operation includes, in response to locating a record for the key, not including the particular record in the third set of records.

8. The method of claim 1 , wherein the storing includes inserting a record at a top level of the hierarchy of levels of the LSM tree, and the method further comprising:
merging, by the computer system, the record through levels of the hierarchy of levels over time, wherein the particular level includes newer records than the lower level.

9. The method of claim 1 , wherein the performing of the key range search includes executing, for each of the hierarchy of levels, a set of scan processes operable to produce a set of records to be returned for that level, wherein a set of scan processes for the particular level is operable to perform the selecting and the merging and to provide the third set of records to a set of scan processes of a higher level of the hierarchy than the particular level.

10. The method of claim 1 , wherein the first and second sets of records include a respective record for a particular key, and wherein the merging includes inserting, into the third set of records, the record of the second set that is associated with the particular key and not the record of the first set that is associated with the particular key.

11. A non-transitory computer readable medium having program instructions stored thereon that are executable by a computer system to cause the computer system to perform operations comprising:
storing records in a hierarchy of levels of a database;
receiving a request to perform a key range search to locate records of the database that fall within a specified key range and satisfy selection criteria; and
performing the key range search, including for a particular level of the hierarchy of levels:
receiving a first set of records associated with a lower level of the hierarchy than the particular level, wherein the lower level stores a greater number of records than the particular level;
selecting a second set of records of the particular level that fall within the specified key range and satisfy the selection criteria; and
merging the first set of records with the second set of records to generate a third set of records, wherein the merging includes performing a merge operation to not insert, into the third set of records, any record of the first set of records for which there is a newer version in the particular level that does not satisfy the selection criteria.

12. The non-transitory computer readable medium of claim 11 , wherein the performing of the key range search includes:
receiving a total set of records associated with a top level of the hierarchy of levels, wherein the total set of records incorporates records from lower levels of the hierarchy of levels;
generating, by the computer system, a result set of records by removing, from the total set of records, any record that does not satisfy the selection criteria; and
returning, by the computer system, the result set of records to a requestor of the request to perform the key range search.

13. The non-transitory computer readable medium of claim 11 , wherein performing the key range search for the lower level associated with the first set of records includes:
selecting records of the lower level that fall within the specified key range; and
generating the first set of records by applying a restricted filter operation to the selected records that removes, from the selected records, only those records that are identified as initial records and do not satisfy the selection criteria.

14. The non-transitory computer readable medium of claim 11 , wherein the performing of the merge operation includes:
identifying, based on a set of Bloom filters, a particular record of the first set of records whose key potentially corresponds to a record in the particular level;
searching the particular level for a record that corresponds to the key of the particular record; and
in response to locating a record for the key in the particular level, not including the particular record in the third set of records.

15. The non-transitory computer readable medium of claim 11 , wherein the merging includes inserting, into the third set of records, a first particular record of the second set of records that supersedes a second particular record of the first set of records, wherein the second particular record is not included in the third set of records.

16. A system, comprising:
at least one processor; and
a memory having program instructions stored thereon that are executable by the at least one processor to perform operations comprising:
storing records in a log-structured merge tree (LSM tree) that comprises a hierarchy of

Assignees

• Salesforce Inc

Inventors

• Helland Patrick James
• Dehaan David Edward

Classifications

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/24573

  using data annotations, e.g. user-defined metadata · CPC title

• G06F16/282 Primary

  Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes · CPC title