Optimization of query streams using semantic prefetching

ABSTRACT

Streams of relational queries submitted by client applications to database servers contain patterns that can be used to predict future requests. We present the Scalpel system, which detects these patterns and optimizes request streams using context-based predictions of future requests. Scalpel uses its predictions to provide a form of semantic prefetching, which involves combining a predicted series of requests into a single request that can be issued immediately. Scalpel's semantic prefetching reduces not only the latency experienced by the application but also the total cost of query evaluation. We describe how Scalpel learns to predict optimizable request patterns by observing the application's request stream during a training phase. We also describe the types of query pattern rewrites that Scalpel's cost-based optimizer considers. Finally, we present empirical results that show the costs and benefits of Scalpel's optimizations.

REFERENCES

• 1: Philip A. Bernstein , Shankar Pal , David Shutt, Context-Based Prefetch for Implementing Objects on Relations, Proceedings of the 25th International Conference on Very Large Data Bases, p.327-338, September 07-10, 1999
• 2: Leonidas Fegaras , David Maier, Optimizing object queries using an effective calculus, ACM Transactions on Database Systems (TODS), v.25 n.4, p.457-516, Dec. 2000 [doi>10.1145/377674.377676]
• 3: Mary Fernandez , Atsuyuki Morishima , Dan Suciu, Efficient evaluation of XML middle-ware queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.103-114, May 21-24, 2001, Santa Barbara, California, United States
• 4: Daniela Florescu , Alon Y. Levy , Dan Suciu , Khaled Yagoub, Optimization of Run-time Management of Data Intensive Web-sites, Proceedings of the 25th International Conference on Very Large Data Bases, p.627-638, September 07-10, 1999
• 5: International Standards Organization. Database language SQL---Part 2: Foundation (SQL / Foundation). ISO/IEC 9075-2:1999, Sept. 1999.
• 6: Tobias Mayr , Praveen Seshadri, Client-site query extensions, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.347-358, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 7: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 8: Praveen Seshadri , Hamid Pirahesh , T. Y. Cliff Leung, Complex Query Decorrelation, Proceedings of the Twelfth International Conference on Data Engineering, p.450-458, February 26-March 01, 1996
• 9: Jayavel Shanmugasundaram , Eugene Shekita , Rimon Barr , Michael Carey , Bruce Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently publishing relational data as XML documents, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.133-154, September 2001