CS315: DATABASE S YSTEMS

Q UERY P ROCESSING

Arnab Bhattacharya
arnabb@[Link]

Computer Science and Engineering,

Indian Institute of Technology, Kanpur
[Link]

2nd semester, 2024-25

Tue, Wed 12:00-13:15

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 1 / 33

 Query
Query in a high-level language is first parsed and validated
s e l e c t c p i from s t u d e n t s where c p i > 9 ;

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 2 / 33

 Query
Query in a high-level language is first parsed and validated
s e l e c t c p i from s t u d e n t s where c p i > 9 ;

Query planner next outputs an equivalent expression in relational

algebra
Πcpi (σcpi>9 (students))
A query order tree is created

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 2 / 33

 Query
Query in a high-level language is first parsed and validated
s e l e c t c p i from s t u d e n t s where c p i > 9 ;

Query planner next outputs an equivalent expression in relational

algebra
Πcpi (σcpi>9 (students))
A query order tree is created
All equivalent evaluation plans are then generated
Πcpi (σcpi>9 (students))
σcpi>9 (Πcpi (students))

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 2 / 33

 Query
Query in a high-level language is first parsed and validated
s e l e c t c p i from s t u d e n t s where c p i > 9 ;

Query planner next outputs an equivalent expression in relational

algebra
Πcpi (σcpi>9 (students))
A query order tree is created
All equivalent evaluation plans are then generated
Πcpi (σcpi>9 (students))
σcpi>9 (Πcpi (students))
Query optimizer next decides on the best evaluation plan among
all equivalent plans
Algorithms
Metadata
Statistics of data

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 2 / 33

 Query
Query in a high-level language is first parsed and validated
s e l e c t c p i from s t u d e n t s where c p i > 9 ;

Query planner next outputs an equivalent expression in relational

algebra
Πcpi (σcpi>9 (students))
A query order tree is created
All equivalent evaluation plans are then generated
Πcpi (σcpi>9 (students))
σcpi>9 (Πcpi (students))
Query optimizer next decides on the best evaluation plan among
all equivalent plans
Algorithms
Metadata
Statistics of data
Query code is finally generated and processed

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 2 / 33

 Query Cost
Factors that affect the runtime of the query
Disk accesses
CPU time
Network communication
Buffering and caching effects
In a non-distributed setting, disk access is the most dominant
factor
In a distributed environment, it is network communication

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 3 / 33

 Query Cost
Factors that affect the runtime of the query
Disk accesses
CPU time
Network communication
Buffering and caching effects
In a non-distributed setting, disk access is the most dominant
factor
In a distributed environment, it is network communication
Disk access can be estimated as a total of
Number of seeks times average seek cost
Number of blocks read or written times average block transfer cost
Write cost can be more since data is verified

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 3 / 33

 Query Cost
Factors that affect the runtime of the query
Disk accesses
CPU time
Network communication
Buffering and caching effects
In a non-distributed setting, disk access is the most dominant
factor
In a distributed environment, it is network communication
Disk access can be estimated as a total of
Number of seeks times average seek cost
Number of blocks read or written times average block transfer cost
Write cost can be more since data is verified
For s seeks and b block transfers, simply estimated as
s × ts + b × tb
Ignores CPU time and buffer management issues

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 3 / 33

 Selection: Linear Search
L INEAR SEARCH
Always applicable

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 4 / 33

 Selection: Linear Search
L INEAR SEARCH
Always applicable
Scan all file blocks and test each record

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 4 / 33

 Selection: Linear Search
L INEAR SEARCH
Always applicable
Scan all file blocks and test each record
Cost for a relation containing b blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 4 / 33

 Selection: Linear Search
L INEAR SEARCH
Always applicable
Scan all file blocks and test each record
Cost for a relation containing b blocks
1 seek
b transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 4 / 33

 Selection: Linear Search
L INEAR SEARCH
Always applicable
Scan all file blocks and test each record
Cost for a relation containing b blocks
1 seek
b transfers
If equality on key or unique attribute, then

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 4 / 33

 Selection: Linear Search
L INEAR SEARCH
Always applicable
Scan all file blocks and test each record
Cost for a relation containing b blocks
1 seek
b transfers
If equality on key or unique attribute, then
b/2 transfers on average

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 4 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is
⌈log2 b⌉ seeks
⌈log2 b⌉ transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is
⌈log2 b⌉ seeks
⌈log2 b⌉ transfers
If one block does not contain all records

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is
⌈log2 b⌉ seeks
⌈log2 b⌉ transfers
If one block does not contain all records
Additional block transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is
⌈log2 b⌉ seeks
⌈log2 b⌉ transfers
If one block does not contain all records
Additional block transfers
Greater than

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is
⌈log2 b⌉ seeks
⌈log2 b⌉ transfers
If one block does not contain all records
Additional block transfers
Greater than
Locate matching record
Traverse forward and do additional transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is
⌈log2 b⌉ seeks
⌈log2 b⌉ transfers
If one block does not contain all records
Additional block transfers
Greater than
Locate matching record
Traverse forward and do additional transfers
Lesser than

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Binary Search
B INARY SEARCH
File must be sorted on attribute which is searched
Equality
Cost for locating the first record is
⌈log2 b⌉ seeks
⌈log2 b⌉ transfers
If one block does not contain all records
Additional block transfers
Greater than
Locate matching record
Traverse forward and do additional transfers
Lesser than
Scan from beginning till matching record
Reduces to linear search

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 5 / 33

 Selection: Index Search
