Database processing on ann-dimensional mesh

In this dissertation, an array processor connected in an n-dimensional mesh is evaluated for very large relational database applications. Each node is assumed to have substantial processing capability with substantial amount of memory. By partitioning each base relation among all nodes, and by storing them directly within primary memory of a memory-resident database machine, the bottleneck of slow secondary storage access is eliminated. Whenever inter-node operations are required, local partitions are routed to other nodes.; In this dissertation, an n-dimensional mesh is studied for SIMD database processing. Database algorithms are classified into five categories based on their routing requirements: (1) database algorithms which do not require any routing such as select; (2) database algorithms that require partial routing without order such as tuple balancing; (3) database algorithms that require partial routing with order such as project, elimination of duplicates, and sort; (4) database algorithms that require full routing such as nested-loop, sort-merge join algorithms, and cartesian product; (5) database algorithms that require random routing such as hash-based join and hash-based aggregate algorithms. Routing algorithms appropriate for these different classes of database algorithms are presented, and their performances are analyzed. Their performances on an n-dimensional mesh are compared with their performances on a binary cube, which is a subset of the n-dimensional mesh. Incremental expansion is studied on an n-dimensional mesh and its impact on performance is measured.; The design of a large parallel computer is often limited by the longest interconnection. In an n-dimensional mesh, the method of interconnection, individual interconnection length and node architecture remain identical as the computer is expanded. A custom node architecture maximizes processing and communication parallelism. Another node architecture uses standard microprocessor components.; Several n-dimensional meshes are connected through serial communication links in the (n + 1)th dimension to support even larger database applications. Each n-dimensional mesh may execute a different database operation or query resulting in an MIMD database computer. Two query execution strategies are presented and their performance are studied using simulation models.