Database Management System (DBMS)
Web Embedded Interactive
Applications Forms SQL SQL
SQL Commands
DBMS
Query
Evaluation Engine
Files and Access Methods
Concurrency Recovery
Control Buffer Manager Manager
Disk Space Manager
Database Data Indexes Catalog
1
Steps in Processing a Query
SQL statement
Scan, Parse, Validate
Intermediate form of query
Query
Query Optimizer
Optimizer
Execution plan
Query Code Generator
Code to execute query
Runtime DB Processor
Results of running query
2
Steps in Processing a Query
SQL statement
Scan, Parse, Validate
Intermediate form of query
Query Optimizer
Execution plan
Query
QueryCode Generator
Code Generator
Code to execute query
Runtime DB Processor
Results of running query
3
How to implement Selection ()?
Depends on:
Type of Query:
1. Point query,
2. Range query,
3. Conjunction, or
4. Disjunction
Type of available Access Path:
1. Index,
2. Sorted File
3. None!
4
Selection () Operator - Examples
Point Query:
SSN='123456789' (Employee)
Range Query
DNUMBER>5 (Department)
Conjunction Query
DNO=5 AND SALARY>30000 AND GENDER=F (Employee)
Disjunction Query
DNO=5 OR SALARY>30000 OR GENDER=F (Employee)
How does the DBMS answer each of those queries?
5
Algorithms for SELECT
Let’s start with the form: [Link] <op> value (R)
This form can represent:
Point Query:
<op> is: “=“ (i.e., equality)
Eg.: σ Age=21 (Students)
Range Query:
<op> is: “>”, “≥”, “<“, “≤”
Eg.: σ Age>21(Students)
Algorithms: in the next slides..
6
SELECT: No Index, Unsorted Data
[Link] op value (R)
(1) Linear search (brute force):
1. Retrieve every record in the file, and
2. Test whether its attribute values satisfy the
selection condition ([Link] op value)
Since records are grouped into blocks:
each block is read from disk and search (i.e.,
test) is done in main memory
7
SELECT: No Index, Sorted Data
[Link] op value (R)
(2) Binary search:
If the data file is sorted on the condition attribute ([Link])
Works for Point Query ( Age=21)
Works for Range Query ( Age>21)
Find the first record that satisfies the condition, then scan
until the condition is no longer satisfied
More efficient than linear search
8
SELECT: Index (B+ tree Index)
[Link] op value (R)
(3) Using an Index (B+ tree)
If an index exists on the condition attribute ([Link])
Flexible solution; can create a B+ tree index on:
key/non-key attribute
Sorted or unsorted data file
Works with both Point or Range Query
Find the first record then follow the next pointer
9
Putting it together
For a single condition: [Link] op value (R):
1. Use the index on the condition attribute if
available, else
2. Use Binary search if the file is sorted on the
condition attribute, else
3. Use the “brute force” linear search approach
Rule of thumb: it is probably cheaper to simply scan the entire
table instead of using an unclustered index if over 5% of the
tuples are to be retrieved.
10
Operator Evaluation
Several alternative algorithms are available
for implementing each relational operator
No algorithm is universally superior
Several factors influence which algorithm performs best:
Size of the tables
Existing index and sort orders
Size of available memory
….
11
Putting it together
[Link]
Linear Search?
Linear Search?
Binary Search?
Binary Search? [Link] = [Link]
Index?
Index?
[Link] > 4 [Link] = CSE454
S E
12
How to choose an implementation?
13
Algorithms for SELECT with Conjunctions
State=QLD AND Gender=F (Employee)
Using a composite index:
If two or more attributes are involved in equality
conditions in the conjunction, and
a composite index exists on the combined field, we
can use the composite index directly
Example: on lastName, firstName (as in phone directory)
Works for point query but what about a range query?
14
Algorithms for SELECT with Conjunctions
Age<25 AND Salary>60000 AND Gender=F (Employee)
Conjunctive selection:
If an attribute in the conjunctive condition has an
index, then:
1. use that index to retrieve the records
Eg: use the index on “age” to fetch all age<25 records
2. for each retrieved record, check if it satisfies the
remaining conditions in the conjunction
Eg: for each retrieved record with age<25, check if:
salary>60,000 and gender=F
15
Which index?
For conjunctive selection conditions:
If there are multiple indexes, query optimization
should:
choose the index/path that retrieves the fewest
records/pages most selective access path
Age<25 AND Salary>60,000 (Employee)
Which index to choose: Age or Salary?
The optimizer should choose the access path
(e.g., index) that retrieves the fewest records:
1. Less blocks to read from disk
2. Less checks to do in memory
16
Selectivity
In a movies database:
σ type=“Drama” AND actress=“Nicole Kidman” (Movies)
Which index to choose: type or actress?
From IMDb:
Total: 2,000,000 titles
Drama: 500,000 titles
Nicole Kidman: 58 titles
The optimizer should:
1. Retrieve all “Nicole Kidman” movies first, and then
2. Check which of the 58 titles is “Drama”
17
Selectivity
The optimizer uses selectivity to choose!
Selectivity (S) (also called reduction factor):
The ratio of: the number of records that satisfy a
condition to the total number of records
Example: for σ type=“Drama” ,S = 500K/2M = 0.25
S between 0.0 and 1.0
S = 0: no records satisfy the condition
S = 1: all records satisfy the condition
Selectivity estimates are stored in DBMS Catalog
18
Selectivity
Equality condition on a key attribute
Eg.: σ title=“Australia”
Number of records that satisfy the condition:
only one!
S = 1/|R|, where |R| is the number of records in R
19
Selectivity
Equality on an attribute with ”x” distinct values
Eg.: σ gender=“female”
and distinct values: female and male (then x=2)
Number of records that satisfy the condition:
|R|/x (assuming uniform distribution)
S = (|R|/x)/|R| = 1/x (if x=2, then S=½)
Eg.: σ type=“Drama”
and distinct values: Drama, Comedy, Action
S = (|R|/x)/|R| = 1/3
20
Selectivity
The actual distribution of selectivity is kept in the
catalog in the form of a histogram
To get more accurate estimate of the number of
records that satisfy a particular condition
Drama: 500,000
Comedy: 460,000
Documentary: 200,000
Musicals: 20,000
The estimated number of records satisfying condition
with selectivity S equals: |R| * S
Eg.: for σ type=“documentary” , 2M * 0.1 = 200K records
Apply the condition with smallest estimate first
21
Projection
The projection operation requires to drop
certain fields of the input EASY and NOT expensive
Duplicates in the result of a projection operation
need to be removed This part is EXPENSIVE
If duplicates need not be eliminated (DISTINCT
keyword is not included in the SQL statement),
simple iteration on either the table (or an index
whose key contains all necessary fields)
If we have to eliminate duplicates, partitioning has
to be used
22
Projection Cont.
Sorting Approach: SELECT DISTINCT [Link], [Link]
FROM Reserves R
Sort on <sid, bid>
Scan Reserves to obtain <sid, bid> pairs
Sort these pairs
Scan the sorted pairs and discard duplicates
Sorting large disk-resident datasets is a very important
operation in database systems
Sorting a table typically requires 2-3 “passes”, each of
which reads and writes the entire table
23