I NDEX SEARCH
B+-tree of height h

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 6 / 33

 Selection: Index Search
I NDEX SEARCH
B+-tree of height h
Equality using primary index

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 6 / 33

 Selection: Index Search
I NDEX SEARCH
B+-tree of height h
Equality using primary index
h + 1 seeks, where h is the height of B+-tree
h + m transfers
where m is the total number of blocks containing matching records
For key, m = 1

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 6 / 33

 Selection: Index Search
I NDEX SEARCH
B+-tree of height h
Equality using primary index
h + 1 seeks, where h is the height of B+-tree
h + m transfers
where m is the total number of blocks containing matching records
For key, m = 1
Equality using secondary index

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 6 / 33

 Selection: Index Search
I NDEX SEARCH
B+-tree of height h
Equality using primary index
h + 1 seeks, where h is the height of B+-tree
h + m transfers
where m is the total number of blocks containing matching records
For key, m = 1
Equality using secondary index
h + n seeks, where h is the height of the index tree
h + n transfers
where n is the total number of matching records, each in a
separate block
For key, n = 1

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 6 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers
Lesser than (A ≤ v ) using primary index

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers
Lesser than (A ≤ v ) using primary index
1 seek to the first block
h + 1 seeks and h + 1 transfers to locate v

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers
Lesser than (A ≤ v ) using primary index
1 seek to the first block
h + 1 seeks and h + 1 transfers to locate v
or
n transfers till v is located
Use sibling leaf pointers to locate all other matching

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers
Lesser than (A ≤ v ) using primary index
1 seek to the first block
h + 1 seeks and h + 1 transfers to locate v
or
n transfers till v is located
Use sibling leaf pointers to locate all other matching
Greater than (A ≥ v ) using secondary index

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers
Lesser than (A ≤ v ) using primary index
1 seek to the first block
h + 1 seeks and h + 1 transfers to locate v
or
n transfers till v is located
Use sibling leaf pointers to locate all other matching
Greater than (A ≥ v ) using secondary index
h + 1 seeks and h + 1 transfers to locate v
Use sibling leaf pointers to locate all other matching records
resulting in n more seeks and n more transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers
Lesser than (A ≤ v ) using primary index
1 seek to the first block
h + 1 seeks and h + 1 transfers to locate v
or
n transfers till v is located
Use sibling leaf pointers to locate all other matching
Greater than (A ≥ v ) using secondary index
h + 1 seeks and h + 1 transfers to locate v
Use sibling leaf pointers to locate all other matching records
resulting in n more seeks and n more transfers
Lesser than (A ≤ v ) using secondary index

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33

 Selection: Index Search (contd.)
Greater than (A ≥ v ) using primary index
h + 1 seeks and h + 1 transfers to locate v
Scan for the rest of the relation resulting in n more transfers
Lesser than (A ≤ v ) using primary index
1 seek to the first block
h + 1 seeks and h + 1 transfers to locate v
or
n transfers till v is located
Use sibling leaf pointers to locate all other matching
Greater than (A ≥ v ) using secondary index
h + 1 seeks and h + 1 transfers to locate v
Use sibling leaf pointers to locate all other matching records
resulting in n more seeks and n more transfers
Lesser than (A ≤ v ) using secondary index
h + 1 seeks and h + 1 transfers to locate v
Use sibling leaf pointers to locate all other matching records
resulting in n more seeks and n more transfers
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 7 / 33
 Selection on Multiple Attributes
Conjunction: AND

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly
Disjunction: OR

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly
Disjunction: OR
Union
If some attribute does not have an index, then linear scan

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly
Disjunction: OR
Union
If some attribute does not have an index, then linear scan
Negation of conjunction
May be very inefficient

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly
Disjunction: OR
Union
If some attribute does not have an index, then linear scan
Negation of conjunction
May be very inefficient
Negation of equality (A , v )

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly
Disjunction: OR
Union
If some attribute does not have an index, then linear scan
Negation of conjunction
May be very inefficient
Negation of equality (A , v )
Linear scan
Index selects leaf pointers for which corresponding records will not
be retrieved

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33

 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly
Disjunction: OR
Union
If some attribute does not have an index, then linear scan
Negation of conjunction
May be very inefficient
Negation of equality (A , v )
Linear scan
Index selects leaf pointers for which corresponding records will not
be retrieved
Negation of comparison
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33
 Selection on Multiple Attributes
Conjunction: AND
Single index is available
For each record satisfying it, test the other attributes
Multiple indexes are available
Use one likely to produce lesser tuples (e.g., equality)
Intersection
If no attribute has an index, test explicitly
Disjunction: OR
Union
If some attribute does not have an index, then linear scan
Negation of conjunction
May be very inefficient
Negation of equality (A , v )
Linear scan
Index selects leaf pointers for which corresponding records will not
be retrieved
Negation of comparison is just another comparison
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 8 / 33
 Sorting
Display purposes
Certain operations such as join can be implemented efficiently on
sorted relations

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 9 / 33

 Sorting
Display purposes
Certain operations such as join can be implemented efficiently on
sorted relations
Index provides a logically sorted view

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 9 / 33

 Sorting
Display purposes
Certain operations such as join can be implemented efficiently on
sorted relations
Index provides a logically sorted view
Tuples need to be physically sorted

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 9 / 33

 Sorting
Display purposes
Certain operations such as join can be implemented efficiently on
sorted relations
Index provides a logically sorted view
Tuples need to be physically sorted
When the relation fits in memory, QUICKSORT can be used
When it does not, external sorting algorithms are used

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 9 / 33

 Sorting
