Back to results
US 12,613,854 B2Granted
Split retrieval structures for storing and querying data
OwnerJulian Reichingerinventor
Life of this patent
Estimating the term…
Abstract
A computer-implemented method is presented for storing and querying records from a data segment. The objective of the disclosure is to find computer-implemented methods for storing and querying records from a data segment that are fast and space efficient storing and querying of APM data stored in a segmented database.
Claims26
A computer-implemented method for storing records from a data segment, comprising:
- receiving, by a computer processor, a data segment comprised of a plurality of data records, where each of the data records in the plurality of data records includes one or more key-value pairs, wherein the plurality of data records is organized into one or more batches, where each of the one or more batches is assigned a batch identifier;
- defining a data structure having a retrieval section and a data section;
- for each of the plurality of data records, tokenizing the key-value pairs in a given data record, thereby creating a list of tokens;
- storing the list of tokens in the retrieval section of the data structure, where each entry in the list of tokens includes a given token and a list of batch identifiers for the batches which contain the given token;
- compressing data records in each of the one or more batches;
- and
- storing the compressed data records for each of the one or more batches in the data section of the data structure.
4 more elements
A computer-implemented method for querying records from a data segment, comprising:
- receiving, by a computer processor, a value for a query of a data segment comprised of a plurality of data records, where each of the data records in the plurality of data records includes one or more key-value pairs, the plurality of data records is organized into one or more batches and each of the one or more batches is assigned a batch identifier;
- loading a first list of tokens from a membership section of a data store;
- determining whether the value from the query is present in the first list of tokens;
- loading a first list of batch identifiers from a posting section of the data store in response to a determination that the value from the query is present in the first list of tokens;
- identifying a first posting list in the first list of batch identifiers from the posting section, where the first posting list are for batches which contain the value from the query;
- loading at least one batch identified in the first posting list of batch identifiers from a data section of the data store;
- uncompressing the at least one batch;
- identifying a record having a token matching the value in the at least one batch;
- and
- outputting the record.
7 more elements
A computer-implemented method for querying records from a data segment, comprising:
- receiving, by a computer processor, a value for a query of a data segment comprised of a plurality of data records, where each of the data records in the plurality of data records includes one or more key-value pairs, the plurality of data records is organized into one or more batches and each of the one or more batches is assigned a batch identifier;
- loading a first list of tokens from a low cardinality section of a data store, where tokens in the first list of tokens represent values in data records having low cardinality and each entry in the first list of tokens includes a given token and a list of batch identifiers for the batches which contain the given token;
- determining whether the value from the query is present in the first list of tokens;
- retrieving a particular list of batch identifiers from the first list of tokens, where the particular list of batch identifiers corresponds to a token matching the value from the query;
- retrieving one or more data records from a data section of the data store using the particular list of batch identifiers, where the retrieval of the one or more data records is in response to a determination that the value from the query is present in the first list of tokens;
- and
- loading a second list of tokens from a high cardinality section of the data store in response to a determination that the value from the query is absent in the first list of tokens, where tokens in the second list of tokens represent values in data records having high cardinality.
4 more elements
Dependencies are inferred from the claim text.