Query Optimization
We must consider the interaction of evaluation technique when choosing evaluation plans. If we choose the cheapest algorithm for each operation independently it may not yield best algorithm as overall. For example: Merge-join may cost little more than hash-join but may provide output which is not only sorted but also reduces the cost for an outer level aggregation. The nested-loop join may provide opportunity for pipelining. Practical query optimizers incorporate elements of two broad approaches and they are as follows: Searches all the plans and chooses the best plan in a cost-based fashion. Uses heuristics to choose a plan. With the dynamic programming time complexity of optimization with bushy trees is O (3n). With n = 10, this number is 59000 instead of 176 billion! Space complexity is O (2n). If we consider left-deep trees only then time complexity of finding best join order is O(n 2n). Space complexity remains atO (2n). Cost-based optimization is expensive but worthwhile for queries on large datasets (typical queries have small n, generally < 10). Cost-based optimization is expensive even with dynamic programming. The systems may use heuristics to reduce the number of choices that must be made in a cost-based fashion.
Summary
We must consider the interaction of evaluation technique when choosing evaluation plans. If we choose the cheapest algorithm for each operation independently it may not yield best algorithm as overall. For example: Merge-join may cost little more than hash-join but may provide output which is not only sorted but also reduces the cost for an outer level aggregation. The nested-loop join may provide opportunity for pipelining. Practical query optimizers incorporate elements of two broad approaches and they are as follows: Searches all the plans and chooses the best plan in a cost-based fashion. Uses heuristics to choose a plan. With the dynamic programming time complexity of optimization with bushy trees is O (3n). With n = 10, this number is 59000 instead of 176 billion! Space complexity is O (2n). If we consider left-deep trees only then time complexity of finding best join order is O(n 2n). Space complexity remains atO (2n). Cost-based optimization is expensive but worthwhile for queries on large datasets (typical queries have small n, generally < 10). Cost-based optimization is expensive even with dynamic programming. The systems may use heuristics to reduce the number of choices that must be made in a cost-based fashion.
Things to Remember
- We must consider the interaction of evaluation technique when choosing evaluation plans. If we choose the cheapest algorithm for each operation independently it may not yield best algorithm as overall.
- For example: Merge-join may cost little more than hash-join but may provide output which is not only sorted but also reduces the cost for an outer level aggregation.
- The nested-loop join may provide opportunity for pipelining.
- Practical query optimizers incorporate elements of two broad approaches and they are as follows:
- Searches all the plans and chooses the best plan in a cost-based fashion.
- Uses heuristics to choose a plan.
- With the dynamic programming time complexity of optimization with bushy trees is O (3n). With n = 10, this number is 59000 instead of 176 billion! Space complexity is O (2n). If we consider left-deep trees only then time complexity of finding best join order is O(n 2n).
- Cost-based optimization is expensive but worthwhile for queries on large datasets (typical queries have small n, generally < 10).
- Cost-based optimization is expensive even with dynamic programming. The systems may use heuristics to reduce the number of choices that must be made in a cost-based fashion.
MCQs
No MCQs found.
Subjective Questions
Q1:
x + 3 = 5
Type: Very_short Difficulty: Easy
<p>or, x + 3 = 5<br />or, x = 5 - 3<br />∴ x = 2<br /><br /></p>
Q2:
x - 2 = 10
Type: Very_short Difficulty: Easy
<p>or, x - 2 = 10<br />or, x = 10 + 2<br />∴ x = 12</p>
Q3:
5x = 15
Type: Very_short Difficulty: Easy
<p>or, 5x = 15<br />or, x = \(\frac{15}{5}\)<br />∴ x = 3</p>
Q4:
\(\frac{x}{2}\) = 7
Type: Very_short Difficulty: Easy
<p>or, \(\frac{x}{2}\) = 7<br />or, x = 7 × 2<br />∴ x = 14</p>
Q5:
4(3 - x) = 2x - 15
Type: Short Difficulty: Easy
<p>or, 4(3 - x) = 2x - 15<br />or, 12 - 4x = 2x - 15<br />or, -4x - 2x = -15 - 12<br />or, -6x = -27<br />or, x = \(\frac{27}{6}\)<br />∴ x = \(\frac{9}{2}\)</p>
Q6:
\(\frac{3x - 5}{3}\) + x = \(\frac{5}{6}\) - \(\frac{2x + 3}{2}\)
Type: Long Difficulty: Easy
<p>or, \(\frac{3x - 5}{3}\) + x = \(\frac{5}{6}\) - \(\frac{2x + 3}{2}\)<br />or, \(\frac{3x - 5 + 3x}{3}\) = \(\frac{5 - 3(2x + 3)}{6}\)<br />or, \(\frac{6x - 5}{3}\) = \(\frac{5 - 6x - 9}{6}\)<br />or, \(\frac{6x - 5}{3}\) = \(\frac{-4 - 6x}{6}\)<br />or, 6(6x - 5) = 3 (-4 - 6x)<br />or, 36x - 30 = -12 - 18x<br />or, 36x + 18x = -12 + 30<br />or, 54x = 18 <br />or, x = \(\frac{18}{54}\) <br />∴ x = \(\frac{1}{3}\)</p>
Q7:
Solve
x + 20% of x = Rs 180
Type: Short Difficulty: Easy
<p>or, x + 20% of x = Rs 180<br />or, x + \(\frac{20}{100}\) × x = Rs 180<br />or, x + \(\frac{x}{5}\) = Rs 180<br />or, \(\frac{5x + x}{5}\) = Rs 180<br />or, \(\frac{6x}{5}\) = rs Rs 180<br />or, 6x = 5 × Rs 180<br />or, x = Rs \(\frac{900}{6}\) <br />or, x = Rs 150<br />∴ x = Rs 150</p>
Q8:
The sum of two numbers is 35. if one of the numbers is 21, find the other number.
Type: Short Difficulty: Easy
<p>Let the other number be x.<br />Now,<br />or, x + 21 = 35<br />or, x = 35 - 21<br />or, x = 14<br />So, the required number is 14.</p>
Q9:
If the sum of three consecutive even numbers is 30, find them.
Type: Long Difficulty: Easy
<p>Let the smaller even number be x.<br />Then, the second consecutive even number = x + 2<br />And, the third consecutive even number = x + 4<br />Now,<br />or, x + (x + 2) + (x + 4) = 30<br />or, 3x + 6 = 30 <br />or, 3x = 30 - 6<br />or, x = \(\frac{24}{3}\) <br />or, x = 8<br />∴ The first even number = x = 8<br />The secomd even number = x + 2 = 8 + 2 = 10<br />Th e third even number = x + 4 = 8 + 4 = 12<br />So, the reuired consecutive even numbers are 8, 10 and 12.</p>
Q10:
A sum of Rs 50 is dived into two parts. If the greater part exceeds the smaller by Rs 10, find the parts of the sum.
Type: Short Difficulty: Easy
<p>Let the smaller part of the sum be Rs x.<br />Then,<br />the greater part of the sum = Rs (x + 10) <br />Now,<br />or, x + (x + 10) = Rs 50<br />or, 2x = Rs (50 - 10)<br />or, x = Rs \(\frac{40}{2}\)<br />or, x = Rs 20<br />∴ The smaller part of the sum = x = Rs 20<br />The greater part of the sum = Rs (x + 10) = Rs (20 + 10) = Rs 30</p>
Videos
Solving Two Step Equations
Solving Two Step Equations Involving Fractions
Query Optimization
Query Optimization
We must consider the interaction of evaluation technique when choosing evaluation plans. If we choose the cheapest algorithm for each operation independently it may not yield the best algorithm as overall. For example, Merge-join may cost little more than hash-join but may provide an output which is not only sorted but also reduces the cost for an outer level aggregation. The nested-loop join may provide an opportunity for pipelining. Practical query optimizers incorporate elements of two broad approaches and they are as follows:
- Searches all the plans and chooses the best plan in a cost-based fashion.
- Uses heuristics to choose a plan.
Cost-Based Optimization
Let us consider finding the best join order for r1⋈r2⋈..... rn. There are (2(n-1))! / (n-1)! Different join orders for above expressions. With n = 7, the number is 665280 and with n = 10, the number is greater than 176 billion! There is no need to generate all the join orders. With the use of dynamic programming, the least cost join order for any subset of {r1, r2,......, rn} is computed only once and stored for future use.
Cost of Optimization
With the dynamic programming time, the complexity of optimization with bushy trees is O (3n). With n = 10, this number is 59000 instead of 176 billion! Space complexity is O (2n). To find the best left-deep join tree for a set of n relations, we must take the following steps:
- Consider n alternatives with one relation as right-hand side input and other relation as left-hand side input.
- Modify the optimization algorithm:
Replace "for each non-empty subset S1 of S such that S1≠ S"
By: "for each relation r in S, let S1 = S - r".
If we consider left-deep trees only then time complexity of finding best join order is O(n 2n). Space complexity remains atO (2n). Cost-based optimization is expensive but worthwhile for queries on large datasets (typical queries have small n, generally < 10).
Heuristic Optimization
Cost-based optimization is expensive even with dynamic programming. The systems may use heuristics to reduce the number of choices that must be made in a cost-based fashion. Heuristic optimization transforms a query-tree by using a set of rules that typically (but not in all cases) improves execution performance and they are presented below:
- Performs selection early (reduces the number of tuples).
- Performs projection early (reduces the number of attributes).
- Performs most restrictive selection and join operations (i.e. with smallest result size) before other similar operations.
- Some systems use only heuristics while others combine heuristics with partial cost-based optimization.
References:
- H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
- A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
- F.Korth, Henry. Database System Concepts. 6th edition.
Lesson
Query Processing and Optimization
Subject
Computer Engineering
Grade
Engineering
Recent Notes
No recent notes.
Related Notes
No related notes.