Parallel Index Scan Using Fetch-And-Add in Multi-Processing
Original Publication Date: 1988-Jun-01
Included in the Prior Art Database: 2005-Feb-15
A technique is described whereby a method for parallel scanning of a tree-structured index, such as a B-tree in multi-processing applications, uses a fetch-and-add type of instruction for synchronization. In prior art, the use of fetch-and-add instructions has been an effective synchronization primitive for allocating work to parallel processors. Typically, fetch-and-add is used to allocate work from a linear data structure or through the use of a parallel "do" loop. The concept described herein extends the use of fetch-and-add so as to allocate work from a tree-based data structure, such as a B-tree. When performing a parallel scan of a B+-tree type of structured index, keys with associated data are only stored in leaf nodes; higher level nodes contain key values or key prefixes and pointer to lower level nodes.