An architecture for query optimization

ABSTRACT

We describe an optimizer for relational queries to databases stored as flat files and Codasyl networks. We include sophisticated manipulations on a broad range of direct access structures (DAS's). To achieve this with minimum additional code, we allow operations like sort, scan, and join to apply to DAS's, and categorize indexes and other DAS's in terms of the operations which can be performed on them. Our storage model, based on indivisible units of access and a small set of associated physical operators, provides a uniform interface to both relational and Codasyl storage mechanisms. The optimizer derives a sequence of internal data structures at successively more detailed levels. For a given query, a graph representing an overview of alternative joins is constructed, and then used to derive a physical graph which considers the physical attributes (location and sort order) of the data objects involved. Using cost predictions and other heuristics, the optimizer prunes the physical graph to produce a final access strategy tree. This layered approach and reliance on primitive operators make explicit (and permit changes to) the universe of possible strategies for the query at hand, and ease extension of the optimizer to new storage structures.

REFERENCES

• 1: {ASTR80} M. M. Astrahan, M. Schkolnick, W. Kim, "Performance of the System R Access Path Selection Mechanism", IFIP, 1980.
• 2: James A. Behymer , Robert A. Ogilive , Alan G. Merten, Analysis of indexed sequential and direct access file organizations, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.389-417, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811522]
• 3: {BLAS76} M.W. Blasgen and K.P. Eswaran, "On the Evaluation of Queries in a Data Base System", IBM Research Report RJ 1945, IBM Research Laboratory, San Jose, California, April, 1976.
• 4: {BLAS77} M.W. Blasgen and K.P. Eswaran, "Storage and Access in Relational Data Bases", IBM Systems Journal, Vol. 16, No. 4, 1977.
• 5: {CHAM76} D.D. Chamberlin et al, "SEQUEL2: A Unified Approach to Data Definition, Manipulation, and Control", IBM Journal of Research and Development, Vol. 20, No. 6, Nov., 1976.
• 6: {CHAN81} A. Chan, S. Fox, K. Lin, D. Ries, "The Design of the ADAPLEX DBMS", Computer Corporation of America Technical Report, CCA-09-81.
• 7: Hai-Yann Hwang , Umeshwar Dayal, Using the Entity-Relationship Model for Implementing Multi-Model Database Systems, Proceedings of the Second International Conference on the Entity-Relationship Approach to Information Modeling and Analysis, p.235-256, October 12-14, 1981
• 8: Won Kim, A new way to compute the product and join of relations, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582278]
• 9: {LORI79} R.A. Lorie, J.F. Nilsson, "An Access Specification Language for a Relational Database System", IBM Journal of Research and Development, Vol. 23, No. 3, May, 1979.
• 10: {MAKI81} A. Makinouchi, M. Tezuka, H. Kitakami, and S. Adachi, "The Optimization Strategy for Query Evaluation in RDB/V1", Proc. Seventh Int. Conf. on Very Large Databases, Cannes, France, Sept. 9--11, 1981.
• 11: {ROSE82} A. Rosenthal and D. Reiner, "Querying Relational Views of Networks", in preparation.
• 12: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 13: {WHAN81} K.-Y. Whang, G. Wiederhold, D. Sagalowicz, "Separability --- An Approach to Physical Database Design", Proc. Seventh Int. Conf. on Very Large Databases, Cannes, France, Sept. 9--11, 1981.
• 14: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 15: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 16: S. Bing Yao, Optimization of query evaluation algorithms, ACM Transactions on Database Systems (TODS), v.4 n.2, p.133-155, June 1979 [doi>10.1145/320071.320072]