# US 12,007,997 B2 · Metadata search via N-gram index

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

- Number: US 12,007,997 B2
- Document ID: US12007997B2
- Status: Granted
- Kind: B2
- Application number: 18/183,483
- Filed: 2023-03-14
- Published: 2023-07-06
- Granted: 2024-06-11
- Earliest claimed: 2021-10-29
- Assignees: Snowflake Inc.
- Applicants: Snowflake Inc.
- Inventors: Lin Chan; Tianyi Chen; Benoit Dageville; Yiming Kang; Jun Luo; Nithin Mahesh; Eric Robinson; Brian Smith
- Web page: https://patentgrep.com/patent/US12007997B2

## CPC

- G06F 16/24549: {Run-time optimisation}
- G06F 7/14: Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence
- G06F 16/2228: {Indexing structures}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 21/6218: {to a system of files or objects, e.g. local or distributed file system or database}
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

As described herein, a N-Gram index may be created and the search may be conducted using the index, which will lead to faster search results. The N-Gram index may also include partial N-Gram components to capture more relevant data. Moreover, as described herein, the search may also take into account recent log data that has not yet been indexed. Techniques for building an index store using log data and efficiently searching the index store and log data to process search requests are described herein.

## Claims

### Claim 1

A method comprising:
storing a log associated with an operation performed on a source table;
creating or updating an index record for a N-Gram index associated with the source table to generate a new version of the N-Gram index based on the log using a background process;
receiving, from a user, a search request including a search string; and
in response to the search request, processing the search request by performing steps including:
loading, in a log cache, log data associated with new logs not yet reflected in the N-Gram index;
retrieving index records matching the search string;
storing the matched index records in an index cache;
merging the log data in the log cache with the matched index records in the index cache to generate merged data; and
generating results of the search request based on the merged data, wherein processing the search request is a separate process than the background process used for updating the new logs in the N-gram index.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
updating metadata associated with the N-Gram index to facilitate searching of the N-Gram index based on the index record;
in response to the search request, loading index statistics of the N-Gram index;
retrieving metadata associated with the N-Gram index; and
performing post filtering of the merged log data and matched index records.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
performing a permission check on the merged data to determine that the user has access rights to the merged data.

### Claim 4 (depends on 1)

The method of claim 1, wherein the operation includes a delete operation, the method further comprising:
generating an index deletion log record associated with the delete operation;
marking an index record in the N-Gram index associated with the delete operation; and
based on at least one search associated with an older version of the N-Gram index being completed, deleting the marked index record based on the index deletion log record.

### Claim 5 (depends on 4)

The method of claim 4, wherein the marked index record is not deleted in a same transaction as the delete operation.

### Claim 6 (depends on 1)

The method of claim 1, wherein N-Gram index includes partial N-grams for at least last N characters of a name.

### Claim 7 (depends on 1)

The method of claim 1, wherein index records for the N-Gram index include a prefix portion indicating whether a corresponding index record is for a prefix substring.

### Claim 8 (depends on 1)

The method of claim 1, wherein the log includes an account ID, a chunk ID, a timestamp, a domain ID, and an entity ID.

### Claim 9 (depends on 1)

The method of claim 1, wherein each index record of the N-Gram index includes an account ID, a prefix portion, an index version, a domain ID, and a parent entity ID.

### Claim 10

A system comprising:
at least one hardware processor; and
at least one memory storing instructions that, when executed by the at least one hardware processor, cause the at least one hardware processor to perform operations comprising:
storing a log associated with an operation performed on a source table;
creating or updating an index record for a N-Gram index associated with the source table to generate a new version of the N-Gram index based on the log using a background process;
receiving, from a user, a search request including a search string; and
in response to the search request, processing the search request by performing steps including:
loading, in a log cache, log data associated with new logs not yet reflected in the N-Gram index;
retrieving index records matching the search string;
storing the matched index records in an index cache;
merging the log data in the log cache with the matched index records in the index cache to generate merged data; and
generating results of the search request based on the merged data, wherein processing the search request is a separate process than the background process used for updating the new logs in the N-gram index.

