Query Execution

Chapter 6

Outline

Introduction
An algebra for queries
Introduction to physical query plan operators
One pass algorithms for Database Operations
Nested-loop joins
Two-pass algorithms Based on Sorting
Two-pass algorithms based on hashing
Index-based algorithms
Buffer Management
Overview of parallel algorithms

Introduction
Previous chapters
Finding tuples given a search key

How to answer queries ?

This chapter and next chapter

Query processor
Converts queries into a sequence of operations on
the database and executes the same.
Nave conversion may require more time.

Query Processor

Query

Query compilation
Chapter 7

Query execution

Meta data

Query
Compilation

Chapter 6
Query
Execution
data

Overview of Query Compilation

Three major steps
Parsing
Query and its structure is constructed

Query rewrite
Parse tree is converted to initial query plan
Algebraic representation of a query

Physical plan generation

Selecting algorithms for each operations
Selecting the order of operations

Query rewrite and physical plan generation are called

query optimizer.
Choice depends on meta data

Query Execution
Execution of relational algebra operations

Union
Intersection
Difference
Selection
Projection
Joins
sorting

An algebra for queries

SQL operators for Union, intersect and difference

UNION, INTERSECT and EXCEPT

Selection:
Where clause

Projection
SECLECT clause

Product
Relations are FROM clause, whose products forms he relation with condition of
WHERE clause and projection of SELECT clause.

JOIN
JOIN, NATURAL JOIN, OUTER JOIN

Duplicate elimination
DISTINCT

Grouping
GROUP BY clause

Sorting
ORDER BY clause

UNION, INTERSECTION and

DIFFERENCE
Differences between relations and sets
(a) Relations are bags
(b) Relations have schemas, a set of attributes that name their columns

Due to (b) schemas of two argument relations must be the

same.
R U S: t appears as many times it is in R plus it is in S.
R S: t appears in the result the minimum number of times it
is in R and S
For R-S: number of times in R minus number of times in S.
By default, duplicates are eliminated
We can use the key word ALL (for example UNION ALL) to
take the bag versions
The bag versions are followed by duplicate elimination.

SELECTION
(R)
C

takes a relation R and a condition C. The condition C may involve

Arithmetic
Comparison
Boolean

PROJECTION
L(R) projection R in list L.
L can have the following elements
An expression xy, where x and y are names
for attributes.
An expression Ez, where E is an expression
involving attributes of R, constants, arithmetic
operators and string operators and z is a new
names of the attribute.

The Product of Relations

RXS
Schema consists of attributes of R and attributes of
S.
If a tuple r appears m times in R and a tuple s
appears s times in S, then the tuple rs appears nm
times.

Joins
Natural join
L(C(R X S))
C is the condition that equates all the pairs of R and S that
have the same name
L is a list of all the attributes of R and S, except one copy of
each pair of attributes is omitted.

Theta join
C(R X S), where condition C is of the form like x any
condition y.

Equijoin
C(R X S), where condition C is of equal form like x = y.

Outer join
Adding dangling tuples from R and S

Left outer join

Only dangling tuples of the left argument are
added

Right outer join

Only dangling tuples of right argument S are
added.

Outer Join Example

Relation loan
loan-number branch-name amount
Downtown
Redwood
Perryridge

L-170
L-230
L-260

3000
4000
1700

Relation borrower
customer-name
Jones
Smith
Hayes

loan-number
L-170
L-230
L-155

branch-name

L-170
L-230
L-260
L-155

Downtown
Redwood
Perryridge
null

amount customer-name
3000
4000
1700
null

loan-number

branch-name

L-170
L-230

Downtown
Redwood

amount customer-name
3000
4000

Jones
Smith

Left Outer Join

loan
loan-number

Borrower
branch-name
Downtown
Redwood
Perryridge

amount
3000
4000
1700

customer-name
Jones
Smith
null

Right Outer Join

borrower

loan-number

Borrower

L-170
L-230
L-260

Full Outer Join

loan

loan

Jones
Smith
null
Hayes

