Virtual split dictionary for search optimization

• US 10,726,005 B2
• Filed: 06/25/2014
• Issued: 07/28/2020
• Est. Priority Date: 06/25/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Verma, Sudhir, Verma, Pravesh, Bhatnagar, Vidur Sailendra
• Primary Examiner(s): Torgrimson, Tyler J
• Application Number:
  US14/314,032
• Publication Number:
  US 20150379073A1
• Time in Patent Office: 2,225 Days
• Field of Search: 707693, 707695, 707715
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

An attribute vector including value identifiers and corresponding to a dictionary structure is identified. A dictionary type encoding structure is generated by virtually partitioning the dictionary structure. The dictionary type encoding structure may include multiple dictionary types. Based on the dictionary encoding structure, the attribute vector may be split to generate multiple attribute vector blocks that may be identified by block transition indices. Based on the dictionary types in the dictionary encoding structure, the value identifiers in the attribute vector blocks are rearranged. Such a rearrangement optimizes the attribute vector for searching the value identifiers.

Claims

1. A computer implemented method comprising:

generating a dictionary including a plurality of value identifiers mapped to a plurality of attribute values, respectively, wherein the plurality of attribute values are identified from data records in a data structure;

modifying the data records in the data structure by replacing an attribute value of each data record with a corresponding value identifier included in the dictionary, wherein the modification comprises mapping at least two data records that have a same attribute value to a same value identifier;

partitioning the modified data structure into a plurality of split data structures and rearranging data records among the split data structures based on the value identifiers such that each rearranged split data structure stores data records having a mutually exclusive subset of value identifiers;

in response to a query being received for an attribute, identifying a value identifier mapped to the attribute in the dictionary, identifying a rearranged split data structure storing the identified value identifier from among the plurality of rearranged split data structures, and executing the query on data records in the identified rearranged split data structure to generate search results; and

outputting information for display on a display device based on the search results.

2. The computer implemented method of claim 1, further comprising:

determining a transition index corresponding to one or more block transition indices within the rearranged split data structures.

3. The computer implemented method of claim 1, wherein the dictionary includes a dictionary structure that comprises one or more dictionary types which correspond to one or more virtual partitions in the data structure.

4. The computer implemented method of claim 3, wherein the dictionary structure includes:

a dictionary type identifier indicating the plurality of rearranged split data structures;

one or more start indices corresponding to the plurality of rearranged split data structures; and

one or more end indices corresponding to the plurality of rearranged split data structures.

5. The computer implemented method of claim 1, wherein the rearranging the data records comprises swapping two data records having two different value identifiers stored in two different split data structures.

6. The computer implemented method of claim 1, wherein the query comprises one or more of an exact match query, a range query, and a query including two or more attributes combined by one or more Boolean operators.

7. A computer system comprising:

a processor; and

one or more memory devices communicatively coupled with the processor and the one or more memory devices storing instructions to;

generate a dictionary including a plurality of value identifiers mapped to a plurality of attribute values, respectively, wherein the plurality of attribute values are identified from data records in a data structure;

modify the data records in the data structure by replacing an attribute value of each data record with a corresponding value identifier included in the dictionary, wherein the modification comprises mapping at least two data records that have a same attribute value to a same value identifier;

partition the modified data structure into a plurality of split data structures and rearrange data records among the split data structures based on the value identifiers such that each rearranged split data structure stores data records having a mutually exclusive subset of value identifiers;

in response to a query being received for an attribute, identify a value identifier mapped to the attribute in the dictionary, identify a rearranged split data structure storing the identified value identifier from among the plurality of rearranged split data structures, and execute the query on data records in the identified rearranged split data structure to generate search results; and

output information for display on a display device based on the search results.

8. The computer system of claim 7, wherein the processor is further configured to determine a transition index corresponding to one or more block transition indices within the rearranged split data structures.

9. The computer system of claim 7, wherein the dictionary includes a dictionary structure that comprises one or more dictionary types which correspond to one or more virtual partitions in the data structure.

10. The computer system of claim 9, wherein the dictionary structure includes:

a dictionary type identifier indicating the plurality of rearranged split data structures;

one or more start indices corresponding to the plurality of rearranged split data structures; and

one or more end indices corresponding to the plurality of rearranged split data structures.

11. The computer system of claim 7, wherein the rearranging the data records comprises swapping two data records having two different value identifiers stored in two different split data structures.

12. The computer system of claim 7, wherein the query comprises one or more of an exact match query, a range query, and a query including two or more attributes combined by one or more Boolean operators.

13. A non-transitory computer readable storage medium tangibly storing instructions, which when executed by a computer, cause the computer to execute operations comprising:

generate a dictionary including a plurality of value identifiers mapped to a plurality of attribute values, respectively, wherein the plurality of attribute values are identified from data records in a data structure;

modify the data records in the data structure by replacing an attribute value of each data record with a corresponding value identifier included in the dictionary, wherein the modification comprises mapping at least two data records that have a same attribute value to a same value identifier;

partitioning the modified data structure into a plurality of split data structures and rearranging data records among the split data structures based on the value identifiers such that each rearranged split data structure stores data records having a mutually exclusive subset of value identifiers;

in response to a query being received for an attribute, identifying a value identifier mapped to the attribute in the dictionary, identifying a rearranged split data structure storing the identified value identifier from among the plurality of rearranged split data structures, and executing the query on data records in the identified rearranged split data structure to generate search results; and

outputting information for display on a display device based on the search results.

14. The non-transitory computer readable storage medium of claim 13, storing instructions, which when executed by a computer, cause the computer to further execute operations comprising:

determine a transition index corresponding to one or more block transition indices within the rearranged split data structures.

15. The non-transitory computer readable storage medium of claim 13, wherein the dictionary includes a dictionary structure that comprises one or more dictionary types which correspond to one or more virtual partitions in the data structure.

16. The non-transitory computer readable storage medium of claim 15, wherein the dictionary structure includes:

a dictionary type identifier indicating the plurality of rearranged split data structures;

one or more start indices corresponding to the plurality of rearranged split data structures; and

one or more end indices corresponding to the plurality of rearranged split data structures.

17. The non-transitory computer readable storage medium of claim 13, wherein the rearranging the data records comprises swapping two data records having two different value identifiers stored in two different split data structures.