Distributed data set indexing

• US 10,303,670 B2
• Filed: 05/21/2018
• Issued: 05/28/2019
• 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/984,706
• Publication Number:
  US 20180276259A1
• Time in Patent Office: 372 Days
• Field of Search: 707687, 707705, 707790, 707821, 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 data records within a data cell, wherein for each data record, the processor retrieves data values from first and second data fields; determines whether the first and second data fields store unique data values; in response to the first data field storing a unique data value, adds an identifier of the data record to a first unique values index, in response to the second data field storing a unique data value, adds the identifier to a second unique values index, wherein identifiers of data records within the unique values indexes are ordered based on corresponding unique data values; and generates an indication of ranges of data values of the first and second data fields to enable a determination of whether a data value specified in search criteria is present within at least the data cell.

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:

read data values from a first data field and a second data field of a set of data fields within each data record of multiple data records of a first data cell of a data set in a single pass through the multiple data records of the first data cell;

for each data record within the first data cell, index the multiple data records of the first data cell, at the first node device and at least partially in parallel with other node devices of the multiple node devices, by performance of operations comprising;

determine, based on the data value retrieved from the first data field, whether the first data field stores a unique data value, wherein the data value has not been read from the first data field of any preceding data record in the single pass;

in response to a determination that the first data field stores a unique data value, add an identifier of the data record to a first unique values index of a first cell index that corresponds to the first data cell, wherein identifiers of data records within the first unique values index are ordered based on corresponding unique data values in the first data field to enable use of the first unique values index to perform a search of the data values within the first data field of the data records of the first data cell;

determine, based on the data value retrieved from the second data field, whether the second data field stores a unique data value, wherein the data value has not been read from the second data field of any preceding data record in the single pass; and

in response to a determination that the second data field stores a unique data value, add an identifier of the data record to a second unique values index of the first cell index, wherein identifiers of data records within the second unique values index are ordered based on corresponding unique data values in the second data field to enable use of the second unique values index to perform a search of the data values within the second data field of the data records of the first data cell;

request provision, by a control device, of a first pointer to a location within a data file maintained by at least one data device at which to store at least the first data cell and the first cell index; and

transmit, to the at least one data device, and at least partially in parallel with other node devices of the multiple node devices, at least the first data cell and the first cell index with an instruction to store at least the first data cell index and the first cell index with the first data cell stored in the data file starting at the location pointed to by the first pointer, and with the first cell index stored in the data file at a location after at least the first data cell.

2. The apparatus of claim 1, wherein:

a first processor core of the processor is caused to read the data values from the first data field and the second data field of the set of data fields within each data record of the multiple data records of the first data cell in a single pass; and

a second processor core of the processor is caused to read data values from the first data field and the second data field of the set of data fields within each data record of multiple data records of a second data cell of the data set in a single pass through the multiple data records of the second data cell.

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

following each retrieval of data values from the first data field and the second data field of a data record of the multiple data records within the first data cell, the processor is caused to perform operations comprising;

search a first binary tree of unique data values of the first data field of the first data cell correlated to the identifier of a data record 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;

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 data value that is not already present within the first binary tree;

search a second binary tree of unique data values of the second data field of the first data cell correlated to the identifier of a data record 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; 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 data value that is not already present within the second binary tree;

generate the first unique values index based on an in-order traversal of the first binary tree; and

generate the second unique values index based on an in-order traversal of the second binary tree.

4. The apparatus of claim 3, wherein:

following each retrieval of a data value from the first data field of a data record of the multiple data records within the first data cell, 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 within the first data cell, 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; and

each duplicate value index within the first and second sets of duplicate value indexes comprises at least one identifier of a data record within the first data cell.

5. The apparatus of claim 1, wherein:

the data set is divided into multiple super cells;

each super cell of the multiple super cells is divided into multiple data cells;

each data cell of the multiple data cells of each super cell, including the first data cell, is divided into multiple data records;

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

a super cell of the multiple super cells comprises the first data cell.

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

transmit an indication of current availability of resources of the first node device to the control device, at least partially in parallel with transmissions by other node devices of the multiple node devices of availability of resources, to the control device, to enable the control device to determine whether to assign the super cell to the first node device in lieu of assigning the super cell to another node device of the multiple node devices;

receive, at the first node device and from the control device, a second pointer to a location within data file from which to retrieve the super cell;

transmit, to the at least on data device and at least partially in parallel with other node devices of the multiple node devices, an instruction to provide the super cell to the first node device; and

receive, at the first node device, the super cell.

7. The apparatus of claim 5, wherein the processor is caused to perform operations comprising generate, within a super cell index corresponding to the super cell, an indication of a range of values of the first data field within the data records of the first data cell, and an indication of a range of values of the second data field within the data records of the first data cell, to enable use of the super cell index to determine whether a value specified in search criteria is present within one of the first and second data fields of any data record of the first data cell.

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

for each data cell of the multiple data cells within the super cell, including the first data cell, add a highest data value and a lowest data value of the range of 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 multiple data cells within the super cell;

add indications of the highest and lowest values of the first data field among the multiple data cells within the super cell to the super cell index to specify the 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 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 multiple data cells within the super cell; and

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