Display purposes
Certain operations such as join can be implemented efficiently on
sorted relations
Index provides a logically sorted view
Tuples need to be physically sorted
When the relation fits in memory, QUICKSORT can be used
When it does not, external sorting algorithms are used
E XTERNAL MERGESORT or E XTERNAL SORT- MERGE

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 9 / 33

 External Mergesort
Assume only m blocks can be put into memory
Size of relation is more than m blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 10 / 33

 External Mergesort
Assume only m blocks can be put into memory
Size of relation is more than m blocks
Create sorted runs
Read m blocks at a time
Sort them in-memory using any algorithm such as quicksort
Write them back to disk

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 10 / 33

 External Mergesort
Assume only m blocks can be put into memory
Size of relation is more than m blocks
Create sorted runs
Read m blocks at a time
Sort them in-memory using any algorithm such as quicksort
Write them back to disk
Merge m − 1 runs ((m − 1)-way merge)
Read in first block of m − 1 runs
Output the first record to buffer block (m-th block in memory)
Continue till buffer block is full
Write buffer block to disk
When a block of a particular run is exhausted, read in the next block
of the run

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 10 / 33

 External Mergesort
Assume only m blocks can be put into memory
Size of relation is more than m blocks
Create sorted runs
Read m blocks at a time
Sort them in-memory using any algorithm such as quicksort
Write them back to disk
Merge m − 1 runs ((m − 1)-way merge)
Read in first block of m − 1 runs
Output the first record to buffer block (m-th block in memory)
Continue till buffer block is full
Write buffer block to disk
When a block of a particular run is exhausted, read in the next block
of the run
Continue with (m − 1)-way merge till the number of sorted runs is
less than m
The last (m − 1)-way merge sorts the relation
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 10 / 33
 Example
21
18
write
21 18
read 19 18 read 36
19
write
write 21 21
19
read 32 21 79 32
36
32 21 32 71 18
21 71 71 32 79 19
21
71 79 36 21
18 18 18 32
19 19 19 71 36
32
79 79 79 79 44
36
36 57
36 36 36
98 read 71 71
98 57 44 write
57 36 79
81 57 98 81
57 36
44 71 98
81 44 44 44
input 57 44 output
44 81
57 81
sorted ...
81 98
runs

98 79
81 81
merge merge
pass 1 pass 2

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 11 / 33

 Cost of External Mergesort
Total number of blocks is b
Initial number of sorted runs is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 12 / 33

 Cost of External Mergesort
Total number of blocks is b
Initial number of sorted runs is n = ⌈b/m⌉
In each merge pass, m − 1 runs are sorted
Therefore, total number of merge passes required is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 12 / 33

 Cost of External Mergesort
Total number of blocks is b
Initial number of sorted runs is n = ⌈b/m⌉
In each merge pass, m − 1 runs are sorted
Therefore, total number of merge passes required is r = ⌈logm−1 n⌉
During each of these passes and the first pass, all blocks are read
and written
There is an initial pass of creating runs
Hence, total number of block transfers is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 12 / 33

 Cost of External Mergesort
Total number of blocks is b
Initial number of sorted runs is n = ⌈b/m⌉
In each merge pass, m − 1 runs are sorted
Therefore, total number of merge passes required is r = ⌈logm−1 n⌉
During each of these passes and the first pass, all blocks are read
and written
There is an initial pass of creating runs
Hence, total number of block transfers is 2br + 2b

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 12 / 33

 Cost of External Mergesort (contd.)
Initial pass to created sorted runs reads m blocks at a time
Therefore, number of seeks is 2n for reading and writing

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 13 / 33

 Cost of External Mergesort (contd.)
Initial pass to created sorted runs reads m blocks at a time
Therefore, number of seeks is 2n for reading and writing
During the merge passes, blocks from different runs may not be
read consecutively
Consequently, each read and write for another run may move the
disk head away, thereby requiring a seek every time
Hence, number of seeks for these passes is 2br
Therefore, total number of seeks is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 13 / 33

 Cost of External Mergesort (contd.)
Initial pass to created sorted runs reads m blocks at a time
Therefore, number of seeks is 2n for reading and writing
During the merge passes, blocks from different runs may not be
read consecutively
Consequently, each read and write for another run may move the
disk head away, thereby requiring a seek every time
Hence, number of seeks for these passes is 2br
Therefore, total number of seeks is 2n + 2br in the worst case

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 13 / 33

 Join
Different join algorithms
N ESTED - LOOP JOIN
B LOCK NESTED - LOOP JOIN
I NDEXED NESTED - LOOP JOIN
M ERGE JOIN
H ASH JOIN
Choice depends on cost estimates

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 14 / 33

 Nested-Loop Join
Applicable for any kind of join
For each record tr ∈ r and for each record ts ∈ s, if tr Z ts satisfies
the join condition, add it to result
Outer relation r : outer loop; inner relation s: inner loop

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 15 / 33

 Block Nested-Loop Join
Applicable for any kind of join
Disk block aware version of nested-loop
For each block lr ∈ r and for each block ls ∈ s, test if every record
tr ∈ lr and ts ∈ ls satisfies the join condition; if so, add to the result

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 16 / 33

 Cost of Block Nested-Loop Join: Minimal
Minimal assumption that only 2 blocks fit in memory

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 17 / 33

 Cost of Block Nested-Loop Join: Minimal
