Query Execution

數(shù)據(jù)庫查詢語句的內(nèi)部執(zhí)行邏輯

components of query processor.png
  1. Turn SQL into a logical plan, which is represented as algebraic laws
  2. 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

Logical Query Plans.png

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
Physical Query Plans.png

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)存空間足夠媳溺,一次讀入處理完成
R交S.png

例子: 兩個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:

  1. 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)
  1. 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 
NLJ.png

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


sorting vs hashing.png

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)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市惜浅,隨后出現(xiàn)的幾起案子瘫辩,更是在濱河造成了極大的恐慌,老刑警劉巖坛悉,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件伐厌,死亡現(xiàn)場離奇詭異,居然都是意外死亡裸影,警方通過查閱死者的電腦和手機挣轨,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來空民,“玉大人刃唐,你說我怎么就攤上這事〗缧” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵衔瓮,是天一觀的道長浊猾。 經(jīng)常有香客問我,道長热鞍,這世上最難降的妖魔是什么葫慎? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮薇宠,結(jié)果婚禮上偷办,老公的妹妹穿的比我還像新娘。我一直安慰自己澄港,他們只是感情好椒涯,可當我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著回梧,像睡著了一般废岂。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上狱意,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天湖苞,我揣著相機與錄音,去河邊找鬼详囤。 笑死财骨,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播隆箩,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼该贾,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了摘仅?” 一聲冷哼從身側(cè)響起靶庙,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎娃属,沒想到半個月后六荒,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡矾端,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年掏击,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片秩铆。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡砚亭,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出殴玛,到底是詐尸還是另有隱情捅膘,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布滚粟,位于F島的核電站寻仗,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏凡壤。R本人自食惡果不足惜署尤,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望亚侠。 院中可真熱鬧曹体,春花似錦、人聲如沸硝烂。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽钢坦。三九已至究孕,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間爹凹,已是汗流浹背厨诸。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留禾酱,地道東北人微酬。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓绘趋,卻偏偏與公主長得像,于是被迫代替她去往敵國和親颗管。 傳聞我的和親對象是個殘疾皇子陷遮,可洞房花燭夜當晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容