loan
loan-number

L-170
L-230
L-155

borrower
branch-name
Downtown
Redwood
null

amount customer-name
3000
4000
null

Jones
Smith
Hayes

Duplicate Elimination
(R ) returns one copy of each tuple.

Grouping and Aggregation

Aggregate operators
AVG, SUM, COUNT, MIN, and MAX

Group By
The relation is grouped according to the value of
the attribute

Having
Provides a condition

Grouping and having should be implemented

together

Sorting operator
We use the operator to sort a relation
SQL ORDER BY
L(R), L is a list of attributes (a1, a2,, an)

Ties are broken as per a2

They agree till an, the tuples are sorted arbitrarily.
Default is ascending order, can be changed using DESC
The result is list of tuples. So it is he last operator.
If this operator is applied, the notion of set is disturbed.

Expression Trees
Schema
MovieStar(name, address, gender, birthdate)
StarsIn(title, year, starName)

Query
Select title, birthdate
From MovieStar, StarsIn
Where Year = 1996 gender = F
starName=name

Expression Tree 1

19

Another logical query plan

20

Introduction to Physical
Query Plan Operators
Scanning tables
Read the entire contents of R.
Two basic operators
Get the blocks one by one
Table scan

Use index to get all the tuples of R

Index scan

Sorting While Scanning Tables

The operator sort-scan takes a relation R and a
specification of attributes on which the sort is to be
made, and produces R in that sorted order.
Ways to implement sort-scan
If we are to produce a relation R sorted by attribute a,
and there is a Btree index on a, simple scan produces
sorted file.
If R fits in main memory, we can retrieve tuples using
index scan or table scan and use main memory sorting
algorithms.
If R is too large to fit in main memory, follow multi-way
merging approach.

Model of Computation of Physical

Operators
Query consists of several operations of relational
algebra and corresponding physical query plan is
composed of several physical operators.
Operations like scanning are invisible in relational algebra.

Physical plan operators should be chosen wisely.

Number of disk I/Os is the measure.
Assumption:
Arguments can be fund on the disk and the result of the
operation is in the main memory.

Parameters to measure the cost

M denotes the number of main memory
buffers.
Input and intermediate results
M is much smaller than the main memory

B(R)- number of blocks that hold R

T(R) - number of tuples in R
V(R,a) number of distinct values of the
column for a in R.

I/O cost for Scan Operators

If R is clustered the number of disk I/Os = B.
If R fits in main memory, B I/Os.
If R is clustered but requires a tw-phase multi-way merge sort
we require 3B disk I/Os
If R is not clustered, the number of disk I/Os is much higher.
If R is distributed among the tuples of other relations, the I/O
cost is T.
IF R is not clustered and requires a two-way merge sort it
requires: T+2B.
Index scan
Fewer than B(R) blocks

Iterators for Implementation for

Physical Operators
Iterator
Getting one tuple at a time.

Three functions
Open:
Starts the process of getting tuples, but does not get a tuple. It initializes
any data structures needed to perform the operation and calls Open for any
orguments of the operation.

GetNext
The function returns the next tuple in the result and adjusts data structures
as necessary to allow subsequent tuples to be obtained. It returns null, if
there are no more tuples produced.

Close
The function ends iteration after all tuples or all the tuples the consumer
wanted, have been obtained.

(Refer Figure 6.8 for table scan operator)

Iterator for Table Scan

Open(R){
b:= the first block of R;
t:= the first tuple of block b;
found := true;
}