Minimal assumption that only 2 blocks fit in memory
Block transfers
bs transfers every time a block lr is read
br transfers for blocks in r
Therefore, total is br + br × bs transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 17 / 33

 Cost of Block Nested-Loop Join: Minimal
Minimal assumption that only 2 blocks fit in memory
Block transfers
bs transfers every time a block lr is read
br transfers for blocks in r
Therefore, total is br + br × bs transfers
Seeks
1 seek for records in s every time a block lr is read
br seeks for records in r
Therefore, total is br + br = 2br seeks
Smaller relation should be

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 17 / 33

 Cost of Block Nested-Loop Join: Minimal
Minimal assumption that only 2 blocks fit in memory
Block transfers
bs transfers every time a block lr is read
br transfers for blocks in r
Therefore, total is br + br × bs transfers
Seeks
1 seek for records in s every time a block lr is read
br seeks for records in r
Therefore, total is br + br = 2br seeks
Smaller relation should be outer

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 17 / 33

 Cost of Block Nested-Loop Join
Assume m blocks of memory to be available

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 18 / 33

 Cost of Block Nested-Loop Join
Assume m blocks of memory to be available
1 left for inner relation s
m − 1 blocks read at a time from outer relation r

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 18 / 33

 Cost of Block Nested-Loop Join
Assume m blocks of memory to be available
1 left for inner relation s
m − 1 blocks read at a time from outer relation r
Number of such runs is n = ⌈br /(m − 1)⌉

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 18 / 33

 Cost of Block Nested-Loop Join
Assume m blocks of memory to be available
1 left for inner relation s
m − 1 blocks read at a time from outer relation r
Number of such runs is n = ⌈br /(m − 1)⌉
Block transfers
For r : br
For s: n × bs

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 18 / 33

 Cost of Block Nested-Loop Join
Assume m blocks of memory to be available
1 left for inner relation s
m − 1 blocks read at a time from outer relation r
Number of such runs is n = ⌈br /(m − 1)⌉
Block transfers
For r : br
For s: n × bs
Seeks
For r : n
For s: n
Smaller relation should be

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 18 / 33

 Cost of Block Nested-Loop Join
Assume m blocks of memory to be available
1 left for inner relation s
m − 1 blocks read at a time from outer relation r
Number of such runs is n = ⌈br /(m − 1)⌉
Block transfers
For r : br
For s: n × bs
Seeks
For r : n
For s: n
Smaller relation should be outer

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 18 / 33

 Example
r : 40000 tuples at 200 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r
Number of runs is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r
Number of runs is n = ⌈200/25⌉ = 8

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r
Number of runs is n = ⌈200/25⌉ = 8
In each run, s requires 1 seek and 250 transfers
Total is 8 seeks and 2000 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r
Number of runs is n = ⌈200/25⌉ = 8
In each run, s requires 1 seek and 250 transfers
Total is 8 seeks and 2000 transfers
r requires 8 seeks and 200 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r
Number of runs is n = ⌈200/25⌉ = 8
In each run, s requires 1 seek and 250 transfers
Total is 8 seeks and 2000 transfers
r requires 8 seeks and 200 transfers
Total is 16 seeks and 2200 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r
Number of runs is n = ⌈200/25⌉ = 8
In each run, s requires 1 seek and 250 transfers
Total is 8 seeks and 2000 transfers
r requires 8 seeks and 200 transfers
Total is 16 seeks and 2200 transfers
If s made outer,

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer (+1 for inner)
Outer should be r
Number of runs is n = ⌈200/25⌉ = 8
In each run, s requires 1 seek and 250 transfers
Total is 8 seeks and 2000 transfers
r requires 8 seeks and 200 transfers
Total is 16 seeks and 2200 transfers
If s made outer, 20 seeks and 2250 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 19 / 33

 Indexed Nested-Loop Join
Indexed version of the block nested-loop algorithm
Applicable when inner relation has an index on the joining attribute
For each block lr ∈ r and for each record tr ∈ lr , use index on s to
locate records ts ∈ s that satisfies the join condition

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 20 / 33

 Indexed Nested-Loop Join
Indexed version of the block nested-loop algorithm
Applicable when inner relation has an index on the joining attribute
For each block lr ∈ r and for each record tr ∈ lr , use index on s to
locate records ts ∈ s that satisfies the join condition
Most effective when the join condition is equality

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 20 / 33

 Cost of Indexed Nested-Loop Join
Assumption is that m blocks are available in memory

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 21 / 33

 Cost of Indexed Nested-Loop Join
Assumption is that m blocks are available in memory
m − 1 blocks from outer relation r can be read at a time

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 21 / 33

 Cost of Indexed Nested-Loop Join
Assumption is that m blocks are available in memory
m − 1 blocks from outer relation r can be read at a time
Assume cost of searching index on s is cs seeks and ct transfers
Typically, cs and ct are height h of B+-tree

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 21 / 33

 Cost of Indexed Nested-Loop Join
Assumption is that m blocks are available in memory
m − 1 blocks from outer relation r can be read at a time
Assume cost of searching index on s is cs seeks and ct transfers
Typically, cs and ct are height h of B+-tree
Cost for r is n = ⌈br /(m − 1)⌉ seeks and br transfers
Therefore, total is n + nr × cs seeks and br + nr × ct transfers
Block processing done to reduce nr to br

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 21 / 33

 Cost of Indexed Nested-Loop Join