### Claim 11 (depends on 10)

The system of claim 10, the operations further comprising:
updating metadata associated with the N-Gram index to facilitate searching of the N-Gram index based on the index record;
in response to the search request, loading index statistics of the N-Gram index;
retrieving metadata associated with the N-Gram index; and
performing post filtering of the merged log data and matched index records.

### Claim 12 (depends on 10)

The system of claim 10, the operations further comprising:
performing a permission check on the merged data to determine that the user has access rights to the merged data.

### Claim 13 (depends on 10)

The system of claim 10, wherein the operation includes a delete operation, the operations further comprising:
generating an index deletion log record associated with the delete operation;
marking an index record in the N-Gram index associated with the delete operation; and
based on at least one search associated with an older version of the N-Gram index being completed, deleting the marked index record based on the index deletion log record.

### Claim 14 (depends on 13)

The system of claim 13, wherein the marked index record is not deleted in a same transaction as the delete operation.

### Claim 15 (depends on 10)

The system of claim 10, wherein N-Gram index includes partial N-grams for at least last N characters of a name.

### Claim 16 (depends on 10)

The system of claim 10, wherein index records for the N-Gram index include a prefix portion indicating whether a corresponding index record is for a prefix substring.

### Claim 17 (depends on 10)

The system of claim 10, wherein the log includes an account ID, a chunk ID, a timestamp, a domain ID, and an entity ID.

### Claim 18 (depends on 10)

The system of claim 10, wherein each index record of the N-Gram index includes an account ID, a prefix portion, an index version, a domain ID, and a parent entity ID.

### Claim 19

A machine-storage medium embodying instructions that, when executed by a machine, cause the machine to perform operations comprising:
storing a log associated with an operation performed on a source table;
creating or updating an index record for a N-Gram index associated with the source table to generate a new version of the N-Gram index based on the log using a background process;
receiving, from a user, a search request including a search string; and
in response to the search request, processing the search request by performing steps including:
loading, in a log cache, log data associated with new logs not yet reflected in the N-Gram index;
retrieving index records matching the search string;
storing the matched index records in an index cache;
merging the log data in the log cache with the matched index records in the index cache to generate merged data; and
generating results of the search request based on the merged data, wherein processing the search request is a separate process than the background process used for updating the new logs in the N-gram index.

### Claim 20 (depends on 19)

The machine-storage medium of claim 19, the operations further comprising:
updating metadata associated with the N-Gram index to facilitate searching of the N-Gram index based on the index record;
in response to the search request, loading index statistics of the N-Gram index;
retrieving metadata associated with the N-Gram index; and
performing post filtering of the merged log data and matched index records.

### Claim 21 (depends on 19)

The machine-storage medium of claim 19, the operations further comprising:
performing a permission check on the merged data to determine that the user has access rights to the merged data.

### Claim 22 (depends on 19)

The machine-storage medium of claim 19, wherein the operation includes a delete operation, further comprising:
generating an index deletion log record associated with the delete operation;
marking an index record in the N-Gram index associated with the delete operation; and
based on at least one search associated with an older version of the N-Gram index being completed, deleting the marked index record based on the index deletion log record.

### Claim 23 (depends on 22)

The machine-storage medium of claim 22, wherein the marked index record is not deleted in a same transaction as the delete operation.

### Claim 24 (depends on 19)

The machine-storage medium of claim 19, wherein N-Gram index includes partial N-grams for at least last N characters of a name.

### Claim 25 (depends on 19)

The machine-storage medium of claim 19, wherein index records for the N-Gran index include a prefix portion indicating whether a corresponding index record is for a prefix substring.

### Claim 26 (depends on 19)

The machine-storage medium of claim 19, wherein the log includes an account ID, a chunk ID, a timestamp, a domain ID, and an entity ID.

### Claim 27 (depends on 19)

The machine-storage medium of claim 19, wherein each index record of the N-Gram index includes an account ID, a prefix portion, an index version, a domain ID, and a parent entity ID.