Distributed data set indexing

• US 10,013,441 B1
• Filed: 12/11/2017
• Issued: 07/03/2018
• Est. Priority Date: 02/13/2017
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Bowman, Brian Payton, Keener, Gordon Lyle, Krueger, Steven E.
• Primary Examiner(s): Al-Hashemi, Sana A
• Application Number:
  US15/838,195
• Time in Patent Office: 204 Days
• Field of Search: 707610, 707613, 707687, 707705, 707790, 707813, 707964
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/2219 Large Object storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/381 using identifiers, e.g. barcodes, RFIDs for URLs G06F16/9554
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06F 7/08 Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry by merging two or more sets of carriers in ordered sequence G06F7/16
• CPC Class Codes: G06F 7/20 Comparing separate sets of record carriers arranged in the same sequence to determine whether at least some of the data in one set is identical with that in the other set or sets
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

An apparatus including a processor to: index multiple data records within a data cell by first and second data fields in a single read pass through the data cell; wherein for each data record within the first data cell, the processor is to retrieve data values from the first and second data fields, search a first binary tree to determine whether the data value from the first data field comprises a unique value, and add the data value to the first binary tree if it is unique, and search a second binary tree to determine whether the data value from the second data field comprises a unique value, and add the data value to the second binary tree if it is unique; and generate a first and second unique values indexes of identifiers of the data records associated with the unique data values within the first and second binary trees.

Claims

1. An apparatus comprising a processor of a first node device of multiple node devices, and a storage of the first node device to store instructions that, when executed by the processor, cause the processor to perform operations comprising:

store, at the first node device, a super cell of multiple super cells into which a data set is divided from a data file maintained by at least one data device, wherein;

the multiple super cells are distributed among the multiple node devices;

each super cell comprises multiple data cells;

each data cell of the multiple data cells comprises multiple data records; and

each data record of the multiple data records comprises a set of data fields at which data values of the data set are stored;

index, at the first node device, the multiple data records within a first data cell of a super cell by a first data field and by a second data field of the set of data fields in a single read pass through the first data cell, wherein for each data record within the first data cell, the processor is caused to;

retrieve data values from the first data field and the second data field;

perform operations to generate a first binary tree of unique data values of the first data field of the first data cell to determine whether the data value retrieved from the first data field comprises a unique value or a duplicate value, the operations comprising;

search the first binary tree to determine whether the data value retrieved from the first data field comprises a duplicate data value that is already present within the first binary tree or a unique value that is not already present within the first binary tree; and

add the data value retrieved from the first data field to the first binary tree in response to a determination that the data value retrieved from the first data field is a unique value; and

perform operations to generate a second binary tree of unique data values of the second data field of the first data cell to determine whether the data value retrieved from the second data field comprises a unique value or a duplicate value, the operations comprising;

search the second binary tree to determine whether the data value retrieved from the second data field comprises a duplicate data value that is already present within the second binary tree or a unique value that is not already present within the second binary tree; and

add the data value retrieved from the second data field to the second binary tree in response to a determination that the data value retrieved from the second data field is a unique value;

generate a first unique values index of identifiers of the data records associated with the unique data values within the first binary tree based on an in-order traversal of the first binary tree to enable use of the first unique values index to perform a binary search of the data values within the first data field of the data records of the first data cell;

generate a second unique values index of identifiers of the data records associated with the unique data values within the second binary tree based on an in-order traversal of the second binary tree to enable use of the second unique values index to perform a binary search of the data values within the second data field of the data records of the first data cell;

generate, within a super cell index corresponding to the super cell, and from the in-order traversals of the first and second binary trees, an indication of a range of the data values of the first data field within the data records of the first data cell, and an indication of a range of the data values of the second data field within the data records of the first data cell; and

provide the super cell index to a control device to enable use of the super cell index by the control device.

2. The apparatus of claim 1, wherein:

the super cell comprises a second data cell in addition to the first data cell;

the processor is caused to index, on a first thread of execution, the multiple data records within the first data cell to generate a first cell index that corresponds to the first data cell; and