Assumption is that m blocks are available in memory
m − 1 blocks from outer relation r can be read at a time
Assume cost of searching index on s is cs seeks and ct transfers
Typically, cs and ct are height h of B+-tree
Cost for r is n = ⌈br /(m − 1)⌉ seeks and br transfers
Therefore, total is n + nr × cs seeks and br + nr × ct transfers
Block processing done to reduce nr to br
If index is available on both relations, like block nested-loop,
smaller relation should be

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 21 / 33

 Cost of Indexed Nested-Loop Join
Assumption is that m blocks are available in memory
m − 1 blocks from outer relation r can be read at a time
Assume cost of searching index on s is cs seeks and ct transfers
Typically, cs and ct are height h of B+-tree
Cost for r is n = ⌈br /(m − 1)⌉ seeks and br transfers
Therefore, total is n + nr × cs seeks and br + nr × ct transfers
Block processing done to reduce nr to br
If index is available on both relations, like block nested-loop,
smaller relation should be outer

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 21 / 33

 Cost of Indexed Nested-Loop Join
Assumption is that m blocks are available in memory
m − 1 blocks from outer relation r can be read at a time
Assume cost of searching index on s is cs seeks and ct transfers
Typically, cs and ct are height h of B+-tree
Cost for r is n = ⌈br /(m − 1)⌉ seeks and br transfers
Therefore, total is n + nr × cs seeks and br + nr × ct transfers
Block processing done to reduce nr to br
If index is available on both relations, like block nested-loop,
smaller relation should be outer
Generally, all levels of B+-tree are held in memory except the last
Then, cost of index search falls to cs = ct = 1

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 21 / 33

 Example
r : 40000 tuples at 200 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner
Outer should be

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner
Outer should be s

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner
Outer should be s
Number of runs is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner
Outer should be s
Number of runs is n = ⌈250/25⌉ = 10

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner
Outer should be s
Number of runs is n = ⌈250/25⌉ = 10
In each run, r requires 1 seek and 1 transfer
Total is 25000 seeks and 25000 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner
Outer should be s
Number of runs is n = ⌈250/25⌉ = 10
In each run, r requires 1 seek and 1 transfer
Total is 25000 seeks and 25000 transfers
s requires 10 seeks and 250 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 25 for outer and enough for inner
Outer should be s
Number of runs is n = ⌈250/25⌉ = 10
In each run, r requires 1 seek and 1 transfer
Total is 25000 seeks and 25000 transfers
s requires 10 seeks and 250 transfers
Total is 25010 seeks and 25250 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 22 / 33

 Merge Join or Sort-Merge Join
Applicable only when the join condition is equality
Relations need to be sorted according to the joining attribute

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 23 / 33

 Merge Join or Sort-Merge Join
Applicable only when the join condition is equality
Relations need to be sorted according to the joining attribute
Proceed in sorted order on two relations
If records match, output; otherwise, advance to next record
Join step is similar to merge step in mergesort

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 23 / 33

 Merge Join or Sort-Merge Join
Applicable only when the join condition is equality
Relations need to be sorted according to the joining attribute
Proceed in sorted order on two relations
If records match, output; otherwise, advance to next record
Join step is similar to merge step in mergesort
If relations are not sorted, secondary index on attributes can be
used
H YBRID MERGE JOIN algorithm merges sorted records in one
relation with B+-tree leaves of other relation

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 23 / 33

 Cost of Merge Join
Each record is read only once
Consequently, each block is read only once

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 24 / 33

 Cost of Merge Join
Each record is read only once
Consequently, each block is read only once
However, blocks may be read in an interleaved manner

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 24 / 33

 Cost of Merge Join
Each record is read only once
Consequently, each block is read only once
However, blocks may be read in an interleaved manner
If only 2 blocks of memory are available (1 for each), cost is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 24 / 33

 Cost of Merge Join
Each record is read only once
Consequently, each block is read only once
However, blocks may be read in an interleaved manner
If only 2 blocks of memory are available (1 for each), cost is
br + bs transfers
br + bs seeks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 24 / 33

 Cost of Merge Join
Each record is read only once
Consequently, each block is read only once
However, blocks may be read in an interleaved manner
If only 2 blocks of memory are available (1 for each), cost is
br + bs transfers
br + bs seeks
If m = m′ /2 blocks of memory are available for each relation, cost
is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 24 / 33

 Cost of Merge Join
Each record is read only once
Consequently, each block is read only once
However, blocks may be read in an interleaved manner
If only 2 blocks of memory are available (1 for each), cost is
br + bs transfers
br + bs seeks
If m = m′ /2 blocks of memory are available for each relation, cost
is ⌈br /m⌉ + ⌈bs /m⌉ seeks and br + bs transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 24 / 33

 Example
