Teradata Row Retrieval: Understanding Hashing, Indexing, and Search Algorithms

Introduction

Teradata uses various mechanisms, such as hash maps, master and cylinder indexes, and binary and sequential search algorithms, to locate table rows. This article explains the process of locating table rows in Teradata using these elements and techniques.

Hash Maps

Teradata’s architecture utilizes the Massively Parallel Processing (MPP) model, which distributes data among Access Module Processors (AMPs). To distribute and retrieve data, Teradata employs a hashing algorithm. The primary index (PI) value is hashed to produce a row hash value during a table row search. This value is used to locate the corresponding AMP in a hash map, ensuring the efficiency and speed of data retrieval operations.

Master Index

After identifying the AMP responsible for storing the row, Teradata refers to the Master Index, which holds information on the location of data blocks on the AMP’s disks. The Master Index maps row hash values to their corresponding data block locations, enabling Teradata to quickly locate the data block containing the desired row.

Cylinder Index

Teradata’s disks are divided into cylinders, each with its own Index that maps row hash values to data block locations. This allows Teradata to efficiently locate the data block containing the searched row.

Binary and Sequential Search within Data Blocks

After locating the data block with the required row, Teradata conducts a search to find the row within the block using either binary or sequential search based on the block size and row count.

• Binary Search: Teradata uses a binary search for larger data blocks with many rows. This search algorithm is efficient because it works on sorted datasets, and in Teradata, rows within a data block are sorted by their row hash values. The binary search algorithm repeatedly narrows the search space by comparing the target row hash value with the middle row’s value until the desired row is found or determined not to exist in the data block.
• Sequential Search: Teradata may use a sequential search, also known as a linear search. This method examines each row in the data block sequentially until the desired row is found or determined not to exist in the data block. Although less efficient than a binary search, the performance difference for small data blocks is minimal.

5. Locating Rows with Table ID, RowID, and Searched Value: Teradata always locates table rows using three key pieces of information: the Table ID, RowID, and the searched value (typically the PI value). The Table ID uniquely identifies the table within the database, while the RowID represents a unique identifier for the row within the table. Combined with the searched value, these identifiers ensure that Teradata can quickly and accurately locate the desired row.

Conclusion

Teradata achieves efficient row retrieval using hash maps, master indexes, cylinder indexes, and binary and sequential search algorithms. Understanding these components and their interactions helps database administrators and developers better appreciate Teradata’s performance capabilities and optimize data warehousing operations.