9. The apparatus of claim 7, 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 unique 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, perform operations comprising;

search at least one of a first set of duplicate value indexes and a 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;

parse the query instructions to determine whether the query instructions include task instructions for the performance of a task with data retrieved from one or more data records identified in at least the first data cell as meeting the search criteria; and

in response to a determination that the query instructions do include task instructions for the performance of a task, execute the instructions to perform the task at least partially in parallel with at least one other node device of the multiple node devices.

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:

read data values from a first data field and a second data field of a set of data fields within each data record of multiple data records of a first data cell of a data set in a single pass through the multiple data records of the first data cell;

for each data record within the first data cell, index the multiple data records of the first data cell, at the first node device and at least partially in parallel with other node devices of the multiple node devices, by performance of operations comprising;

determine, based on the data value retrieved from the first data field, whether the first data field stores a unique data value, wherein the data value has not been read from the first data field of any preceding data record in the single pass;

in response to a determination that the first data field stores a unique data value, add an identifier of the data record to a first unique values index of a first cell index that corresponds to the first data cell, wherein identifiers of data records within the first unique values index are ordered based on corresponding unique data values in the first data field to enable use of the first unique values index to perform a search of the data values within the first data field of the data records of the first data cell;

determine, based on the data value retrieved from the second data field, whether the second data field stores a unique data value, wherein the data value has not been read from the second data field of any preceding data record in the single pass; and

in response to a determination that the second data field stores a unique data value, add an identifier of the data record to a second unique values index of the first cell index, wherein identifiers of data records within the second unique values index are ordered based on corresponding unique data values in the second data field to enable use of the second unique values index to perform a search of the data values within the second data field of the data records of the first data cell;

request provision, by a control device, of a first pointer to a location within a data file maintained by at least one data device at which to store at least the first data cell and the first cell index; and

transmit, to the at least one data device, and at least partially in parallel with other node devices of the multiple node devices, at least the first data cell and the first cell index with an instruction to store at least the first data cell index and the first cell index with the first data cell stored in the data file starting at the location pointed to by the first pointer, and with the first cell index stored in the data file at a location after at least the first data cell.

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

a first processor core of the processor is caused to read the data values from the first data field and the second data field of the set of data fields within each data record of the multiple data records of the first data cell in a single pass; and

a second processor core of the processor is caused to read data values from the first data field and the second data field of the set of data fields within each data record of multiple data records of a second data cell of the data set in a single pass through the multiple data records of the second data cell.

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

following each retrieval of data values from the first data field and the second data field of a data record of the multiple data records within the first data cell, the processor is caused to perform operations comprising;

search a first binary tree of unique data values of the first data field of the first data cell correlated to the identifier of a data record 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;

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 data value that is not already present within the first binary tree;

search a second binary tree of unique data values of the second data field of the first data cell correlated to the identifier of a data record 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; 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 data value that is not already present within the second binary tree;

generate the first unique values index based on an in-order traversal of the first binary tree; and

generate the second unique values index based on an in-order traversal of the second binary tree.

14. The computer-program product of claim 13, wherein:

following each retrieval of a data value from the first data field of a data record of the multiple data records within the first data cell, 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 within the first data cell, 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; and

each duplicate value index within the first and second sets of duplicate value indexes comprises at least one identifier of a data record within the first data cell.

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

the data set is divided into multiple super cells;

each super cell of the multiple super cells is divided into multiple data cells;

each data cell of the multiple data cells of each super cell, including the first data cell, is divided into multiple data records;

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

a super cell of the multiple super cells comprises the first data cell.

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

transmit an indication of current availability of resources of the first node device to the control device, at least partially in parallel with transmissions by other node devices of the multiple node devices of availability of resources, to the control device, to enable the control device to determine whether to assign the super cell to the first node device in lieu of assigning the super cell to another node device of the multiple node devices;

receive, at the first node device and from the control device, a second pointer to a location within data file from which to retrieve the super cell;

transmit, to the at least on data device and at least partially in parallel with other node devices of the multiple node devices, an instruction to provide the super cell to the first node device; and

receive, at the first node device, the super cell.

17. The computer-program product of claim 15, wherein the processor is caused to perform operations comprising generate, within a super cell index corresponding to the super cell, an indication of a range of values of the first data field within the data records of the first data cell, and an indication of a range of values of the second data field within the data records of the first data cell, to enable use of the super cell index to determine whether a value specified in search criteria is present within one of the first and second data fields of any data record of the first data cell.

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

for each data cell of the multiple data cells within the super cell, including the first data cell, add a highest data value and a lowest data value of the range of 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 multiple data cells within the super cell;

add indications of the highest and lowest values of the first data field among the multiple data cells within the super cell to the super cell index to specify the 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 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 multiple data cells within the super cell; and

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

19. The computer-program product of claim 17, 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 unique 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, perform operations comprising;

search at least one of a first set of duplicate value indexes and a 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;

parse the query instructions to determine whether the query instructions include task instructions for the performance of a task with data retrieved from one or more data records identified in at least the first data cell as meeting the search criteria; and

