Distributed data set indexing

Patent metadata

Field	Value
Publication number	US-9977805-B1
Application number	US-201715838110-A
Country	US
Kind code	B1
Filing date	Dec 11, 2017
Priority date	Feb 13, 2017
Publication date	May 22, 2018
Grant date	May 22, 2018

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.

First claim

The invention claimed is:

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:
receive, 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 fields at which data values of the data set are stored;

index, at the first node device, and at least partially in parallel with other node devices of the multiple node devices, the multiple data records within each data cell of the multiple data cells by a first data field and by a second data field of the set of fields in a single read pass through each data cell of the multiple data cells, wherein for each data record within a first data cell of the received super cell, the processor is caused to:
retrieve a data value from the first data field and a data value from the second data field;
determine, based on the data value retrieved from the first data field, whether the first data field of the data record stores a unique data value, wherein the data value has not yet been retrieved by the processor from the first data field of any data record of the first data cell;
in response to a determination that the first data field of the data record stores a unique data value, add an identifier of the data record to a first unique values index of a first cell index corresponding to the first data cell, wherein identifiers of data records within the first unique values index are ordered based on the 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 of the data record stores a unique data value, wherein the data value has not yet retrieved by the processor from the second data field of any data record of the first data cell; and
in response to a determination that the second data field of the data record 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 the 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;

generate, within a super cell index corresponding to the received super cell, 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, 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;
provide, to a control device, a request for a first pointer to a location within the data file at which to store the super cell, the super cell index and the first cell index;
receive, at the first node device and from the control device, the first pointer; and
transmit, to the at least one data device and at least partially in parallel with other node devices of the multiple node devices, the super cell, the super cell index and the first cell index with an instruction to store the super cell, the super cell index and the first cell index with the super cell stored in the data file starting at the location pointed to by the first pointer, with the super cell index and the first cell index stored in the data file at a location after the super cell.

2. The apparatus of claim 1 , wherein:
the received super cell comprises a second data cell in addition to the first data cell;
the processor is caused to index the multiple data records within the second data cell by the first data field and by the second data field of the set of fields in a single read pass to generate additional unique values indexes within the first cell index 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;
a first processor core of the processor indexes the multiple data records within the first data cell; and
a second processor core of the processor indexes the multiple data records within the second data cell at least partially in parallel with the indexing, by the first processor core, of the multiple data records within the first data cell.

3. The apparatus of claim 1 , wherein the processor is caused to:
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.

4. 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, 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

Assignees

• Sas Inst Inc

Inventors

• Bowman Brian Payton
• Keener Gordon Lyle
• Krueger Steven E

Classifications

• G06F16/2228 Primary

  Indexing structures · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F9/5072

  Grid computing · CPC title

• G06F16/21

  Design, administration or maintenance of databases · CPC title

• G06F16/9027

  Trees · CPC title