Optimized match keys for fields with prefix structure
The system tokenizes values stored by records' fields, creates trie from tokenized values, each branch labeled with tokenized value, each node storing count indicating number of records associated with tokenized value sequence beginning from trie root. The system tokenizes value stored by record field, identifies nodes, beginning from trie root, corresponding to token value sequence associated with tokenized value, until node is identified that stores count that is less than node threshold. The system identifies branch sequence comprising each identified node as record's key, and associates key with node storing count less than node threshold, and record with key. The system tokenizes prospective value stored by prospective record's field, identifies nodes, beginning from trie root, corresponding to another token value sequence associated with tokenized prospective value, until another node is identified that stores another count that is less than node threshold. The system identifies other node's key as prospective record's key, identifies existing record that matches prospective record by using prospective record's key.
1. A system for optimized match keys for fields with prefix structure, the system comprising:
one or more processors; and
a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to:
tokenize, by a database system, values stored in a field by a plurality of records;
create, by the database system, a trie from the tokenized values, each branch in a trie labeled with one of the tokenized values, each node storing a count indicating a number of the plurality of records associated with a tokenized value sequence beginning from a root of the trie;
tokenize, by the database system, a value stored in the field by one of the plurality of records;
identify, by the database system, each node, beginning from the root of the trie, corresponding to a token value sequence associated with the tokenized value, until a node is identified that stores a count less than a node threshold;
identify, by the database system, a branch sequence comprising each identified node as a key for the record;
associate, by the database system, the key with the node storing the count less than the node threshold, and the record with the key;
tokenize, by the database system, a prospective value stored in the field by a prospective record;
identify, by the database system, each node, beginning from the root of the trie, corresponding to another token value sequence associated with a tokenized prospective value, until another node is identified that stores another count that is less than the node threshold;
identify, by the database system, a key associated with the other node as a key for the prospective record; and
identify, by the database system, using the key for the prospective record, an existing record of the plurality of records that matches the prospective record.
2. The system of claim 1 , wherein identifying the key associated with the other node as the key for the prospective record comprises identifying another key associated with another corresponding field in the prospective record as the other key for the prospective record, and identifying the existing record that matches the prospective record comprises combining records associated with the key for the prospective record with other records associated with the other key associated with the other corresponding field in the prospective record.
3. The system of claim 2 , wherein combining the records associated with the key with the other records associated with the other key comprises:
determining whether a sum of a count of the records associated with the key with another count of the records associated with the other key exceeds a record threshold;
using a Boolean AND function for combining the records associated with the key with the other records associated with the other key in response to a determination that the sum of the count of the records associated with the key with the other count of the records associated with the other key exceeds the record threshold; and
using a Boolean OR function for combining the records associated with the key with the other records associated with the other key in response to a determination that the sum of the count of the records associated with the key with the other count of the records associated with the other key does not exceed the record threshold.
4. The system of claim 1 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a transposed key for the record by exchanging adjacent tokens in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a transposed key for the prospective record by exchanging adjacent tokens in the key for the prospective record.
5. The system of claim 1 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a substitution based key for the record by substituting a placeholder for a token in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a substitution based key for the prospective record by substituting a placeholder for a token in the key for the prospective record.
6. The system of claim 1 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating an insertion based key for the record by inserting a placeholder in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating an insertion based key for the prospective record by inserting a placeholder in the key for the prospective record.
7. The system of claim 1 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a deletion based key for the record by deleting a token in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a deletion based key for the prospective record by deleting a token in the key for the prospective record.
8. A computer program product comprising computer-readable program code to be executed by one or more processors when retrieved from a non-transitory computer-readable medium, the program code including instructions to:
tokenize, by a database system, values stored in a field by a plurality of records;
create, by the database system, a trie from the tokenized values, each branch in a trie labeled with one of the tokenized values, each node storing a count indicating a number of the plurality of records associated with a tokenized value sequence beginning from a root of the trie;
tokenize, by the database system, a value stored in the field by one of the plurality of records;
identify, by the database system, each node, beginning from the root of the trie, corresponding to a token value sequence associated with the tokenized value, until a node is identified that stores a count less than a node threshold;
identify, by the database system, a branch sequence comprising each identified node as a key for the record;
associate, by the database system, the key with the node storing the count less than the node threshold, and the record with the key;
tokenize, by the database system, a prospective value stored in the field by a prospective record;
identify, by the database system, each node, beginning from the root of the trie, corresponding to another token value sequence associated with a tokenized prospective value, until another node is identified that stores another count that is less than the node threshold;
identify, by the database system, a key associated with the other node as a key for the prospective record; and
identify, by the database system, using the key for the prospective record, an existing record of the plurality of records that matches the prospective record.
9. The computer program product of claim 8 , wherein identifying the key associated with the other node as the key for the prospective record comprises identifying another key associated with another corresponding field in the prospective record as the other key for the prospective record, and identifying the existing record that matches the prospective record comprises combining records associated with the key for the prospective record with other records associated with the other key associated with the other corresponding field in the prospective record.
10. The computer program product of claim 9 , wherein combining the records associated with the key with the other records associated with the other key comprises:
determining whether a sum of a count of the records associated with the key with another count of the records associated with the other key exceeds a record threshold;
using a Boolean AND function for combining the records associated with the key with the other records associated with the other key in response to a determination that the sum of the count of the records associated with the key with the other count of the records associated with the other key exceeds the record threshold; and
using a Boolean OR function for combining the records associated with the key with the other records associated with the other key in response to a determination that the sum of the count of the records associated with the key with the other count of the records associated with the other key does not exceed the record threshold.
11. The computer program product of claim 8 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a transposed key for the record by exchanging adjacent tokens in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a transposed key for the prospective record by exchanging adjacent tokens in the key for the prospective record.
12. The computer program product of claim 8 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a substitution based key for the record by substituting a placeholder for a token in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a substitution based key for the prospective record by substituting a placeholder for a token in the key for the prospective record.
13. The computer program product of claim 8 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating an insertion based key for the record by inserting a placeholder in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating an insertion based key for the prospective record by inserting a placeholder in the key for the prospective record.
14. The computer program product of claim 8 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a deletion based key for the record by deleting a token in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a deletion based key for the prospective record by deleting a token in the key for the prospective record.
15. A method comprising:
tokenizing, by a database system, values stored in a field by a plurality of records;
creating, by the database system, a trie from the tokenized values, each branch in a trie labeled with one of the tokenized values, each node storing a count indicating a number of the plurality of records associated with a tokenized value sequence beginning from a root of the trie;
tokenizing, by the database system, a value stored in the field by one of the plurality of records;
identifying, by the database system, each node, beginning from the root of the trie, corresponding to a token value sequence associated with the tokenized value, until a node is identified that stores a count less than a node threshold;
identifying, by the database system, a branch sequence comprising each identified node as a key for the record;
associating, by the database system, the key with the node storing the count less than the node threshold, and the record with the key;
tokenizing, by the database system, a prospective value stored in the field by a prospective record;
identifying, by the database system, each node, beginning from the root of the trie, corresponding to another token value sequence associated with a tokenized prospective value, until another node is identified that stores another count that is less than the node threshold;
identifying, by the database system, a key associated with the other node as a key for the prospective record; and
identifying, by the database system, using the key for the prospective record, an existing record of the plurality of records that matches the prospective record.
16. The method of claim 15 , wherein identifying the key associated with the other node as the key for the prospective record comprises identifying another key associated with another corresponding field in the prospective record as the other key for the prospective record, and identifying the existing record that matches the prospective record comprises combining records associated with the key for the prospective record with other records associated with the other key associated with the other corresponding field in the prospective record, wherein combining the records associated with the key with the other records associated with the other key comprises:
determining whether a sum of a count of the records associated with the key with another count of the records associated with the other key exceeds a record threshold;
using a Boolean AND function for combining the records associated with the key with the other records associated with the other key in response to a determination that the sum of the count of the records associated with the key with the other count of the records associated with the other key exceeds the record threshold; and
using a Boolean OR function for combining the records associated with the key with the other records associated with the other key in response to a determination that the sum of the count of the records associated with the key with the other count of the records associated with the other key does not exceed the record threshold.
17. The method of claim 15 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a transposed key for the record by exchanging adjacent tokens in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a transposed key for the prospective record by exchanging adjacent tokens in the key for the prospective record.
18. The method of claim 15 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a substitution based key for the record by substituting a placeholder for a token in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a substitution based key for the prospective record by substituting a placeholder for a token in the key for the prospective record.
19. The method of claim 15 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating an insertion based key for the record by inserting a placeholder in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating an insertion based key for the prospective record by inserting a placeholder in the key for the prospective record.
20. The method of claim 15 , wherein at least one of identifying the branch sequence comprising each identified node as the key for the record comprises creating a deletion based key for the record by deleting a token in the key for the record, and identifying the key associated with the other node as the key for the prospective record comprises creating a deletion based key for the prospective record by deleting a token in the key for the prospective record.