Please enable JavaScript.
Coggle requires JavaScript to display documents.
Relational Operators #1: Selection - Coggle Diagram
Relational Operators #1: Selection
Logical vs Physical Operators
Logical: what (union, selection, project,
join
, group)
Physical: how (
nested loop
join,
sort-merge
join,
hash
join)
Selection on single attribute
access path
: way to retrieve tuples from a table
File Scan: scan entire file
I/O = # pages (N)
independent of selection condition
Index Scan: use available index on predicate
I/O cost varies depending on index
Hash index: O(1) only with equality search
no range search
bad if many duplicates -> overflows
B+ Tree index: (height - Lb + # leafs) + X (clustered/unclustered)
unclustered: X = # selected tuples in worst case
clustered: X = # selected tuples / # tupes per page
optimization: sort rids by page # before retrieve -> one page once
unclustered + sorting: at most all pages in B+ Tree
selectivity: % of tuples that satisfy selection condition
General Selection
Index Matching
index matches selection predicate:
index can be used to evaluate a selection
Hash index:
all
attributes in index search key appear in a predicate with
=
(conjunction of predicates)
B+ Tree
attributes in predicates form a
prefix
of search key in B+ Tree
order
of search key in B+ Tree matters
any operations can be used
A predicate (selection condition) can match >=1 index
A=7 AND B=5 AND C=4
hash index on (A) and B+ Tree on (B,C)
compute
selectivity
to decide which option/order is better
Selection with Disjunction (OR)
A=7 OR B>5; hash index on A + hash index on B
Only: file scan
A=7 OR B>5; hash index on A + B+ Tree on B
Solution 1: file scan
Solution 2: use both indexes, fetch
rids
,
union
,
retrieve
tuples
(A=7 OR C>5) AND B>5; hash on (A) + B+ Tree on B
Use B+ Tree to fetch B>5 tuples, then filter on A
Selectivity
selectivity
of access path = % of
tuples
to be retrieved
Choose the
most selective (small selectivity)
path
Estimate: 1/ #keys (uniform key) = 1/10 (default)
Range: selectivity = interval / (High-Low)