the processor is caused to index, on a second thread of execution at least partially in parallel with the indexing of the multiple data records of the first data cell, the multiple data records within the second data cell by the first data field and the by the second data field of the set of data fields in a single read pass to generate a second cell index that corresponds to the second data cell, wherein the second cell index includes unique values indexes to enable a binary search of the data values within at least one of the first data field and the second data field of the data records within the second data cell.

3. The apparatus of claim 2, wherein the processor is caused to allocate a separate processor core of the processor to each of the first and second threads of execution.

4. The apparatus of claim 1, wherein the processor is caused to perform operations comprising:

for each data cell within the super cell, add a highest data value and a lowest data value of the range of data values of the first data field to a third binary tree;

perform an in-order traversal of the third binary tree to identify highest and lowest data values of the first data field among the data cells within the super cell;

add indications of the highest and lowest values of the first data field among the data cells within the super cell to the super cell index to specify a range of values of the first data field for the super cell therein;

for each data cell within the super cell, add a highest data value and a lowest data value of the range of data values of the second data field to a fourth binary tree;

perform an in-order traversal of the fourth binary tree to identify highest and lowest data values of the second data field among the data cells within the super cell; and

add indications of the highest and lowest values of the second data field among the data cells within the super cell to the super cell index to specify a range of values of the second data field for the super cell therein.

5. The apparatus of claim 1, wherein the processor is caused to perform operations comprising:

analyze a data type and a data size of the first data field to determine whether to generate a unique values vector within a first cell index that corresponds to the first data cell; and

in response to a determination to generate the unique values vector, the processor is caused to perform operations comprising;

retrieve the unique values within the first binary tree via an in-order traversal of the first binary tree; and

generate the unique values vector to include the unique values within the first binary tree sorted as sorted by the in-order traversal.

6. The apparatus of claim 1, wherein the processor is caused to perform operations comprising:

analyze a data type and a data size of the first data field to determine whether to generate a hash values vector within a first cell index that corresponds to the first data cell; and

in response to a determination to generate the hash values vector, the processor is caused to perform operations comprising;

generate a hash value from each unique value within the first binary tree; and

generate the hash values vector to include the hash values sorted by value.

7. The apparatus of claim 1, wherein:

following each retrieval of a data value from the first data field of a data record of the multiple data records, the processor is caused to perform operations comprising;

in response to a determination that the first data field of the data record stores a duplicate data value, search a first set of duplicate value indexes within the first cell index to determine whether a duplicate value index already exists within the first set for the duplicate value;

in response to identifying an existing duplicate value index for the duplicate value within the first set, add the identifier of the data record to the identified existing duplicate value index; and

in response to determining that there is no existing duplicate value index among the first set of duplicate value indexes for the duplicate value, add a duplicate value index to the first set for the duplicate value and add the identifier of the data record to the added duplicate value index;

following each retrieval of a data value from the second data field of a data record of the multiple data records, the processor is caused to perform operations comprising;

in response to a determination that the second data field of the data record stores a duplicate data value, search a second set of duplicate value indexes with the first cell index to determine whether a duplicate value index already exists within the second set for the duplicate value;

in response to identifying an existing duplicate value index for the duplicate value within the second set, add the identifier of the data record to the identified existing duplicate value index; and

in response to determining that there is no existing duplicate value index among the second set of duplicate value indexes for the duplicate value, add a duplicate value index to the second set for the duplicate value and add the identifier of the data record to the added duplicate value index;

the first unique values index comprises a vector of identifiers of data records;

the second unique values index comprises a vector of identifiers of data records; and

each duplicate value index within the first and second sets of duplicate value indexes comprises a vector of identifiers of data records.

8. The apparatus of claim 7, wherein:

the first unique values index comprises a count of indexes of data records included in the first unique values index;

the second unique values index comprises a count of indexes of data records included in the second unique values index;

each duplicate value index within the first set of duplicate value indexes comprises a count of indexes of data records included in the duplicate value index; and

each duplicate value index within the second set of duplicate value indexes comprises a count of indexes of data records included in the duplicate value index.

9. The apparatus of claim 8, wherein the processor is caused to perform operations comprising:

