查詢優化
數據庫管理系統中非常重要的一部分。
代數優化
按照一定的規則將語句變化成關系代數以后進行優化
操作優化
對代數優化后的查詢樹使用比較好的方法進行查詢。
主要是對連接運算進行優化
- 嵌套循環
- 歸并掃描
- 索引優化
- 哈希連接
恢復機制
備份（完整備份+差異備份）+日志
事務
- A：原子性
- C：保持一致性
- I：隔離性
- D：持久性
事務的特性由DBMS負責維護，因此對于需要使用事務來進行執行的SQL語句，我們要定義在事務中。
如果沒有顯式地創建事務，那么DBMS會把每一條語句當作一個事務。
恢復信息
日志存儲在非揮發存儲器中。
- Commit list：已經提交的TID的列表
- Active list：進程中的TID列表
- Log：更新前和更新后的信息。存儲的是修改前后的物理塊的值
提交(commit)規則：在提交事務之前修改后的數據A.I必須寫到非揮發存儲器中
先記后寫(log ahead)規則：在修改數據前必須把被修改數據的舊值B.I寫到日志中
操作：
- 還原undo
- 重做redo
這兩種操作具有冪等性：一次和和好多次是相等的
更新策略
A.I->DB before commit
TID->active list
…
B.I->Log
A.I->DB
…
TID->commit list
delete TID from active list
如果發生故障會啟動重啟動恢復：檢查TID目前所處的狀態
| Commit list | Active list | Operation |
|---|---|---|
| No | Yes | undo,delete TID from active list |
| Yes | Yes | delete TID from active list |
| Yes | No | nothing to do |
為了避免每次檢查都需要檢查所有的TID，使用檢查點。
檢查點(check point)：運行一段時間以后進行一次檢查，并且設立一個檢查點。每次檢查檢查上一次檢查點以后的TID
A.I->DB after commit
TID->active list
…
A.I -> Log
…
TID->commit list
ALL:A.I -> DB
delete TID from active list
重啟動恢復：
| Commit list | Active list | Operation |
|---|---|---|
| No | Yes | delete TID from active list |
| Yes | Yes | redo, delete TID from active list |
| Yes | No | nothing to do |
這種策略的并發度更高。可以推遲加排他鎖的時間。
A.I -> DB concurrently with commit
TID -> active list
…
A.I,B.I -> log
…
A.I->DB(partially done by 后臺進程 when hard disk is free)
…
TID->commit list
A.I->DB(completed)
delete TID from active list
重啟動恢復：
| Commit list | Active list | Operation |
|---|---|---|
| No | Yes | undo, delete TID from active list |
| Yes | Yes | redo, delete TID from active list |
| Yes | No | nothing to do |
總結
| redo | undo | |
|---|---|---|
| A.I->DB before commit | No | Yes |
| A.I->DB after commit | Yes | No |
| A.I->DB concurrently commit | Yes | Yes |
| 異地更新(有缺點，沒有被推廣) | No | No |
并發控制
并發：支持多個事務同時訪問數據庫
原因：
- 改善系統的利用率
- 不同的事務很可能訪問的是不同的數據，互不沖突
并發控制：對事務的并發運行加以管理
任意并發的后果：
- 丟失更新：寫-寫沖突
- 讀臟數據->恢復時的多米諾現象：寫-讀沖突
- 不可重復的讀：讀-寫沖突
可串行化：并發運行事務以后的結果如果和某種串行運行的結果相同，則說這種并發運行是可串行化的，即是正確的。
如果用戶把一些事務同時提交并發運行，則要求這些事務誰先運行后運行是無所謂的，即默認所有可串行化的結果都是正確的。
并發控制策略
通過并發控制使得并發事務的運行是可串行化的
封鎖法
通過鎖對事務強行串行化
- X鎖協議（排他鎖）
定義1：在一個事務里面，如果所有的加鎖請求都在鎖釋放之前，稱這個事務是一個兩階段事務，符合兩階段加鎖協議。（增長階段-縮減階段）
定義2：先得到鎖再訪問數據對象，那么這個事務就是well-formed（合式的）
定義：如果每個事務是合式的兩階段事務，那么這些事務一定是可串行化的。
如果事務是合式的并且是兩階段事務，并且在事務結束的時候釋放更新鎖，那么這個事務是可串行化的、可恢復的。不會出現恢復的時候的多米諾效應
如果在事務結束的時候釋放所有的鎖，那么稱這個事務滿足嚴格的兩階段加鎖協議。
| NL | X | |
|---|---|---|
| NL | Y | Y |
| X | Y | N |
數據庫效率比較低。
- SX鎖協議
S(hare) lock ：如果是讀操作
X lock：如果是更新操作
| NL | S | X | |
|---|---|---|---|
| NL | Y | Y | Y |
| S | Y | Y | N |
| X | Y | N | N |
- S(share)U(update)X locks
| NL | S | U | X | |
|---|---|---|---|---|
| NL | Y | Y | Y | Y |
| S | Y | Y | Y | N |
| U | Y | Y | N | N |
| X | Y | N | N | N |
系統的并發度較高。
死鎖/活鎖（饑餓）
活鎖/饑餓：優化調度策略
死鎖：
- 防：防止出現死鎖
- 治：出現死鎖以后能夠解決死鎖。
治：
- 當事務獲得鎖以后的等待時候超過一個限度以后就判定已經發生了死鎖，就重啟事務。對于時間的設置影響系統的運行效率
- 構造等待圖
節點：等待的事務
邊：等待關系
如果在等待圖里面出現環就說明出現死鎖。
檢查時機：每次出現新的等待關系的時候/周期檢查
解決方法：選擇一個犧牲者（目前擁有鎖最小的/滾回代價最小的事務）。然后等待環路上的其他事務都運行結束以后再運行該事務。
防
操作系統中的解決方案：
- 檢查所需要的所有資源
- 給資源進行排序
在數據庫系統中不現實
多粒度加鎖
- 一旦遇到得不到鎖就終止，不等待就不會死鎖
- 事務重試：給每一個事務安排一個時間戳
- 當作TID
- 比較兩個事務的年齡
等待死亡協議：
如果Ta需要申請一個鎖，這個鎖已經被Tb占領了：
- 如果Ta比Tb年老，則Ta進行等待
- 如果Ta比Tb年輕，則自己終止，然后自動重新運行（以原來的時間戳）
因此不可能重現循環等待，解決了死鎖和活鎖問題
受傷等待協議：
如果Ta需要申請一個鎖，這個鎖已經被Tb占領了：
- 如果Ta比Tb年輕，則Ta進行等待
- 如果Ta比Tb年老的話，則將Tb終止
