Database indexing using structure-preserving dimensionality reduction to accelerate database operations
Embodiments of the present disclosure are directed to systems and methods for managing a database. In one or more examples, the system obtains input data comprising one or more data entries, where each data entry comprises one or more data items, and each data item comprises a field name and a field value. The system can generate a key-value set for each data item to obtain a plurality of key-value sets. Each key-value set includes at least a first key element comprising the field name of the respective data item and a second key element comprising the field value of the respective data item. The system can sort and store the plurality of key-value sets in the database. The system can further receive a query indicative of a field name or a field value, and generate, for display, an output based on retrieved key elements sets based on the query.
1. A method comprising:
obtaining input data comprising one or more data entries for storage in a database, wherein each data entry comprises one or more data items, and wherein each data item comprises a field name and a field value;
pre-processing a data item of the one or more data items by tokenizing a text entry of the data item into a plurality of n-grams wherein the data item is one of a plurality of data items;
in response to tokenizing the text entry, generating a key-value set for the data item including a first key element comprising the field name of the data item, and a second key element comprising the field value of the data item, wherein the field value includes the plurality of n-grams, wherein the key-value set is one of a plurality of key-value sets respectively generated for the plurality of data items, each with field values including respective pluralities of n-grams and wherein the generated key-value set is stored within the database according to a key-value map;
sorting the plurality of key-value sets based on first key elements of the plurality of key-value sets;
storing the sorted plurality of key-value sets in a database, wherein matching the query to the one of the n-grams in the key-value set comprises matching the query to one or more key-value sets containing the one of the n-grams;
receiving a query indicative a queried field value;
matching the query to one of the n-grams in the key-value set reflected in the key-value map;
retrieving one or more key elements corresponding to the key-value set stored within the database;
generating an output based on the one or more key elements; and
providing, for display, the output.
2. The method of claim 1 , wherein the plurality of key-value sets are stored in the database as a one-dimensional list.
3. The method of claim 1 , further comprising:
obtaining a user input indicative of an addition of a new data item;
generating a new key-value set based on the new data item;
retrieving the key-value map corresponding to the sorted plurality of key-value sets in the database;
adding the new key-value set to the key-value map;
sorting the key-value map to generate an updated key-value map; and
storing the updated key-value map in the database.
4. The method of claim 1 , further comprising:
obtaining a user input indicative of an update to a particular data item of the plurality of data items, the particular data item corresponding to a particular key-value set;
retrieving the particular key-value set from the database;
deleting the particular key-value set from the database;
generating a new key-value set based on the user input;
retrieving the key-value map corresponding to the sorted plurality of key-value sets in the database;
adding the new key-value set to the key-value map;
sorting the key-value map to generate an updated key-value map; and
storing the updated key-value map in the database.
5. The method of claim 1 , wherein the one or more data entries comprise a first data entry including a first data item, and wherein the first data item is an identifier item including an identifier field and an identifier value.
6. The method of claim 5 , wherein generating the plurality of key-value sets comprises obtaining a second key-value set for a second data item by: assigning a field name of the second data item as a first key element of the second key-value set; assigning a field value of the second data item as a second key element of the second key-value set; and assigning the identifier value of the first data item as a third key element of the second key-value set.
7. The method of claim 1 , wherein the query comprises a range query.
8. The method of claim 1 , wherein the plurality of n-grams comprises a plurality of trigrams.
9. The method of claim 1 , wherein retrieving the one or more key elements corresponding to the key-value set is performed without accessing a metadata table.
10. The method of claim 1 , further comprising:
determining a key-value set schema based on presence of predefined types of fields in the input data, wherein the key-value set is generated based on the key-value set schema.
11. The method of claim 10 , wherein determining the key-value set schema is also based on user input.
12. The method of claim 1 , wherein generating the output comprises averaging, summing, or a combination thereof.
13. A non-transitory computer-readable medium storing program instructions that, when executed by one or more processors of a computing system, cause the computing system to perform operations comprising:
obtaining input data comprising one or more data entries for storage in a database, wherein each data entry comprises one or more data items, and wherein each data item comprises a field name and a field value;
pre-processing a data item of the one or more data items by tokenizing a text entry of the data item into a plurality of n-grams wherein the data item is one of a plurality of data items;
in response to tokenizing the text entry, generating a key-value set for the data item including a first key element comprising the field name of the data item, and a second key element comprising the field value of the data item, wherein the field value includes the plurality of n-grams, wherein the key-value set is one of a plurality of key-value sets respectively generated for the plurality of data items, each with field values including respective pluralities of n-grams, and wherein the generated key-value set is stored within the database according to a key-value map;
sorting the plurality of key-value sets based on first key elements of the plurality of key-value sets;
storing the sorted plurality of key-value sets in a database, wherein matching the query to the one of the n-grams in the key-value set comprises matching the query to one or more key-value sets containing the one of the n-grams;
receiving a query indicative a queried field value;
matching the query to one of the n-grams in the key-value set reflected in the key-value map;
retrieving one or more key elements corresponding to the key-value set stored within the database;
generating an output based on the one or more key elements; and
providing, for display, the output.
14. The non-transitory computer-readable medium of claim 13 , wherein the plurality of n-grams comprises a plurality of trigrams.
15. The non-transitory computer-readable medium of claim 13 , the operations further comprising:
determining a key-value set schema based on presence of predefined types of fields in the input data, wherein the key-value set is generated based on the key-value set schema.
16. A computing system comprising:
a processor;
memory; and
program instructions, stored in the memory, that upon execution by the processor cause the computing system to perform operations comprising:
obtaining input data comprising one or more data entries for storage in a database, wherein each data entry comprises one or more data items, and wherein each data item comprises a field name and a field value;
pre-processing a data item of one or more data items by tokenizing a text entry of the data item into a plurality of n-grams wherein the data item is one of a plurality of data items;
in response to tokenizing the text entry, generating a key-value set for the data item including a first key element comprising the field name of the data item, and a second key element comprising the field value of the data item, wherein the field value includes the plurality of n-grams, wherein the key-value set is one of a plurality of key-value sets respectively generated for the plurality of data items, each with field values including respective pluralities of n-grams, and wherein the generated key-value set is stored within the database according to a key-value map;
sorting the plurality of key-value sets based on first key elements of the plurality of key-value sets;
storing the sorted plurality of key-value sets in a database, wherein matching the query to the one of the n-grams in the key-value set comprises matching the query to one or more key-value sets containing the one of the n-grams;
receiving a query indicative a queried field value;
matching the query to one of the n-grams in the key-value set reflected in the key-value map;
retrieving one or more key elements corresponding to the key-value set stored within the database;
generating an output based on the one or more key elements; and
providing, for display, the output.