receive, at the first node device, and at least partially in parallel with other node devices of the multiple node devices, query instructions specifying search criteria of a search to be performed of the data set for data records meeting the search criteria, wherein the search criteria comprises at least one data value to be searched for within at least one of the first data field and the second data field;

compare the at least one data value to at least one of the range of values of the first data field and the range of values of the second data field specified by the super cell index to determine whether the super cell includes any data records that meet the search criteria; and

in response to a determination that at least one data record within at least one data cell of the super cell does include a data record that meets the search criteria, compare the at least one data value to at least one of the range of values of the first data field and the range of values of the second data field specified by the super cell index to determine at least whether the first data cell includes any data records that meet the search criteria.

10. The apparatus of claim 9, wherein the processor is caused to perform operations comprising:

in response to a determination that at least the first data cell does include a data record that meets the search criteria, use at least one of the first unique values index and the second values index to perform a binary search of the data records of the first data cell to identify one or more data records of the first data cell that meet the search criteria; and

upon identifying a data record of the first data cell that meets the search criteria, search at least one of the first set of duplicate value indexes and the second set of duplicate value indexes for a duplicate value index that identifies one or more additional data records of the first data cell that meet the search criteria.

11. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a processor of a first node device of multiple node devices to perform operations comprising:

store, at the first node device, a super cell of multiple super cells into which a data set is divided from a data file maintained by at least one data device, wherein;

the multiple super cells are distributed among the multiple node devices;

each super cell comprises multiple data cells;

each data cell of the multiple data cells comprises multiple data records; and

each data record of the multiple data records comprises a set of data fields at which data values of the data set are stored;

index, at the first node device, the multiple data records within a first data cell of a super cell by a first data field and by a second data field of the set of data fields in a single read pass through the first data cell, wherein for each data record within the first data cell, the processor is caused to;

retrieve data values from the first data field and the second data field;

perform operations to generate a first binary tree of unique data values of the first data field of the first data cell to determine whether the data value retrieved from the first data field comprises a unique value or a duplicate value, the operations comprising;

search the first binary tree to determine whether the data value retrieved from the first data field comprises a duplicate data value that is already present within the first binary tree or a unique value that is not already present within the first binary tree; and

add the data value retrieved from the first data field to the first binary tree in response to a determination that the data value retrieved from the first data field is a unique value; and

perform operations to generate a second binary tree of unique data values of the second data field of the first data cell to determine whether the data value retrieved from the second data field comprises a unique value or a duplicate value, the operations comprising;

search the second binary tree to determine whether the data value retrieved from the second data field comprises a duplicate data value that is already present within the second binary tree or a unique value that is not already present within the second binary tree; and

add the data value retrieved from the second data field to the second binary tree in response to a determination that the data value retrieved from the second data field is a unique value;

generate a first unique values index of identifiers of the data records associated with the unique data values within the first binary tree based on an in-order traversal of the first binary tree to enable use of the first unique values index to perform a binary search of the data values within the first data field of the data records of the first data cell;

generate a second unique values index of identifiers of the data records associated with the unique data values within the second binary tree based on an in-order traversal of the second binary tree to enable use of the second unique values index to perform a binary search of the data values within the second data field of the data records of the first data cell;

generate, within a super cell index corresponding to the super cell, and from the in-order traversals of the first and second binary trees, an indication of a range of the data values of the first data field within the data records of the first data cell, and an indication of a range of the data values of the second data field within the data records of the first data cell; and

provide the super cell index to a control device to enable use of the super cell index by the control device.

12. The computer-program product of claim 11, wherein:

the super cell comprises a second data cell in addition to the first data cell;

the processor is caused to index, on a first thread of execution, the multiple data records within the first data cell to generate a first cell index that corresponds to the first data cell; and

the processor is caused to index, on a second thread of execution at least partially in parallel with the indexing of the multiple data records of the first data cell, the multiple data records within the second data cell by the first data field and the by the second data field of the set of data fields in a single read pass to generate a second cell index that corresponds to the second data cell, wherein the second cell index includes unique values indexes to enable a binary search of the data values within at least one of the first data field and the second data field of the data records within the second data cell.

13. The computer-program product of claim 12, wherein the processor is caused to allocate a separate processor core of the processor to each of the first and second threads of execution.

14. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising:

for each data cell within the super cell, add a highest data value and a lowest data value of the range of data values of the first data field to a third binary tree;

perform an in-order traversal of the third binary tree to identify highest and lowest data values of the first data field among the data cells within the super cell;

add indications of the highest and lowest values of the first data field among the data cells within the super cell to the super cell index to specify a range of values of the first data field for the super cell therein;

for each data cell within the super cell, add a highest data value and a lowest data value of the range of data values of the second data field to a fourth binary tree;

perform an in-order traversal of the fourth binary tree to identify highest and lowest data values of the second data field among the data cells within the super cell; and

add indications of the highest and lowest values of the second data field among the data cells within the super cell to the super cell index to specify a range of values of the second data field for the super cell therein.

15. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising:

analyze a data type and a data size of the first data field to determine whether to generate a unique values vector within a first cell index that corresponds to the first data cell; and

in response to a determination to generate the unique values vector, the processor is caused to perform operations comprising;

retrieve the unique values within the first binary tree via an in-order traversal of the first binary tree; and

generate the unique values vector to include the unique values within the first binary tree sorted as sorted by the in-order traversal.

16. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising:

analyze a data type and a data size of the first data field to determine whether to generate a hash values vector within a first cell index that corresponds to the first data cell,

in response to a determination to generate the hash values vector, the processor is caused to perform operations comprising;

generate a hash value from each unique value within the first binary tree; and

generate the hash values vector to include the hash values sorted by value.

17. The computer-program product of claim 11, wherein:

following each retrieval of a data value from the first data field of a data record of the multiple data records, the processor is caused to perform operations comprising;

in response to a determination that the first data field of the data record stores a duplicate data value, search a first set of duplicate value indexes within the first cell index to determine whether a duplicate value index already exists within the first set for the duplicate value;

in response to identifying an existing duplicate value index for the duplicate value within the first set, add the identifier of the data record to the identified existing duplicate value index; and

in response to determining that there is no existing duplicate value index among the first set of duplicate value indexes for the duplicate value, add a duplicate value index to the first set for the duplicate value and add the identifier of the data record to the added duplicate value index;

following each retrieval of a data value from the second data field of a data record of the multiple data records, the processor is caused to perform operations comprising;

in response to a determination that the second data field of the data record stores a duplicate data value, search a second set of duplicate value indexes with the first cell index to determine whether a duplicate value index already exists within the second set for the duplicate value;

in response to identifying an existing duplicate value index for the duplicate value within the second set, add the identifier of the data record to the identified existing duplicate value index; and

in response to determining that there is no existing duplicate value index among the second set of duplicate value indexes for the duplicate value, add a duplicate value index to the second set for the duplicate value and add the identifier of the data record to the added duplicate value index;

the first unique values index comprises a vector of identifiers of data records;

the second unique values index comprises a vector of identifiers of data records; and

each duplicate value index within the first and second sets of duplicate value indexes comprises a vector of identifiers of data records.

18. The computer-program product of claim 17, wherein:

the first unique values index comprises a count of indexes of data records included in the first unique values index;

the second unique values index comprises a count of indexes of data records included in the second unique values index;

each duplicate value index within the first set of duplicate value indexes comprises a count of indexes of data records included in the duplicate value index; and

each duplicate value index within the second set of duplicate value indexes comprises a count of indexes of data records included in the duplicate value index.

19. The computer-program product of claim 18, wherein the processor is caused to perform operations comprising:

receive, at the first node device, and at least partially in parallel with other node devices of the multiple node devices, query instructions specifying search criteria of a search to be performed of the data set for data records meeting the search criteria, wherein the search criteria comprises at least one data value to be searched for within at least one of the first data field and the second data field;

compare the at least one data value to at least one of the range of values of the first data field and the range of values of the second data field specified by the super cell index to determine whether the super cell includes any data records that meet the search criteria; and

in response to a determination that at least one data record within at least one data cell of the super cell does include a data record that meets the search criteria, compare the at least one data value to at least one of the range of values of the first data field and the range of values of the second data field specified by the super cell index to determine at least whether the first data cell includes any data records that meet the search criteria.