r : 40000 tuples at 200 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 13 for each

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 13 for each
Number of seeks for r is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 13 for each
Number of seeks for r is ⌈250/13⌉ = 20
Number of seeks for s is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 13 for each
Number of seeks for r is ⌈250/13⌉ = 20
Number of seeks for s is ⌈200/13⌉ = 16

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 13 for each
Number of seeks for r is ⌈250/13⌉ = 20
Number of seeks for s is ⌈200/13⌉ = 16
Total is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Example
r : 40000 tuples at 200 per block: 200 blocks
s: 25000 tuples at 100 per block: 250 blocks
Available memory is m = 13 for each
Number of seeks for r is ⌈250/13⌉ = 20
Number of seeks for s is ⌈200/13⌉ = 16
Total is 36 seeks and 450 transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 25 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}
Partitioning (or building) phase partitions the relations and writes
them to disk

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}
Partitioning (or building) phase partitions the relations and writes
them to disk
Matching (or probing) phase
Partition Pi (s) is read into memory: ts ∈ Pi (s) ⇐⇒ h(ts ) = i
A finer-grained in-memory hash may be constructed on Pi (s)

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}
Partitioning (or building) phase partitions the relations and writes
them to disk
Matching (or probing) phase
Partition Pi (s) is read into memory: ts ∈ Pi (s) ⇐⇒ h(ts ) = i
A finer-grained in-memory hash may be constructed on Pi (s)
Partition Pi (r ) is read block by block: tr ∈ Pi (r ) ⇐⇒ h(tr ) = i
For each tuple in Pi (r ), in-memory hash of Pi (s) is searched

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}
Partitioning (or building) phase partitions the relations and writes
them to disk
Matching (or probing) phase
Partition Pi (s) is read into memory: ts ∈ Pi (s) ⇐⇒ h(ts ) = i
A finer-grained in-memory hash may be constructed on Pi (s)
Partition Pi (r ) is read block by block: tr ∈ Pi (r ) ⇐⇒ h(tr ) = i
For each tuple in Pi (r ), in-memory hash of Pi (s) is searched
After partition i is done, new partitions are loaded

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}
Partitioning (or building) phase partitions the relations and writes
them to disk
Matching (or probing) phase
Partition Pi (s) is read into memory: ts ∈ Pi (s) ⇐⇒ h(ts ) = i
A finer-grained in-memory hash may be constructed on Pi (s)
Partition Pi (r ) is read block by block: tr ∈ Pi (r ) ⇐⇒ h(tr ) = i
For each tuple in Pi (r ), in-memory hash of Pi (s) is searched
After partition i is done, new partitions are loaded
s is called build input
r is called probe input

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33

 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}
Partitioning (or building) phase partitions the relations and writes
them to disk
Matching (or probing) phase
Partition Pi (s) is read into memory: ts ∈ Pi (s) ⇐⇒ h(ts ) = i
A finer-grained in-memory hash may be constructed on Pi (s)
Partition Pi (r ) is read block by block: tr ∈ Pi (r ) ⇐⇒ h(tr ) = i
For each tuple in Pi (r ), in-memory hash of Pi (s) is searched
After partition i is done, new partitions are loaded
s is called build input
r is called probe input
Each partition of build relation must be stored in memory
Smaller relation should be
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33
 Hash Join
Applicable only when the join condition is equality
If record tr and ts match, they must hash to same value, and thus,
only partitions with the same hash value need to be compared
PARTITION HASH JOIN
Hash function h to partition records of both relations into n
partitions: h : t ∈ (r ∪ s) → {0, . . . , n − 1}
Partitioning (or building) phase partitions the relations and writes
them to disk
Matching (or probing) phase
Partition Pi (s) is read into memory: ts ∈ Pi (s) ⇐⇒ h(ts ) = i
A finer-grained in-memory hash may be constructed on Pi (s)
Partition Pi (r ) is read block by block: tr ∈ Pi (r ) ⇐⇒ h(tr ) = i
For each tuple in Pi (r ), in-memory hash of Pi (s) is searched
After partition i is done, new partitions are loaded
s is called build input
r is called probe input
Each partition of build relation must be stored in memory
Smaller relation should be build
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 26 / 33
 Single Pass
Each of the n partitions of build input s should fit into memory
If build relation has bs blocks, each partition has roughly bs /n
blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 27 / 33

 Single Pass
Each of the n partitions of build input s should fit into memory
If build relation has bs blocks, each partition has roughly bs /n
blocks
Assume an available memory of m blocks for build

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 27 / 33

 Single Pass
Each of the n partitions of build input s should fit into memory
If build relation has bs blocks, each partition has roughly bs /n
blocks
Assume an available memory of m blocks for build
If each partition fits, then m > bs /n or n > bs /m

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 27 / 33

 Single Pass
Each of the n partitions of build input s should fit into memory
If build relation has bs blocks, each partition has roughly bs /n
blocks
Assume an available memory of m blocks for build
If each partition fits, then m > bs /n or n > bs /m
During partitioning, at least 1 block of each partition should fit in
memory
Thus, m > n

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 27 / 33

 Single Pass
Each of the n partitions of build input s should fit into memory
If build relation has bs blocks, each partition has roughly bs /n
blocks
Assume an available memory of m blocks for build
If each partition fits, then m > bs /n or n > bs /m
During partitioning, at least 1 block of each partition should fit in
memory
Thus, m > n
Combining,

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 27 / 33

 Single Pass
Each of the n partitions of build input s should fit into memory
If build relation has bs blocks, each partition has roughly bs /n
blocks
Assume an available memory of m blocks for build
If each partition fits, then m > bs /n or n > bs /m
During partitioning, at least 1 block of each partition should fit in
memory
Thus, m > n
Combining, m > n > bs /m or, m >
p
bs
If not so, then partitioning cannot be done in one pass

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 27 / 33

 Recursive Partitioning
If m <
p
bs , then partitioning cannot be done in one pass

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 28 / 33

 Recursive Partitioning
If m <
p
bs , then partitioning cannot be done in one pass
Recursive partitioning is employed

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 28 / 33

 Recursive Partitioning
If m <
p
bs , then partitioning cannot be done in one pass
Recursive partitioning is employed
Initially, number of partitions ns is chosen to be at most m
However, each partition now does not fit into memory
Thus, each partition is read and re-partitioned till each smaller
partition fits into memory

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 28 / 33

 Recursive Partitioning
