Query execution in DIRECT

ABSTRACT

In this paper query organization, execution, and optimization in the database machine DIRECT are discussed. We demonstrate that the use of a monitor for each relation referenced by a query along with the use of the NEXT PAGE construct permits the DIRECT back-end controller to assign a query to any number of processors for execution. Furthermore, these constructs also permit the controller to balance the load in the back-end by dynamically adjusting how many processors are assigned to each executing query.We also identify the problem of relation fragmentation which occurs when a query is executed by several processors in parallel and develop a technique for estimating the optimal number of processors to compress a relation so that the execution time of the entire query is minimized. These results appear to be applicable to all database machines which employ parallel processing techniques to enhance query execution.

REFERENCES

• 1: David J. DeWitt, DIRECT - a multiprocessor organization for supporting relational data base management systems, Proceedings of the 5th annual symposium on Computer architecture, p.182-189, April 03-05, 1978 [doi>10.1145/800094.803046]
• 2: Dewitt, D.J., "DIRECT --- A Multiprocessor Organization for Supporting Relational Database Management Systems," IEEE Transactions on Computers, June 1979. Also: Computer Sciences Technical Report #325, Univ. of Wisconsin, June 1978.
• 3: Ozkarahan, E.A., Schuster, S.A., and K.C. Smith, "RAP --- An associative processor for database management," Proceedings of the 1975 NCC, pp. 379--386.
• 4: Schuster, S.A., Ozkarahan, E.A., and K.C. Smith, "A virtual memory system for a relational associative processor," Proceedings of the 1976 NCC, pp. 855--862.
• 5: E. A. Ozkarahan , S. A. Schuster , K. C. Sevcik, Performance evaluation of a relational associative processor, ACM Transactions on Database Systems (TODS), v.2 n.2, p.175-195, June 1977 [doi>10.1145/320544.320553]
• 6: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 7: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]