GetNext {
IF(t is past the last tuple on block b) { increment b to the next block;
IF(there is no next block) {Found:=FALSE; RETURN;}
ELSE /* b is a new block */
t:= first tuple on bock b;
Oldt:=t;
Increment t to the next tuple of b;
RETURN oldt;
}

CLOSE(R) {}

Iterator for sort-scan

The open function read all the tuples in mainmemory sized chunks, sort them and stores
them on the disk
Initialize the data structure for the second
merge phase, load the first block of each
sublist into main-memory structure.

Iterators
Iterators can be combined by calling other
iterators.
Open(R,S){ R.open(); CurRel:=R;}
GetNext(R,S) { IF CurRel=R {t=R.GetNext()
IF (Fund) RETURN t ELSE S.open();
CurRel=S;}} Return S.GetNext();
Close(R,S){ R.Close(); S.Close();}

Algorithms For Database Operations

How to execute each individual steps
Join and selection
Selecting a choice of an algorithm

Three categories
Sorting-based methods
Hash-based methods
Index-based methods

One pass algorithms

Requires reading only once from the disk
At least one of the arguments fits in the memory

Two pass algorithms

Too large to fit in the memory but not the largest.
Requires two readings
First read and process and write back.
Read again for further processing

Multi pass algorithms

No limit on the size of data
Recursive generalizations of two pass algorithms

Three types of operators

Tuple at a time, unary operations
Selection and projection

Full relation
Seeing all the tuples in memory once

Full-relation, binary operations

Union, intersection, joins, products

One pass algorithms for tuple at a time

Operations
(R), (R),
Read the blocks of R one at a time into input buffer
and move the tuples to output buffer.
Complexity is B, if R is clustered and T if R is not
clustered.
If the condition variable has an Index, it affects the
performance.

One Pass algorithms for Unary and

Full Relation Operations
Duplicate elimination and grouping
For each tupe
If we have seen it first time, write it to output
buffer
If the tuple is seen before, do not output this tuple.
For this we have to keep one copy of every tuple we
have seen.
One memory buffer holds the block of Rs tuples, the
remaining M-1 blocks can be used to hold a single copy
of every tuple seen so far.

One pass algorithms

Each new tuple takes processor time proportional to
n.
Complete operation takes n2 processor time.
If n is large, it becomes significant.

The main memory data structure to allow

Add a new tuple
Tell a whether a given tuple is already there.

Use hash tables or binary search tree

Assumption: no extra space is required
If B((R)) <=M, it is OK, otherwise thrashing might
occur.

Grouping
The grouping operation L gives zero or more grouping
attributes and one or more aggregated attributes.
For each of grouping attribute create one entry for each value
and scan each block at a time
For a MIN(a) or MAX(a) aggregate, record min and max value,
respectively and change min or maximum whenever each time a tuple
of a group seen
For COUNT, add one to the corresponding group
For SUM(a), add the value of a to the accumulated sum.
AVG(a): maintain two accumulations: count and sum of values.

Until all the tuples are seen, we can not output the result.
Entire grouping is done in OPEN function.
Hash tables and balanced trees are used to find the entry in
each group.
The number o I/Os is B.

One pass Algorithms for Binary Operations

Set Union
Read S into M-1 buffers of main memory and build a search structure
where the search key is the entire tuple. All the tuples are copied to the
output
Read R into mth buffer, one at a time. If t is in S, skip t, otherwise
write t to output.

Set Intersection
Read S into M-1 buffers and build a search structure with full tuples as
search key. Read each block of R, for each t of R, see if t is also in S.
If so, copt t to the output. If not, ignore it.

Set difference
Assume R is larger relation. Read S to M-1 buffers and build a search
structure with full tuple as a search key.
R-S
Read each block of R. IF t is in S, ignore t; if it is not in S, copy t to the
output

S-R
Read each block of R. IF t is in S, ignore t; if it is in S, delete t from the
copy of S. If t is not in S we do nothing. After completing R, output the
remaining S tuples.

Bag intersection and Bag difference

Bag intersection
We read S into M-1 buffers, we associate each
distinct tuple a count, which measures the number
of times the tuple appears in S.
Read each block of R whether t occurs in S. If not,
ignore t. If it appears, if the count is positive,
output t and decrement the count by one. If t
appears in S and count is zero, we do not out put t.

Bag difference
Similar.. (Check the book)

Product
Product
Read S into M-1 buffers. Read each
block of R. For each tuple of R,
concatenate t with each tuple of S.
Output concatenated file.

Natural Join
Natural join
R(X,Y) being joined with S(Y,Z)
Read all the tuples of S into M-1 blocks.
Read each block of R. For each t of R, find
the tuples that agree with all the attributes of
Y. For each matching tuple of S, form a
tuple by joining it with t, and move the
resulting tuple to the output.
Takes B(R)+B(S) disk I/Os

Nested Loop Joins

Tuple-based Nested loop join
Complexity: T(R)T(S) disk I/Os.

Iterator for Tuple-based Nested Loop

Join
Iterators can be easily built.

A block-based Nested Loop Join

Organize the access to both relations by
blocks.
Using as much memory, store the tuples of S.

Nested Block Join

FOR each chunk of M-1 blocks of S DO BEGIN
read these blocks into main memory buffers;
Organize their tuples into a search tree structure whose search key
is the common attributes of R and S;
FOR each block b of R DO BEGIN
read b into memory;
FOR each tuple t of b DO BEGIN
find the tuples of S in main memory that
join with t;
output the join of t with each of these tuples;
END;
END;
END;

Example
B(R)=1000 and B(S)=500 and let M=101.
We use 100 blocks of memory for S
Outer loop iterates five times
Each iteration we have 100 disk I/Os
Second loop we must read entire R.
1000 I/Os

5500 I/Os

If we reverse the role of R and S

6000 I/Os

Analysis of Nested Loop Join

Iterations of outer nested loop B(S)/(M-1)
For each iteration we read M-1 blocks of S and
B(R) blocks of R.
The number of disk I/Os
(B(S)/(M-1)) (M-1+B(R))
B(S)+ B(S)B(R)/(M-1)
B(S)B(R )/M

Summary
Operators

Approximate M
Required

Disk I/O

,
,

1
B

B
B

U, , , , Join

Min(B(R),B(S))

B(R )+B(S)

Join

Any M 2

B(R)B(S)/M

Two-pass Algorithms Based on Sorting

Two pass algorithms are sufficient.
It can be generalized into higher passes
If we have large relation R

Read M blocks into main memory

Sort these M blocks
Write sorted list into M blocks of disk
Execute the desired operator on the sorted lists

Duplicate Elimination Using Sorting

Hold the first block from each of the sorted
sublist.
Consider first unconsidered tuple from each
block, make copy of t to the output. Remove
from the fronts of various input blocks all
copies of t.
If the block is exhausted, bring new block of
that sorted sub-list.

Complexity
Ignore the writing of output

B(R) to read each block of R when creating sorted sublists

B(R) to write each of sublists to disk
B(R) to read each block from sublist.
Total =3*B(R)

Memory requirement
B M2 is required for the two pass algorithm to be feasible
(for one pass B<= M)
(R ) requires B(R ) blocks of memory
(for one pass B=M)

Grouping and Aggregation

The algorithm for (R ) is similar to (R).
Read R, M blocks at a time. Sort each blocks grouping
attributes of R as the sorted key. Write each sorted sublist to
disk.
Use the one memory buffer for each sublist, load the first
block of each sublist into its buffer
Repeatedly find the least value in the available sub-buffers.
This value, v, becomes the next value
Prepare to compute all the aggregates on list L for this group
Examine each of the tuples with sort key v, and accumulate the needed
aggregates.
If a buffer becomes empty, replace it with the next block from the same
list.

Complexity is similar to
B M2 is required for the two pass algorithm to be feasible
(R ) requires B(R ) blocks of memory

Sort-based Union Algorithm

One-pass algorithm works, if at least one relation is in main
memory.
Two pass algorithm
Create sorted sublists of R of size M.
Create sorted sublists of S of size M.
Use one main-memory buffer for each sublist of R and S. Initialize
with first block of each R and S.
Repeatedly find the first remaining tuple t among all the buffers. Copy
t to the output and remove from all the copies of t.
If the buffer becomes empty read the next block in the sublist.

Total cost= 3(B(R )+B(S))

Each tuple is read twice in main memory: Once when sublists are being
created and the second time as a part of one f the sublists.
Each tuple is written once
The size of two relations should not exceed M 2.
That is, B(R)+ B(S) M2

Sort-based Algorithms for

Intersection and Difference
Same as union
Set intersection:
Output t, if t appears in both R and S.

Bag intersection
Output t the minimum number of times t appears in R and in S.

R-S (set)
Output t, if only it appears in R but not in S.

R-S (bag)
Output t the number of times it appears in R minus the number of times
it appears in S. If both occur at equal number of times, we do not
output any tuples.

Analysis
3(B(S)+B(S)) disk I/Os.
B(R)+B(S) M2 for the algorithm to work.

Simple Sort-based Joining Algorithm

Sort R, with mupli-way merge sort, with Y as the sort key.
Sort S similarly.
Merge the sorted R and S. Use only two buffers contains
current blocks of R and S respectively.
Find least value y that is currently in front of the blocks for R and S.
If y does not appear in front of other relation, remove tuples with sort
key y.
Otherwise, identify all the tuples from both relations having sort key y.
read blocks from R and S, until no more keys. Use M buffers for this
purpose.
Output all such tuples.
If either relation has no more unconsidered tuples in main memory,
reload the buffer for that relation.

Simple Sort join: modification for

the worst case

If Y-is the key for R or S no problem arises.

If the tuples from one of the relations, say R, that
have Y-value y fit in to M-1 buffers, do one pas join

load these blocks of R into buffers and read the blocks of S

that hold tuples with y, one at a time into remaining buffer.

If neither relation has sufficiently few tuples with Yvalue y that they all fit into M-1 buffers, do nestedloop join
Use M buffers to perform nested loop join on the tuples
with Y-value y from both relations.

Analysis of Simple Sort-based Join

Analysis
We shall not run out of buffers, if the tuples in
common y value can not fit in buffers.
5(B(R)+B(S)) disk I/Os.
B(R) M2 and B(S)M2 to work.

A More Efficient Sort-based Join

Second phase of join and sorting can be combined. It is called
sort-join, sort-merge-join, merge join.
Create sorted sublists on R and S using Y.
Bring the first block of each sublist into buffer (No more than
M sublists)
Repeatedly, find the least Y-value y among the first available
tuples of all the sublists. Identify all the tuples of both
relations that have Y-value y, using some of the available M
buffers. Output the join of all tuples from R with all tuples
from S that share this common Y-value. If the buffer of one
sublist exhausted, replenish it from disk.
Analysis
3(B(R)+B(S)) disk I/Os.
(B(R)+B(S)) M2 is sufficient.

Problem of many tuples with Yvalue

Problem may not arise
Y is the key of R

If B(R) + B(S) is much less than M*M, use

many unused buffers.
In the worst case follow nested loop join.

Summary of Sort-based algorithms

Operators

Approximate M
Required

Disk I/O

3B

U, ,
Join

(B(R)+B(S))
3(B(R )+B(S))
max(B(R),B(S)) 5(B(R )+B(S))

Join

(B(R)+B(S)

3(B(R )+B(S))

Two-Pass Algorithms Based on Hashing

Basic idea
If the data is too big to store in main-memory
buffers, hash all the tuples of the argument or
arguments using an appropriate hash key.
If M buffers are available, we can pick M as
number of buckets.
We can gain a factor of M similar to sort-based
algorithms, but different means.

Partitioning Relations Using Hashing

Let hash function be h

Associate one buffer with each bucket.
Partition R is using M buffers
Partition R into M-1 buckets.
Read R in to Mth buffer
Each tuple is hashed to M-1 buckets and
copied to appropriate buffer.
If the buffer is full, write it to disk and initialize
another block.

Bucket size is bigger than buffers.

A hash-based Algorithm for Duplicate Elimination

(R)
Hash R to M-1 buckets.
Two copies of the same tuple are hashed to the same
bucket.
Eliminate one bucket at a time.
One pass algorithm can be used.

It works if individual Ris fits into main memory.

Each Ri is equal to B(R)/(M-1) blocks in size.
If the number of blocks no longer than M, i.e., B(R)M(M1), two pass hash based algorithm works.
B(R) M2 (same as sort-based algorithm for duplicate
elimination)

Hash-based algorithm for grouping and

aggregation
L(R)
Chose the hash function on the grouping attributes
of list L.
Hash all the tuples of R into M-1 buckets
Use one pass algorithm
We can process provided that B(R) M2
Number of disk I/Os = 3B(R)

Hash-based algorithms for U,, and

Binary operation
Use the same hash function to hash tuples of both
arguments.
R Us S
Hash both R and S to R1, R2, ,RM-1 and S1, S2,,SM-1.
Take set union of Ri and Si, for all i and output the result.

Intersection or difference
Apply appropriate one pass algorithm
(B(R) + B(S)) I/Os.

Summary
Total 3(B(R)+B(S)) I/Os
The algorithms work iff Min(B(R), B(S)) M2

Hash Join Algorithm

Compute R(X,Y) join S(Y,Z)
Use the hash key for the join attributes.
If tuples join they will wind up in corresponding
Ri and Si for some i.
One pass join of all pairs of corresponding
buckets.

Summary
Total 3(B(R)+B(S)) I/Os
The algorithms work iff Min(B(R), B(S)) M2

Hybrid Hash Join:

Saving some disk I/Os
Use several blocks for each bucket and write them out in a
group , in consecutive blocks of disk.
Hybrid hash join
Use several tricks to avoid writing of some of the blocks.
Suppose S is a smaller relation
Keep all m buckets in main memory and keep one block for each
remaining bucket.
(m*((B(S)/k))+(k-m) M
B(S)/k is the expected size of bucket.

M buckets of S are not written into memory

One block for each (k-m) buckets of R whose corresponding
buckets of S were written to disk.
In the second pass, R and S can be joined as usual, Actually,
there is no need to join.

Saving some disk I/Os

Saving disk I/Os equal to two for every blocks
of S and corresponding R buckets. Note that
m/k buckets are in main memory
Savings= 2(m/k)(B(R)+B(S))
Intuition: k should be as small as possible to
maximize savings.
Buckets are equal to M, so k=B(S)/M and m=1
Savings= (2M/B(S))(B(R)+B(S))
Total cost (3-(2M/B(S)))(B(R )+B(S))

Summary of Hash-based Join

algorithms
Operators

Approximate M
Required

Disk I/O

3B

U, ,

B(S)

3(B(R )+B(S))

Join

B(S)

5(B(R )+B(S))

Join

B(S)

(3-2M/B(S))(B(R )
+B(S))

Assume B(S) B(R)

Sort-based and Hash-based algorithms

Size
Hash depends on smaller relation size
Sort depends on sum of two relation sizes.
Sort order
Sort algorithms produce sorted order
Hash algorithms not
Size of buckets
Hash depends on buckets of equal size. It is not possible to
use buckets that occupy M blocks
In sort-based algorithms, sorted sub-lists can be written in
consecutive blocks of disk. Rotational and seek latency can be
reduced
In hash-based algorithms also, we can write several blocks of
buckets at once.

Index-based Algorithms
Index is available on one or more attributes of
a relation

Clustering and non-clustering indexes

All the relations are clustered
If the tuples are packed roughly as few blocks as
can possibly hold those tuples.

Clustering idexes
Indexes on an attribute or attributes such that all
the tuples with a fixed value for the search key of
this index appear roughly as few blocks that hold
them
Only clustered relations have clustered index.

Index-based Selection

If there are no indexes on R, one has to read all the tuples of
R
Number of disk I/Os=B(R) or t(R )

If the search key is equal a=v, and a is an attribute for which

an index exists and v is a value.
We can use index and get the pointers.
If index is clustered the number of disk I/Os=B(R )/V(R,a).
Actual number might be higher
Disk I/Os are needed to support index lookup
The tuples can be spread over several blocks
The tuples can spread several blocks.

If the index is non-clustered, we must access T(R)/V(R,a)

tuples.
The number might be higher because, we might read some index
blocks. (sometimes lower also)

Notions of clustering
Clustered file organization
Tuples of two relations are placed together in the
same block based on certain value.

Clustered relation
One block contains the tuples of one relation.

Clustered index
Tuples having given search key value are stored
together.

Joining by Using an Index

Suppose S has an index on attributes Y
Examine each block of R, identify tuples that match y, use
index to find all tuples of S that have ty in their Y-components.
Disk I/Os
Reading R
If R is clustered, we have to read B(R) blocks.
If R is not clustered, upto T(R) blocks

Reading S
For each tuple t of R, we must read an average of T(S)/V(S,Y) tuples of S.
S has non clustered index on Y, the number of disk I/Os required is T(R)
T(S)/V(S,Y) disk I/Os
If the index is clustered we only need T(R )B(S)/V(S,Y) disk I/Os office.

Regardless of R is clustered or not, the cost of accessing tuples of S

dominates
So we take T(R) T(S)/V(S,Y) or T(R )(max(1,B(S)/V(S,Y))) for clusted or
non-clustered indexes, respectively.

Advantages of Index Join

R is very small compared with S and V(S,Y) is
large.
If we select before join, most of the S tuples
will not be examined.
Both sort/hash based methods examine every
tuple of S at least once.

Joins using Sorted Index

If we have a sorting idexes on Y for both R
and S we have to perform only the final step of
the simple sorted-based join.

Buffer Management
Value of M vary depending on system
conditions
Buffer manager allocates buffers to processes
such that delay is minimized.

Buffer Management Architecture

It controls main memory directly, or
Buffer manager allocates buffers in virtual
memory, allowing OS to decide which buffers
are actually in main memory at any time.
Should avoid thrashing.

Buffer Management Strategies

If buffers are full, it has to decide which block has to throw
out to create space for new block.
LRU
Throw out the block which has not been used for a longer period of
time.

FIFO
Throw out the bock which has stayed for longer time.

CLOCK algorithm
Approximation of LRU
Buffers are arranged in a circle.
When the block is read it is set to 1. When the contents are accessed it
is set to 1.
Buffer manager replaces a block with 0. If it finds 1, it sets to 0.

System control
Take advice from query processor about the algorithm and pinned
blocks.

Pinned blocks
The blocks can not be moved with out
modifying other blocks that point to it.
Buffer manager avoid expelling pinned
blocks.
If the block is pinned, it will remain in
memory
Root block of B-tree is pinned
Pin the blocks of smaller relation in the join

Relation between Physical Operator Selection

and Buffer Management
Query optimizer selects some operators
Each operator assumes availability of some
buffers
Buffer manager may not guarantee
So,
Can the algorithm of physical operator adapt
changes to M ?

Observations
If we use sort-based algorithm, it is possible to
adapt to changes to M.
If M shrinks, we can change the h=size of sublist.

If the algorithm is hash-based, we can reduce

the number of buckets if M shrinks as long as
buckets do not become so large they do not fit
in allotted main memory.

Algorithms with more than two passes

Generalization of two pass algorithm.
Sorting-based
Hash-based

Parallel Algorithms
Database operations can profit from parallel
processing

Models of parallelism
Shared memory
Each processor can access all the memory of all the
processors.
Single physical address space

Shared disk
Every processor has its own memory and not accessible by
other processors
Disks are accessible by every processor through network

Shared nothing
Each processor has its own memory and disk
Communication is through network

Shared Nothing
Tuple-at-a time operations in parallel
If there are P processors, divide Rs tuples
evenly among the P processors.
Send the selection and projection to the
processors.

Full Relation Operations

Use hash to distribute the tuples
Apply grouping operation in parallel.
For union, intersection and subtraction use the
same hash function to distribute R.

Performance
Number of disk I/Os do not change
Time = 1/p of time + cost of shipping
Shipment over network is cheaper than disk
utilization.