If m <
p
bs , then partitioning cannot be done in one pass
Recursive partitioning is employed
Initially, number of partitions ns is chosen to be at most m
However, each partition now does not fit into memory
Thus, each partition is read and re-partitioned till each smaller
partition fits into memory
Number of passes is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 28 / 33

 Recursive Partitioning
If m <
p
bs , then partitioning cannot be done in one pass
Recursive partitioning is employed
Initially, number of partitions ns is chosen to be at most m
However, each partition now does not fit into memory
Thus, each partition is read and re-partitioned till each smaller
partition fits into memory
Number of passes is p = ⌊logm bs ⌋

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 28 / 33

 Recursive Partitioning
If m <
p
bs , then partitioning cannot be done in one pass
Recursive partitioning is employed
Initially, number of partitions ns is chosen to be at most m
However, each partition now does not fit into memory
Thus, each partition is read and re-partitioned till each smaller
partition fits into memory
Number of passes is p = ⌊logm bs ⌋
H YBRID HASH JOIN when more memory is available

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 28 / 33

 Recursive Partitioning
If m <
p
bs , then partitioning cannot be done in one pass
Recursive partitioning is employed
Initially, number of partitions ns is chosen to be at most m
However, each partition now does not fit into memory
Thus, each partition is read and re-partitioned till each smaller
partition fits into memory
Number of passes is p = ⌊logm bs ⌋
H YBRID HASH JOIN when more memory is available
Entire build relation s can be in memory
Retain the first partition of build relation in memory

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 28 / 33

 Example
Suppose, build input has bs = 120 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 29 / 33

 Example
Suppose, build input has bs = 120 blocks
Available memory is m = 12 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 29 / 33

 Example
Suppose, build input has bs = 120 blocks
Available memory is m = 12 blocks
Partitioning produces 120/12 = 10 blocks that fit
Thus, only 1 pass is required

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 29 / 33

 Example
Suppose, build input has bs = 120 blocks
Available memory is m = 12 blocks
Partitioning produces 120/12 = 10 blocks that fit
Thus, only 1 pass is required
Available memory is m = 10 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 29 / 33

 Example
Suppose, build input has bs = 120 blocks
Available memory is m = 12 blocks
Partitioning produces 120/12 = 10 blocks that fit
Thus, only 1 pass is required
Available memory is m = 10 blocks
Partitioning produces 120/10 = 12 blocks that do not fit
Thus, 12 blocks are partitioned again to 12/10 = 2 blocks each
This now fits
Thus, 2 passes are required

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 29 / 33

 Example
Suppose, build input has bs = 120 blocks
Available memory is m = 12 blocks
Partitioning produces 120/12 = 10 blocks that fit
Thus, only 1 pass is required
Available memory is m = 10 blocks
Partitioning produces 120/10 = 12 blocks that do not fit
Thus, 12 blocks are partitioned again to 12/10 = 2 blocks each
This now fits
Thus, 2 passes are required
Available memory is m = 4 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 29 / 33

 Example
Suppose, build input has bs = 120 blocks
Available memory is m = 12 blocks
Partitioning produces 120/12 = 10 blocks that fit
Thus, only 1 pass is required
Available memory is m = 10 blocks
Partitioning produces 120/10 = 12 blocks that do not fit
Thus, 12 blocks are partitioned again to 12/10 = 2 blocks each
This now fits
Thus, 2 passes are required
Available memory is m = 4 blocks
Partitioning produces 120/4 = 30 and then 30/4 = 8 and then
8/4 = 2 blocks
Thus, 3 passes are required

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 29 / 33

 Cost of Hash Join
Initial reading of a relation i requires bi transfers

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 30 / 33

 Cost of Hash Join
Initial reading of a relation i requires bi transfers
Total number of blocks after partitioning is at most

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 30 / 33

 Cost of Hash Join
Initial reading of a relation i requires bi transfers
Total number of blocks after partitioning is at most bi + n as each
of n partitions may be partially full
Writing them back requires

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 30 / 33

 Cost of Hash Join
Initial reading of a relation i requires bi transfers
Total number of blocks after partitioning is at most bi + n as each
of n partitions may be partially full
Writing them back requires (bi + n) transfers
Reading them again during matching requires

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 30 / 33

 Cost of Hash Join
Initial reading of a relation i requires bi transfers
Total number of blocks after partitioning is at most bi + n as each
of n partitions may be partially full
Writing them back requires (bi + n) transfers
Reading them again during matching requires (bi + n) transfers
Therefore, total number of transfers is 3(br + bs ) + 4n

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 30 / 33

 Cost of Hash Join
Initial reading of a relation i requires bi transfers
Total number of blocks after partitioning is at most bi + n as each
of n partitions may be partially full
Writing them back requires (bi + n) transfers
Reading them again during matching requires (bi + n) transfers
Therefore, total number of transfers is 3(br + bs ) + 4n
Assume memory buffer of m blocks
Partitioning requires

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 30 / 33

 Cost of Hash Join
