tailieunhanh - Query OptimizationYannis E. IoannidisComputer Sciences Department University of Wisconsin

Query Optimization Yannis E. Ioannidis Computer Sciences Department University of Wisconsin Madison, WI 53706 yannis@ 1 Introduction Imagine yourself standing in front of an exquisite bu et lled with numerous delicacies. Your goal is to try them all out, but you need to decide in what order. What exchange of tastes will maximize the overall pleasure of your palate? Although much less pleasurable and subjective, that is the type of problem that query optimizers are called to solve. Given a query, there are many plans that a database management system DBMS can follow to process it and produce its answer. All plans are equivalent. | Query Optimization Yannis E. loannidis Computer Sciences Department University of Wisconsin Madison WI 53706 yannis@ 1 Introduction Imagine yourself standing in front of an exquisite buffet filled with numerous delicacies. Your goal is to try them all out but you need to decide in what order. What exchange of tastes will maximize the overall pleasure of your palate Although much less pleasurable and subjective that is the type of problem that query optimizers are called to solve. Given a query there are many plans that a database management system DBMS can follow to process it and produce its answer. All plans are equivalent in terms of their final output but vary in their cost . the amount of time that they need to run. What is the plan that needs the least amount of time Such query optimization is absolutely necessary in a DBMS. The cost difference between two alternatives can be enormous. For example consider the following database schema which will be Partially supported by the National Science Foundation under Grants IRI-9113736 and IRI-9157368 PYI Award and by grants from DEC IBM HP AT T Informix and Oracle. 1 used throughout this chapter emp name age sal dno dept duo dname floor budget mgr ano acnt ano type balance bno bank bno bname address Further consider the following very simple SQL query select name floor from emp dept where and sal 100K. Assume the characteristics below for the database contents structure and run-time environment Parameter Description Parameter Value Number of emp pages Number of emp tuples Number of emp tuples with sal 100K Number of dept pages Number of dept tuples 20000 100000 10 10 100 Indices of emp Indices of dept Clustered B -tree on 3-levels deep Clustered hashing on average bucket length of pages Number of buffer pages 3 Cost of one disk page access 20ms Consider the following three different plans Pl Through the B -tree find all tuples of emp that satisfy the selection on .