代數優化是查詢優化的關鍵方面之一，它涉及關係代數表示式的變換和改進。 這些表示式通常由查詢處理過程中的查詢分析和檢查步驟生成。 通過應用一系列代數規則和啟發式方法，代數優化的目標是找到成本最低的執行計畫。
以下是關係代數表示式變換的一些基本規則，這些規則是代數優化過程中常用的工具：
交換：連線和笛卡爾乘積運算都充滿了**反轉，即改變運算順序不影響結果。
笛卡爾乘積交換定律：$e 1 乘以 e2 = e2 乘以 e1 $$
自然聯絡的交換定律：$e 1 領結 e2 = e2 領結 e1 $$
自然聯絡的交換定律：$e 1 bowtief e2 = e2 bowtief e1$$
關聯性：連線和笛卡爾積也滿足並集定律，這使我們能夠在不改變結果的情況下重新組織運算的組合方式。
笛卡爾乘積關聯性：$e 1 乘以 e2） 乘以 e3 = e1 乘以 （e2 乘以 e3） $
自然連線粘接法則：$e 1 個領結 e2） 領結 e3 = e1 領結 （e2 領結 e3） $
條件連線關聯定律： $e 1 bowtie1} e2） bowtie2} e3 = e1 bowtie1} （e2 bowtie2} e3） $
選擇級聯選擇定律：選擇操作可以串聯執行，也可以按任何順序執行。 合併條件（和連線條件）可以分解為多個選擇操作。
選擇運算順序的換向定律：$sigma（ sigma（e）） = sigma（ sigma（e））。
連詞條件分解定律：$sigma（e） = sigma（e） cap sigma（e） $
投影運算串聯定律：如果投影的屬性集是另乙個投影屬性集的子集，則可以將兩個投影操作合併為乙個。
pi（ pi（e）） = pi（e） 當 （ai subseteq b j）$$
選擇換向與其他操作：在某些情況下，選擇操作可以與笛卡爾積、投影和連線操作進行交換，以便可以先過濾小資料集，從而減少後續操作的資料量。
選擇和笛卡爾積：$sigma（e1 times e2） = （ sigma（e1）） times e2 $$，如果 （f） 中涉及的所有屬性都是 （$e 1$） 中的所有屬性。
選擇和投影：$sigma（ pi（e）） = pi（ sigma（e）） 如果 （f） 僅與 （a） 的性質有關。
分配性：對於並集和自然連線操作，選擇操作是分布式的，而投影操作對於笛卡爾乘積求和操作是分布式的。
選擇和平行： $sigma（e1 cup e2） = sigma（e1） cup sigma（e2） $
選擇和差分演算法： $sigma（e1 - e2） = sigma（e1） -sigma（e2） $
選擇與自然聯絡：$sigma（e1 領結 e2） = （ sigma（e1）） 領結 （ sigma（e 2）） 如果 （f） 只涉及共同屬性。
這些轉換規則的應用使我們能夠將複雜的查詢表示式轉換為一系列更有效的操作步驟。 例如，通過推遲對大型表的聯接操作，並首先對小型表執行選擇和投影操作，可以顯著降低查詢成本。
代數優化的目標
代數優化的最終目標是減少查詢期間的磁碟操作，因為磁碟訪問通常是資料庫操作中最耗時的部分。 此外，優化器還嘗試減小中間結果的大小，並降低 CPU 計算的複雜性。
在實際的DBMS中，代數優化通常是自動化的。 優化器根據資料庫統計資訊（如表的大小、索引的存在與否、資料的分布特徵）選擇最佳執行計畫。 但是，資料庫管理員和有經驗的使用者可以通過查詢重寫或使用特定的查詢提示來幫助或指導優化程式的選擇。
總的來說，代數優化是查詢優化的乙個組成部分，確保資料庫系統能夠以最有效的方式執行使用者的查詢請求。
選擇操作優先原則：此規則的基礎是，盡早過濾掉不相關的資料可以顯著減少後續操作處理的資料量。 通過在查詢的早期應用選擇（篩選）條件，可以避免對不需要的資料執行複雜的操作。
投影操作優先原則：與選擇操作類似，投影（確定需要哪些列）操作也應盡早進行，以減小處理資料的寬度，尤其是在聯接操作之前。
笛卡爾積合併規則：笛卡爾乘積產生大量中間結果，通常是不必要的。 因此，笛卡爾積應盡可能與選擇和投影等其他操作相結合，以減少中間結果的產生。
提取常用表示式規則：如果乙個計算在多個地方重複，並且計算的結果集很小，則應計算一次，並將結果快取起來以供後續操作使用。
假設我們想從資料庫中檢索所有選修課，其數字為'02'課程的學生姓名。 SQL 查詢語句可能如下所示：
select s.sname from s, sc where s.sno = sc.sno and sc.cno = '02';在沒有優化的情況下，資料庫可能會在應用選擇條件之前執行笛卡爾積，這是非常低效的。 應用啟發式方法後，我們可以按如下方式細化查詢執行計畫：
選擇操作優先順序首先，我們應用選擇標準sc.cno='02'篩選sc表，用於減小後續操作的資料集大小。
投影操作優先： 其次，我們只選擇s.sname跟s.sno，以及符合條件的人sc.sno以進一步減小資料的寬度。
合併笛卡爾乘積：我們在選擇操作後立即進行連線操作，避免了不必要的大量中間資料的生成。
提取常用表示式：如果sc.cno='02'是一種常見的查詢條件，其結果可以快取，以便後續查詢快速使用。
優化後的查詢執行方案如下：
select s.sname from s join sc on s.sno = sc.sno where sc.cno = '02';在這個優化的查詢計畫中，我們從
sc該錶應用選擇條件，然後僅對此篩選的結果集執行聯接操作。 這種策略將大大提高查詢的效率。
從這些示例中，我們可以看到適當的查詢優化可以極大地提高資料庫系統的效能。 此過程通常是自動化的，使用者不必擔心底層執行細節，但了解這些優化原則可以幫助您編寫更高效的查詢。
物理優化是查詢優化的重要組成部分，它涉及底層資料訪問方式和執行演算法的選擇。 目的是通過選擇最有效的訪問路徑和操作演算法減少資源消耗，提高查詢執行過程中的查詢速度。 物理優化通常包括基於啟發式規則的優化和基於成本估算的優化。
在物理優化中，啟發式規則提供了一組經驗法則，可以在沒有詳細統計資訊的情況下快速指導訪問路徑的選擇。
選擇操作的啟發式規則
對於具有小關係的查詢，即使存在索引，全表掃瞄也往往是最快的。
對於主鍵等效查詢，通常使用主鍵索引，因為結果最多只有乙個元組。
對於非主要屬性的等效查詢，如果存在索引並且預期返回的元組數量較少（小於總數的 10%），則應考慮索引掃瞄; 否則，使用全表掃瞄可能更有效。
對於不相等或範圍查詢，如果結果集較小且具有索引，則同樣應優先考慮索引掃瞄。
對於具有 AND 聯接的多條件查詢，如果存在涉及多個條件的復合索引，則復合索引優先。
對於已聯接 OR 的查詢，通常使用完整表掃瞄。
連線操作的啟發式規則
如果兩個表都已按聯接屬性排序，則應使用排序合併聯接。
如果其中乙個表在 join 屬性上具有索引，則通常首選索引聯接。
如果兩個表都很大並且沒有索引優勢，請考慮使用雜湊聯接。
如果上述規則均不適用，請考慮使用巢狀迴圈聯接，尤其是當乙個錶比另乙個表小得多時。
假設我們有乙個簡單的查詢：從employees在表中檢索部門為“銷售”的所有員工記錄。 我們的資料庫包含以下統計資料：
employees共享的表b塊。
每個塊可以包含r記錄。
部門列具有非聚集索引。
基於成本的優化計算每個操作演算法的執行成本，這需要了解資料庫的狀態，包括：
表的元組總數 （n）。
表的元組的平均長度 （l）。
表（b）占用的資料塊數。
每個欄位的不同值數 （m）。
字段選擇率 （s）。
索引的層數 （l）。
索引的選擇基數 （s）。
基於上述資訊，查詢優化器可以使用以下演算法來估算執行查詢的成本：
全表掃瞄演算法成本估算
成本 （ 成本 = b ）。
如果選擇條件為“主程式碼 = 值”，則平均搜尋成本 （cost = frac$）。
估算索引掃瞄演算法的成本
如果選擇條件為“code = value”，則使用表的主索引，如果是b+樹，層數為l，則成本（成本=l+1）。
巢狀環路連線演算法成本的估算
對於兩個表的巢狀迴圈聯接，如果其中乙個表較小，則可以將較小的表放入內部迴圈中，代價為 （ cost = b + frac times b }$
排序-合併連線演算法成本估算
如果聯接表已按聯接屬性排序，則成本 （ 成本 = b + b + 壓裂乘以 n 乘以 n}}$
其中：$b$） 和 （$b$） 分別是兩個連線表占用的資料塊數。
k ） 是記憶體中可用於儲存資料的資料塊的數量。
f$ 是連線選擇性，表示連線結果的元組數占比例。
m $ 是儲存連線結果的塊因子，表示每個塊中可以儲存的結果元組的數量。
假設employees該錶有 1000 個資料塊，部門列的非聚類索引有 3 個圖層，我們希望使用此索引快速定位“銷售”部門中的員工。
估算完整表掃瞄的成本
成本 （ 成本 = 1000$ ）。
估算索引掃瞄的成本
成本 （成本 = 3 + 1 = 4$） 假定索引掃瞄直接以所需記錄為目標）。
如果“銷售”部門的員工百分比低於 10%，則索引掃瞄將是一種更有效的方法，因此我們選擇它作為我們的查詢策略。 在更複雜的查詢中，需要考慮更多因素，例如聯接操作、併行執行等。