Query optimization in distributed networks of autonomous database systems

ABSTRACT

Large-scale distributed environments, where each node is completely autonomous and offers services to its peers through external communication, pose significant challenges to query processing and optimization. Autonomy is the main source of the problem, as it results in lack of knowledge about any particular node with respect to the information it can produce and its characteristics, for example, cost of production or quality of produced results. In this article, inspired by e-commerce technology, we recognize queries as commodities and model query optimization as a trading negotiation process. Subquery answers and subquery operator execution jobs are traded between nodes until deals are struck with some nodes for all of them. Such trading may also occur recursively, in the sense that some nodes may play the role of intermediaries between other nodes (subcontracting). We identify the key parameters of the overall framework and suggest several potential alternatives for each one. In comparison to trading negotiations for e-commerce, query optimization faces unique new challenges that stem primarily from the fact that queries have a complex structure and can be broken into smaller parts. We address these challenges through a particular instantiation of our framework focusing primarily on the optimization algorithms run on “buying” and “selling” nodes, the evaluation metrics of the queries, and the negotiation strategy. Finally, we present the results of several experiments that demonstrate the performance characteristics of our approach compared to those of traditional query optimization.

REFERENCES

• 1: Bichler, M., Kaukal, M., and Segev, A. 1999. Multi-attribute auctions for electronic procurement. In Proceedings of the 1st IBM IAC Workshop on Internet Based Negotiation Technologies (Yorktown Heights, NY).
• 2: John Collins , Maksim Tsvetovat , Rashmi Sundareswara , Joshua van Tonder , Maria Gini , Bamshad Mobasher, Evaluating risk: flexibility and feasibility in multi-agent contracting, Proceedings of the third annual conference on Autonomous Agents, p.350-351, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301229]
• 3: Conitzer, V. and Sandholm, T. 2003. Complexity results about nash equilibria. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03). Morgan Kaufmann, San Francisco, CA.
• 4: Decoupled Query Optimization for Federated Database Systems, Proceedings of the 18th International Conference on Data Engineering, p.716, February 26-March 01, 2002
• 5: Michael J. Franklin , Björn Thór Jónsson , Donald Kossmann, Performance tradeoffs for client-server query processing, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.149-160, June 04-06, 1996, Montreal, Quebec, Canada
• 6: Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
• 7: Gravelle, H. and Rees, R. 2004. Microeconomics (3rd ed). Pearson Education, England.
• 8: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 9: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• 10: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.2, p.132-151, May 1997 [doi>10.1007/s007780050037]
• 11: Kagel, J. H. 1995. Auctions: A survey of experimental research. In The Handbook of Experimental Economics, J. H. Kagel and A. E. Roth, Eds. Princeton University Press, Princeton, NJ.
• 12: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 13: Donald Kossmann , Konrad Stocker, Iterative dynamic programming: a new class of query optimization algorithms, ACM Transactions on Database Systems (TODS), v.25 n.1, p.43-82, March 2000 [doi>10.1145/352958.352982]
• 14: Sarit Kraus, Strategic negotiation in multiagent environments, MIT Press, Cambridge, MA, 2001
• 15: Bin Liu , Elke A. Rundensteiner, Revisiting pipelined parallelism in multi-join query processing, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 16: Mariposa. 2002. Mariposa Distributed Database Management Systems, User's Manual. Mariposa, Available at http://s2k-ftp.cs.berkeley.edu:8000/mariposa/ /src/alpha-1/mariposa-manual.pdf.
• 17: Mas-Colell, A., Whinston, M. D., and Green, J. R. 1995. Microeconomic Theory. Oxford University Press, New York.
• 18: Julio C. Navas , Michael Wynblatt, The network is the database: data management for highly distributed systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.544-551, May 21-24, 2001, Santa Barbara, California, United States
• 19: Elth Ogston , Stamatis Vassiliadis, A peer-to-peer agent auction, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544776]
• 20: Christos H. Papadimitriou , Mihalis Yannakakis, Multiobjective query optimization, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.52-59, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375560]
• 21: Parunak, H. V. D. 1987. Manufacturing experience with the contract net. In Distributed Artificial Intelligence, Research Notes in Artificial Intelligence, M. N. Huhns, Ed. vol. 1. Pitman, London, England, 285--310.
• 22: Pentaris, F. and Ioannidis, Y. E. 2004. Distributed query optimization by query trading. In EDBT, E. Bertino, S. Christodoulakis, D. Plexousakis, V. Christophides, M. Koubarakis, K. Böhm, and E. Ferrari, Eds. Lecture Notes in Computer Science, vol. 2992. Springer-Verlag, New York, 532--550.
• 23: Rachel Pottinger , Alon Y. Levy, A Scalable Algorithm for Answering Queries Using Views, Proceedings of the 26th International Conference on Very Large Data Bases, p.484-495, September 10-14, 2000
• 24: Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
• 25: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
• 26: 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]
• 27: Smith, R. G. 1980. The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Trans. Comput. 29, 12 (Dec.), 1104--1113.
• 28: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 29: Michael Stonebraker , Paul M. Aoki , Robert Devine , Witold Litwin , Michael A. Olson, Mariposa: A New Architecture for Distributed Data, Proceedings of the Tenth International Conference on Data Engineering, p.54-65, February 14-18, 1994
• 30: Michael Stonebraker , Paul M. Aoki , Witold Litwin , Avi Pfeffer , Adam Sah , Jeff Sidell , Carl Staelin , Andrew Yu, Mariposa: a wide-area distributed database system, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.048-063, January 1996 [doi>10.1007/s007780050015]
• 31: Stanley Y.W. Su , Chunbo Huang , Joachim Hammer , Yihua Huang , Haifei Li , Liu Wang , Youzhong Liu , Charnyote Pluempitiwiriyawej , Minsoo Lee , Herman Lam, An Internet-based negotiation server for e-commerce, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.1, p.72-90, August 2001
• 32: Pinata Winoto , Gordon I. McCalla , Julita Vassileva, An Extended Alternating-Offers Bargaining Protocol for Automated Negotiation in Multi-agent Systems, On the Move to Meaningful Internet Systems, 2002 - DOA/CoopIS/ODBASE 2002 Confederated International Conferences DOA, CoopIS and ODBASE 2002, p.179-194, October 30-November 01, 2002
• 33: Markos Zaharioudakis , Roberta Cochrane , George Lapis , Hamid Pirahesh , Monica Urata, Answering complex SQL queries using automatic summary tables, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.105-116, May 15-18, 2000, Dallas, Texas, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
Query optimization