數(shù)據(jù)庫查詢語句的內(nèi)部執(zhí)行邏輯
- Turn SQL into a logical plan, which is represented as algebraic laws
- Turn logical query plan into a physical one
Query optimization can be done in 2 ways above:
1.Logical Query Optimization（關(guān)系代數(shù)優(yōu)化嗽上，啟發(fā)式查詢）
2.Physical Query Optimization（IO成本最低優(yōu)化,這里我們主要討論物理層面上的查詢過程）
Logical/physical operators
Logical operator: what they do
union, join, selection, projection, group by
Physical operator: how they do（implementation）
- scanning, hashing, sorting, and index-based
- methods for implementing join can be: nested loop join, sort-merge join, hash join, index join
- different algorithm has different requirements on the amount of available memory & different costs
Each operation is implemented by 3 functions:（operation簡單的說就是對數(shù)據(jù)操作的過程）
- Open: sets up the data structures and performs initializations
- GetNext: returns the next tuple of the result.
- Close: ends the operations. Cleans up the data structures
Cost Model
Notation：
- M = number of blocks/pages that are available in the main memory
- B(R) = number of blocks holding in relation R
- T(R) = number of tuples in the relation R
- V(R, a) = number of distinct values of the attribute a in relation R
Assumption:
- only consider I/O cost( ignore CPU computation cost)
- don't include the cost of writing the result (最后一步的結(jié)果寫出不計在內(nèi))
- table(relation) is clustered, that is for relation R, the cost of scanning the whole table is B(R)
Physical operator classification
- One-pass algorithm
- Nested-Loop Join algorithm
- Two-pass algorithm (sorting & hashing)
- K-pass algorithm
- Index-based algorithm
One-pass algorithm
- Read the data only once from disk
- Usually, require at least one of the input relations fits in main memory
主要是處理relation比較小的情況闰靴，內(nèi)存空間足夠媳溺，一次讀入處理完成
例子: 兩個relation相交
- Read S into M-2 buffers and build a search structure
- Read each block of R, and for each tuple t of R, see if t is also in S --- 有一張表必須足夠小到可以完全放進內(nèi)存中
- If so, copy t to the output; if not, ignore t
這里需要保證內(nèi)存的空間最夠膝藕，也就是(M-2)>= min(B(R),B(S))认境，保證一次能夠?qū)⒛骋粋€relation完全讀入，兩外的一個input page作為另一個relation的讀入辩蛋，一個output page作為處理結(jié)果輸出
Nested-loop join algorithm
- Read one relation only once, while the other will be read repeatedly from disk (one to many mode)
example:
- Tuple-based Nested Loop Join Join R ? S
Assumption: neither relation is clustered
for each tuple r in R do
for each tuple s in S do
if r and s join then output (r,s)
total cost: T(R)*T(S)
- Block-based Nested Loop Join Join R ? S
Assumption:
each relation is clustered;
memory size M pages;
B(R)<=B(S) and B(R)>m 表明內(nèi)存無法一次完全讀取一張表
for each (M-2) blocks br of R do
for each block bs of S do
for each tuple r in br do
for each tuple s in bs do
if r and s join then output(r,s)
Cost:
– Read R once: cost B(R)
– Outer loop runs B(R)/(M-2) times, and each time need to read S: costs B(R)B(S)/(M-2)
– Total cost: B(R) + B(R)B(S)/(M-2)
R as outer loop Cost: B(R) + B(R)B(S)/(M-2)
S as outer loop Cost: B(S) + B(R)B(S)/(M-2)
=> It is better to iterate over the smaller relation first
Suppose M = 102 blocks (i.e., pages), B(R) = 1,000 blocks, B(S) = 5,000 blocks
以R作為outer loop，每次讀取100個blocks進入內(nèi)存翩蘸，也就是說B(R)這張大表被分割成50個每個大小為100pages的小表，然后對每個表進行一次內(nèi)部循環(huán)淮逊，內(nèi)部循環(huán)就是對其中的每個記錄去S這張大表中檢索催首，由于有50次，每一次的內(nèi)部循環(huán)都需要去讀取整個B(S) 泄鹏，所以最后的cost為 1000（外部循環(huán)讀取的成本） + 50*5,000 （內(nèi)部循環(huán)讀取的成本）
- What is the minimum memory requirement郎任？
Answer: 3
Two-pass algorithm based on sorting
- First pass: read data from disk, process it, write it to the disk
- Second pass: read the data for further processing
為什么需要two-pass？ an operation can not be completed in one pass备籽，主要就是空間的問題
1.Simple example: B(R) distinct operation(duplicate elimination)
步驟：1. sort first 2. eliminate duplicate
pass1: read B(R), sort it into runs with M pages and write Cost: 2B(R)
pass2: merge M-1 runs, include each tuple only once Cost: B(R)
Assumption:
number of runs from pass1: B/M
B/M must be less of than M-1 because we can only proceed M-1 ways merging in pass2
so
B/M <= M-1
roughly B <= M^2
2.Sort-Merge Join => 基于Sort-Merge的join其實是有問題的舶治，想想為什么分井？
（Assumption: memory buffer is enough to hold join tuples for at least one relation）
3.Simple Sort-based Join
這里和Sort-Merge Join的區(qū)別在于，首先將B(R)和B(S)進行merge-sort得到每一個表的一個runs霉猛，Sort-Merge Join只是根據(jù)內(nèi)存的大小對B(R)尺锚，B(S)進行排序得到B/M個runs
所以一般而言Simple Sort-based Join比較保險
Assumption:
B(R) <= M(M-1) , B(S) <= M(M-1)
and at least one set of the tuples with a common value for the join attributes fit in M-2 pages
Note that we only need 1 page buffer for the other relation
Two-pass algorithm based on Hashing
hash idea:
All the tuples of input relations get to the same bucket
Reduce the size of input relations by a factor of M
Perform the operation by working on a bucket at a time
Index-Based algorithm
useful for selection operations
Selection on equality a=v(R) (ignore the cost of reading index block and here we consider the worst time)
Clustered index on attribute a => cost: B(R)/V(R,a)
Unclustered index on a => cost: T(R)/V(R,a)
Example: B(R) = 2000, T(R) = 100,000, V(R, a) = 20, compute the cost of a=v(R)
Cost of using table scan:
– If R is clustered: B(R) = 2000 I/Os
– If R is unclustered: T(R) = 100,000 I/Os
Cost of index-based selection:
– If index is clustered: B(R)/V(R,a) = 100 I/Os
– If index is unclustered: T(R)/V(R,a) = 500 I/Os
Index-Based Join
Assumption:
1.S has an index on the join attribute
2.R is clustered
Step: iterate over each tuple in R, fetch corresponding tuple from S
Cost:
if the index is clustered:B(R) + T(R)B(S)/V(S,a)
if the index is unclustered: B(R) + T(R)T(S)/V(S,a)
if both R and S have a clustered index on the join attribute
Then can perform a sort-merge join where sorting is already done (for free)
Cost: B(R) + B(S)