Initial reading of a relation i requires bi transfers
Total number of blocks after partitioning is at most bi + n as each
of n partitions may be partially full
Writing them back requires (bi + n) transfers
Reading them again during matching requires (bi + n) transfers
Therefore, total number of transfers is 3(br + bs ) + 4n
Assume memory buffer of m blocks
Partitioning requires ki = ⌈bi /m⌉ seeks for reading and
ki′ = ⌈(bi + n)/m⌉ seeks for writing
Reading n partitions during matching requires n seeks per relation
Therefore, total number of seeks is kr + ks + kr′ + ks′ + 2n

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 30 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is p = ⌊logm bs ⌋

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is p = ⌊logm bs ⌋
During partitioning, total number of block transfers is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is p = ⌊logm bs ⌋
During partitioning, total number of block transfers is
2p(br + n + bs + n)

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is p = ⌊logm bs ⌋
During partitioning, total number of block transfers is
2p(br + n + bs + n)
Number of seeks during partitioning is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is p = ⌊logm bs ⌋
During partitioning, total number of block transfers is
2p(br + n + bs + n)
Number of seeks during partitioning is 2p(kr′ + ks′ )

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is p = ⌊logm bs ⌋
During partitioning, total number of block transfers is
2p(br + n + bs + n)
Number of seeks during partitioning is 2p(kr′ + ks′ )
Matching requires

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Cost of Recursive Partitioning
Number of passes in recursive partitioning is p = ⌊logm bs ⌋
During partitioning, total number of block transfers is
2p(br + n + bs + n)
Number of seeks during partitioning is 2p(kr′ + ks′ )
Matching requires (br + n + bs + n) transfers and n + n seeks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 31 / 33

 Example
r : 25000 tuples at 100 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block:

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is 250 + (250 + 15) = 515
Number of seeks for r is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is 250 + (250 + 15) = 515
Number of seeks for r is ⌈250/10⌉ + ⌈265/10⌉ = 52

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is 250 + (250 + 15) = 515
Number of seeks for r is ⌈250/10⌉ + ⌈265/10⌉ = 52
Matching phase requires reading all blocks of s and r :

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is 250 + (250 + 15) = 515
Number of seeks for r is ⌈250/10⌉ + ⌈265/10⌉ = 52
Matching phase requires reading all blocks of s and r :
215 + 265 = 480
Number of seeks in matching phase is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is 250 + (250 + 15) = 515
Number of seeks for r is ⌈250/10⌉ + ⌈265/10⌉ = 52
Matching phase requires reading all blocks of s and r :
215 + 265 = 480
Number of seeks in matching phase is 15 + 15 = 30

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is 250 + (250 + 15) = 515
Number of seeks for r is ⌈250/10⌉ + ⌈265/10⌉ = 52
Matching phase requires reading all blocks of s and r :
215 + 265 = 480
Number of seeks in matching phase is 15 + 15 = 30
Total is

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33

 Example
r : 25000 tuples at 100 per block: 250 blocks
s: 40000 tuples at 200 per block: 200 blocks
Available memory is 15 for partitions and m = 10 for buffering
Number of partitions is n = 15
Size of each partition of r is ⌈250/15⌉ = 17
Size of each partition of s is ⌈200/15⌉ = 14
Build input should be s
Partitioning s requires 200 + (200 + 15) = 415 transfers
Number of seeks for s is ⌈200/10⌉ + ⌈215/10⌉ = 42
Partitioning r requires 1 pass since it is probe input
Number of transfers for r is 250 + (250 + 15) = 515
Number of seeks for r is ⌈250/10⌉ + ⌈265/10⌉ = 52
Matching phase requires reading all blocks of s and r :
215 + 265 = 480
Number of seeks in matching phase is 15 + 15 = 30
Total is 15 + 15 + 42 + 52 = 124 seeks and
415 + 515 + 480 = 1410 transfers
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 32 / 33
 Other Operations
Complex join conditions

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the probe relation
If r is the build relation, keep track of which records in hash index
have been used; output all non-used records
If r ⊐[⊏ s, use both techniques

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the probe relation
If r is the build relation, keep track of which records in hash index
have been used; output all non-used records
If r ⊐[⊏ s, use both techniques
Set operations

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the probe relation
If r is the build relation, keep track of which records in hash index
have been used; output all non-used records
If r ⊐[⊏ s, use both techniques
Set operations
If relations are sorted, scan in order
Build hash index on one relation; test records from other relation

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the probe relation
If r is the build relation, keep track of which records in hash index
have been used; output all non-used records
If r ⊐[⊏ s, use both techniques
Set operations
If relations are sorted, scan in order
Build hash index on one relation; test records from other relation
Grouping and aggregation

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the probe relation
If r is the build relation, keep track of which records in hash index
have been used; output all non-used records
If r ⊐[⊏ s, use both techniques
Set operations
If relations are sorted, scan in order
Build hash index on one relation; test records from other relation
Grouping and aggregation
Use hashing to organize into groups; then apply aggregation

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the probe relation
If r is the build relation, keep track of which records in hash index
have been used; output all non-used records
If r ⊐[⊏ s, use both techniques
Set operations
If relations are sorted, scan in order
Build hash index on one relation; test records from other relation
Grouping and aggregation
Use hashing to organize into groups; then apply aggregation
Duplicate detection and elimination

Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33

 Other Operations
Complex join conditions
Block nested-loop for conjunctive and/or disjunctive selection
If only equality, union/intersection of results of index or merge or
hash join may be used
Outer join
Block nested-loop algorithm requires almost no modification
For merge join, select all (non-joining) records while scanning
For hash join, if r ⊐Y s, r should be the probe relation
If r is the build relation, keep track of which records in hash index
have been used; output all non-used records
If r ⊐[⊏ s, use both techniques
Set operations
If relations are sorted, scan in order
Build hash index on one relation; test records from other relation
Grouping and aggregation
Use hashing to organize into groups; then apply aggregation
Duplicate detection and elimination
Use hashing or sorting
Arnab Bhattacharya (arnabb@[Link]) CS315: Query Processing 2024-25 33 / 33