20. The computer-program product of claim 19, wherein the processor is caused to perform operations comprising:

in response to a determination that at least the first data cell does include a data record that meets the search criteria, use at least one of the first unique values index and the second values index to perform a binary search of the data records of the first data cell to identify one or more data records of the first data cell that meet the search criteria; and

upon identifying a data record of the first data cell that meets the search criteria, search at least one of the first set of duplicate value indexes and the second set of duplicate value indexes for a duplicate value index that identifies one or more additional data records of the first data cell that meet the search criteria.

21. A computer-implemented method comprising:

storing, at the first node device, a super cell of multiple super cells into which a data set is divided from a data file maintained by at least one data device, wherein;

the multiple super cells are distributed among the multiple node devices;

each super cell comprises multiple data cells;

each data cell of the multiple data cells comprises multiple data records; and

each data record of the multiple data records comprises a set of data fields at which data values of the data set are stored;

indexing, at the first node device, the multiple data records within a first data cell of a super cell by a first data field and by a second data field of the set of data fields in a single read pass through the first data cell, wherein the operations comprise, for each data record within the first data cell;

retrieving data values from the first data field and the second data field;

performing operations to generate a first binary tree of unique data values of the first data field of the first data cell to determine whether the data value retrieved from the first data field comprises a unique value or a duplicate value, the operations comprising;

searching the first binary tree to determine whether the data value retrieved from the first data field comprises a duplicate data value that is already present within the first binary tree or a unique value that is not already present within the first binary tree; and

adding the data value retrieved from the first data field to the first binary tree in response to a determination that the data value retrieved from the first data field is a unique value; and

perform operations to generate a second binary tree of unique data values of the second data field of the first data cell to determine whether the data value retrieved from the second data field comprises a unique value or a duplicate value, the operations comprising;

searching the second binary tree to determine whether the data value retrieved from the second data field comprises a duplicate data value that is already present within the second binary tree or a unique value that is not already present within the second binary tree; and

adding the data value retrieved from the second data field to the second binary tree in response to a determination that the data value retrieved from the second data field is a unique value;

generating a first unique values index of identifiers of the data records associated with the unique data values within the first binary tree based on an in-order traversal of the first binary tree to enable use of the first unique values index to perform a binary search of the data values within the first data field of the data records of the first data cell;

generating a second unique values index of identifiers of the data records associated with the unique data values within the second binary tree based on an in-order traversal of the second binary tree to enable use of the second unique values index to perform a binary search of the data values within the second data field of the data records of the first data cell;

generating, within a super cell index corresponding to the super cell, and from the in-order traversals of the first and second binary trees, an indication of a range of the data values of the first data field within the data records of the first data cell, and an indication of a range of the data values of the second data field within the data records of the first data cell; and

providing the super cell index to a control device to enable use of the super cell index by the control device.

22. The computer-implemented method of claim 21, wherein:

the super cell comprises a second data cell in addition to the first data cell; and

the method comprises;

indexing, on a first thread of execution, the multiple data records within the first data cell to generate a first cell index that corresponds to the first data cell; and

indexing, on a second thread of execution at least partially in parallel with the indexing the multiple data records of the first data cell, the multiple data records within the second data cell by the first data field and the by the second data field of the set of data fields in a single read pass to generate a second cell index that corresponds to the second data cell, wherein the second cell index includes unique values indexes to enable a binary search of the data values within at least one of the first data field and the second data field of the data records within the second data cell.

23. The computer-implemented method of claim 22, comprising allocating a separate processor core of the processor to each of the first and second threads of execution.

24. The computer-implemented method of claim 21, wherein the method comprises:

for each data cell within the super cell, adding a highest data value and a lowest data value of the range of data values of the first data field to a third binary tree;

performing an in-order traversal of the third binary tree to identify highest and lowest data values of the first data field among the data cells within the super cell;

adding indications of the highest and lowest values of the first data field among the data cells within the super cell to the super cell index to specify a range of values of the first data field for the super cell therein;

for each data cell within the super cell, adding a highest data value and a lowest data value of the range of data values of the second data field to a fourth binary tree;

