Query-Processing
Query-Processing
Course Instructor
Dr. Shirshendu Das
IIT Hyderabad
[email protected]
Finding a good execution plan for a query consists of more than just choosing an
implementation for each of the relational operators that appear in the query.
For example, the order in which operators are applied can influence the cost.
Indexing:
Hash based indexing
B+ Tree based indexing
Remember both hashing can be either clustered or unclustered.
Relational algebra:
• Select, Project, Join
• Selection Condition
File operations:
• Scan, Equality search, Range search etc.
3
R
M
4
R
M
5
R
M
6
R
M
7
R
M
Cost:
8
R
M
Cost:
9
R
M
10
R
M
Cost:
11
R
M
12
R
M
Cost:
13
R
M
Cost:
14
R
M
15
R
M
16
R
M
17
R
M
18
R
M
19
R
M
We can retrieve tuples satisfying the condition rname=‘Joe’ by using the index on rname.
If the selection condition is (day < 8/9/94 ∨ rname=‘Joe’) ∧ sid=3, the index on sid
matches the conjunct sid=3.
21
We can use this index to find qualifying tuples and apply day < 8/9/94 ∨ rname=‘Joe’ to
R
M
22
R
M
The first and third steps are straightforward and relatively inexpensive.
23
R
M
In fact, this modification will reduce the cost of the merging passes since fewer tuples are written out in
each pass.
3. In the second pass we read the runs, at a cost of 250 I/Os, and merge them.
4. The total cost is 1,500 I/Os.
5. Which is much lower than the cost of the first approach used to implement projection.
25
R
M
Partitioning:
26
R
M
Duplicate Elimination:
27
R
M
28
R
M
29
R
M
30
R
M
31
R
M
Main Memory
R S
32
R
M
Main Memory
R S
33
R
M
35
R
M
36
R
M
Main Memory
R S
37
R
M
Main Memory
R S
38
R
M
39
R
Main Memory M
R S
40
R
M
41
R
M
Main Memory
R S
42
R
M
43
R
M
Main Memory
R S
44
R
M
Main Memory
R S
45
Block Nested Loop Join With In-Memory Hashing:
R
M
Main Memory
R S
46
R
M
47
R
M
48
R
M
R S
49
R
M
50
R
M
51
R
M
52
R
M
53
Hash Join R
M
Main Memory
Relation R
54
*****This is an example of how partitioning happens in hash based join. The relation (table) considered is not from book (RM).
Hash Join R
Partitions of both R and S using the hash function h. M
Partitions of R
Partitions of S
55
R
Hash Join M
Main Memory
If r is a tuple from R and s is a tuple from S then <r,s> is the tuple in the natural join of R and S provided the condition
56 of
natural join is satisfied by these two tuples.
R
M
57
R
M
58
R
M
59
R
M
60
R
M
61
R
M
62
R
M
63
R
M
64
R
M
65
66
This slide is based on our text book “Database System Concepts”. But you no need
to read book for this. Understanding the contents in slide is enough.
67
This slide is based on our text book “Database System Concepts”. But you no need
to read book for this. Understanding the contents in slide is enough.
68
This slide is based on our text book “Database System Concepts”. But you no need
to read book for this. Understanding the contents in slide is enough.
69
This slide is based on our text book “Database System Concepts”. But you no need
to read book for this. Understanding the contents in slide is enough.
70
This slide is based on our text book “Database System Concepts”. But you no need
to read book for this. Understanding the contents in slide is enough.
71
This slide is based on our text book “Database System Concepts”. But you no need
to read book for this. Understanding the contents in slide is enough.
Assume:
number of pages in T1 as 10
number of pages in T2 as 250
number of buffer pages is 5.
Cost:
1. Applying sort merge join for T1 and T2:
Cost:
2. Applying block nested join for T1 and T2:
72
Assume:
number of pages in T1 as 10
number of pages in T2 as 250
number of buffer pages is 5.
Cost:
1. Applying sort merge join for T1 and T2: 4060 I/O pages
2. Applying block nested join for T1 and T2: 2770 I/O pages
73
Suppose that we have the following two index available:
1. a clustered static hash index on the bid field of
Reserves
2. a hash index on the sid field of Sailors.
74
Suppose that we have the following two index available:
1. a clustered static hash index on the bid field of
Reserves
2. a hash index on the sid field of Sailors.
75
We have the following two index available:
1. a clustered static hash index on the bid field of
Reserves
2. a hash index on the sid field of Sailors.
76
End of Query Processing and
Optimisation
77