Query optimization in star computer networks

ABSTRACT

Query processing is investigated for relational databases distributed over several computers organized in a star network. Minimal response-time processing strategies are presented for queries involving the select, project, and join commands. These strategies depend on system parameters such as communication costs and different machine processing speeds; database parameters such as relation cardinality and file size; and query parameters such as estimates of the size and number of tuples in the result relation. The optimal strategies specify relation preparation processes, the shipping strategy, serial or parallel processing, and, where applicable, the site of join filtering and merging. Strategies for optimizing select and join queries have been implemented and tested.

REFERENCES

• 1: M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
• 2: BERNSTEIN, P. A., AND CHIU, D.W. Using semi-joins to solve relational queries. Tech. Rep. 7901-7901, Computer Corporation of America, Boston, 1979.
• 3: CHAN, A., AND NIAMIR, B. On estimating the cost of accessing records in blocked database organizations. Comput. J., to be published.
• 4: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 5: EPSTEIN, R., STONEBRAKER, M., AND WONG, E. Distributed query processing in a relational data base system. Memor. UCB/ERL M78/18, Electronics Research Lab., Univ. of California, Berkeley, April 1978.
• 6: 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]
• 7: HEVNER, R., AND YAO, S.B. Query processing on a distributed database. In Proc. 1978 Berkeley Workshop on Distributed Data Management and Computer Networks (Aug. 1978), NTIS, Washington, D.C.
• 8: HEVNER, R., AND YAO, S.B. Query processing in distributed database systems. IEEE Trans. Soflw. Eng. SE-5, 3 (May 1979).
• 9: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 10: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 11: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 12: MERRETT, W., AND OTOO, E. Distribution models of relations. In Proc. 5th Int. Conf. Very Large Data Bases (Rio de Janeiro, Oct. 3-5), ACM, New York, 1979, pp. 418-425.
• 13: B. Niamir, ATTRIBUTE PARTITIONING IN A SELF-ADAPTIVE RELATIONAL DATA BASE SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 14: 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]
• 15: TING, P.D., AND TSICHRITZIS, D.C. A Micro-DBMS for a distributed data base. In Proc. 4th Int. Conf. Very Large Data Bases (West Berlin, Sept. 13-15), ACM, New York, 1978, pp. 200-206.
• 16: TONG, E. Retrieving dispersed data from SDD-I: A system for distributed databases. In Proc. 1977 Berkeley Workshop on Distributed Data Management and Computer Networks (May 1977}, NTIS, Washington, D.C.
• 17: 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]
• 18: 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]
• 19: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Design studies

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems
      D.4.7 Organization and Design
          Subjects: Distributed systems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Performance

Keywords:
query optimization, relational database system, star computer network