performing an in-order traversal of the fourth binary tree to identify highest and lowest data values of the second data field among the data cells within the super cell; and

adding indications of the highest and lowest values of the second data field among the data cells within the super cell to the super cell index to specify a range of values of the second data field for the super cell therein.

25. The computer-implemented method of claim 21, comprising:

analyzing a data type and a data size of the first data field to determine whether to generate a unique values vector within a first cell index that corresponds to the first data cell; and

in response to a determination to generate the unique values vector, the processor is caused to perform operations comprising;

retrieving the unique values within the first binary tree via an in-order traversal of the first binary tree; and

generating the unique values vector to include the unique values within the first binary tree sorted as sorted by the in-order traversal.

26. The computer-implemented method of claim 21, comprising:

analyzing a data type and a data size of the first data field to determine whether to generate a hash values vector within a first cell index that corresponds to the first data cell, and

in response to a determination to generate the hash values vector, the processor is caused to perform operations comprising;

generating a hash value from each unique value within the first binary tree; and

generating the hash values vector to include the hash values sorted by value.

27. The computer-implemented method of claim 21, comprising:

following each retrieval of a data value from the first data field of a data record of the multiple data records, performing operations comprising;

in response to a determination that the first data field of the data record stores a duplicate data value, searching a first set of duplicate value indexes within the first cell index to determine whether a duplicate value index already exists within the first set for the duplicate value;

in response to identifying an existing duplicate value index for the duplicate value within the first set, adding the identifier of the data record to the identified existing duplicate value index; and

in response to determining that there is no existing duplicate value index among the first set of duplicate value indexes for the duplicate value, adding a duplicate value index to the first set for the duplicate value and add the identifier of the data record to the added duplicate value index;

following each retrieval of a data value from the second data field of a data record of the multiple data records, performing operations comprising;

in response to a determination that the second data field of the data record stores a duplicate data value, searching a second set of duplicate value indexes with the first cell index to determine whether a duplicate value index already exists within the second set for the duplicate value;

in response to identifying an existing duplicate value index for the duplicate value within the second set, adding the identifier of the data record to the identified existing duplicate value index; and

in response to determining that there is no existing duplicate value index among the second set of duplicate value indexes for the duplicate value, adding a duplicate value index to the second set for the duplicate value and add the identifier of the data record to the added duplicate value index;

the first unique values index comprises a vector of identifiers of data records;

the second unique values index comprises a vector of identifiers of data records; and

each duplicate value index within the first and second sets of duplicate value indexes comprises a vector of identifiers of data records.

28. The computer-implemented method of claim 27, wherein:

the first unique values index comprises a count of indexes of data records included in the first unique values index;

the second unique values index comprises a count of indexes of data records included in the second unique values index;

each duplicate value index within the first set of duplicate value indexes comprises a count of indexes of data records included in the duplicate value index; and

each duplicate value index within the second set of duplicate value indexes comprises a count of indexes of data records included in the duplicate value index.

29. The computer-implemented method of claim 28, comprising:

receiving, at the first node device, and at least partially in parallel with other node devices of the multiple node devices, query instructions specifying search criteria of a search to be performed of the data set for data records meeting the search criteria, wherein the search criteria comprises at least one data value to be searched for within at least one of the first data field and the second data field;

comparing the at least one data value to at least one of the range of values of the first data field and the range of values of the second data field specified by the super cell index to determine whether the super cell includes any data records that meet the search criteria; and

in response to a determination that at least one data record within at least one data cell of the super cell does include a data record that meets the search criteria, comparing the at least one data value to at least one of the range of values of the first data field and the range of values of the second data field specified by the super cell index to determine at least whether the first data cell includes any data records that meet the search criteria.

30. The computer-implemented method of claim 29, comprising:

in response to a determination that at least the first data cell does include a data record that meets the search criteria, using at least one of the first unique values index and the second values index to perform a binary search of the data records of the first data cell to identify one or more data records of the first data cell that meet the search criteria; and

upon identifying a data record of the first data cell that meets the search criteria, searching at least one of the first set of duplicate value indexes and the second set of duplicate value indexes for a duplicate value index that identifies one or more additional data records of the first data cell that meet the search criteria.