in response to a determination that the query instructions do include task instructions for the performance of a task, execute the instructions to perform the task at least partially in parallel with at least one other node device of the multiple node devices.

21. A computer-implemented method comprising:

reading, at a first node device of multiple node devices, data values from a first data field and a second data field of a set of data fields within each data record of multiple data records of a first data cell of a data set in a single pass through the multiple data records of the first data cell;

for each data record within the first data cell, indexing the multiple data records of the first data cell, at the first node device and at least partially in parallel with other node devices of the multiple node devices, by performing operations comprising;

determining, based on the data value retrieved from the first data field, whether the first data field stores a unique data value, wherein the data value has not been read from the first data field of any preceding data record in the single pass;

in response to a determination that the first data field stores a unique data value, adding an identifier of the data record to a first unique values index of a first cell index that corresponds to the first data cell, wherein identifiers of data records within the first unique values index are ordered based on corresponding unique data values in the first data field to enable use of the first unique values index to perform a search of the data values within the first data field of the data records of the first data cell;

determining, based on the data value retrieved from the second data field, whether the second data field stores a unique data value, wherein the data value has not been read from the second data field of any preceding data record in the single pass; and

in response to a determination that the second data field stores a unique data value, adding an identifier of the data record to a second unique values index of the first cell index, wherein identifiers of data records within the second unique values index are ordered based on corresponding unique data values in the second data field to enable use of the second unique values index to perform a search of the data values within the second data field of the data records of the first data cell;

requesting provision, by a control device, of a first pointer to a location within a data file maintained by at least one data device at which to store at least the first data cell and the first cell index; and

transmitting, to the at least one data device, and at least partially in parallel with other node devices of the multiple node devices, at least the first data cell and the first cell index with an instruction to store at least the first data cell index and the first cell index with the first data cell stored in the data file starting at the location pointed to by the first pointer, and with the first cell index stored in the data file at a location after at least the first data cell.

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

a first processor core of a processor of the first node device is caused to read the data values from the first data field and the second data field of the set of data fields within each data record of the multiple data records of the first data cell in a single pass; and

a second processor core of the processor is caused to read data values from the first data field and the second data field of the set of data fields within each data record of multiple data records of a second data cell of the data set in a single pass through the multiple data records of the second data cell.

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

following each retrieval of data values from the first data field and the second data field of a data record of the multiple data records within the first data cell, performing operations comprising;

searching a first binary tree of unique data values of the first data field of the first data cell correlated to the identifier of a data record 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;

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 data value that is not already present within the first binary tree;

searching a second binary tree of unique data values of the second data field of the first data cell correlated to the identifier of a data record 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; 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 data value that is not already present within the second binary tree;

generating the first unique values index based on an in-order traversal of the first binary tree; and

generating the second unique values index based on an in-order traversal of the second binary tree.

24. The computer-implemented method of claim 23, wherein:

the method comprises, following each retrieval of a data value from the first data field of a data record of the multiple data records within the first data cell, 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;

the method comprises, following each retrieval of a data value from the second data field of a data record of the multiple data records within the first data cell, 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; and

each duplicate value index within the first and second sets of duplicate value indexes comprises at least one identifier of a data record within the first data cell.

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

the data set is divided into multiple super cells;

each super cell of the multiple super cells is divided into multiple data cells;

each data cell of the multiple data cells of each super cell, including the first data cell, is divided into multiple data records;

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

a super cell of the multiple super cells comprises the first data cell.

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

transmitting an indication of current availability of resources of the first node device to the control device, at least partially in parallel with transmissions by other node devices of the multiple node devices of availability of resources, to the control device, to enable the control device to determine whether to assign the super cell to the first node device in lieu of assigning the super cell to another node device of the multiple node devices;

receiving, at the first node device and from the control device, a second pointer to a location within data file from which to retrieve the super cell;

transmitting, to the at least on data device and at least partially in parallel with other node devices of the multiple node devices, an instruction to provide the super cell to the first node device; and

receiving, at the first node device, the super cell.

27. The computer-implemented method of claim 25, comprising generating, within a super cell index corresponding to the super cell, an indication of a range of values of the first data field within the data records of the first data cell, and an indication of a range of values of the second data field within the data records of the first data cell, to enable use of the super cell index to determine whether a value specified in search criteria is present within one of the first and second data fields of any data record of the first data cell.

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

for each data cell of the multiple data cells within the super cell, including the first data cell, adding a highest data value and a lowest data value of the range of 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 multiple data cells within the super cell;

adding indications of the highest and lowest values of the first data field among the multiple data cells within the super cell to the super cell index to specify the 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 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 multiple data cells within the super cell; and

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

29. The computer-implemented method of claim 27, 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 unique 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, performing operations comprising;

searching at least one of a first set of duplicate value indexes and a 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;

parsing the query instructions to determine whether the query instructions include task instructions for the performance of a task with data retrieved from one or more data records identified in at least the first data cell as meeting the search criteria; and

in response to a determination that the query instructions do include task instructions for the performance of a task, executing the instructions to perform the task at least partially in parallel with at least one other node device of the multiple node devices.