優化技術

優化技術是指通過一定的方法或策略使系統或程序有關性能提高。優化技術的好處主要可以從以下幾個方面來體現：內存利用更加合理；運行時間更短；讀取數據的數據更快；準確率更高等。不管是從軟件角度還硬件角度進行優化工作，優化技術的基礎是數據流分析和控制流分析。

數據流分析是一項編譯時使用的技術，它能從程序代碼中收集程序的語義信息，並通過代數的方法在編譯時確定變量的定義和使用。通過數據流分析，可以不必實際運行程序就能夠發現程序運行時的行為，這樣可以幫助大家理解程序。數據流分析被用於解決編譯優化、程序驗證、調試、測試、並行、向量化和片行編程環境等問題 ^[1]  。

數據流分析試圖獲得程序中每一點的特定信息。通常，在基本塊(basic blocks)的界限內就可以獲得這些信息，因為很容易計算基本塊中的信息。在前向流分析(forward flow analysis)中，一個塊的結束狀態是這個塊起始狀態的一個函數。函數由塊內的語句的影響信息組成。一個塊的開始狀態是它的前驅的結束狀態的函數。這就產生了一系列的數據流方程：

對於每一個塊b：

在這裏，

是塊b的轉移函數。它作用於入口狀態

，併產生出口狀態

。連接運算符join將塊b的前驅節點

的出口狀態聯合起來，產生入口狀態b。在求解這一系列方程之後，塊的入口和出口狀態可以被用來獲得程序在塊內的屬性。每條語句的轉移函數可以被分別的用於獲得在一個基本塊內的某一點的信息。每一個特定類型的數據流分析都有它自己的特定的轉移函數和連接運算符。一些數據流問題需要後向數據流分析。和前向數據流分析類型，除了轉移函數是使用出口狀態來產生入口狀態，而連接運算符作用於後繼節點的入口狀態以產生出口狀態。(在前向流分析中的)入口點起着重要的作用：因為它沒有前驅節點，它的入口信息在分析開始時是明確的。比如，可以確定的局部變量的值的集合此時為空。如果控制流圖並不包含循環(在程序中顯性的或隱性的循環)，只需直接求解數據流方程即可。此時可以對控制流圖的基本塊進行拓撲排序；按照排序後的結果依次計算，則每個塊的入口狀態都可以在塊起始處計算，因為此時塊的所有前驅節點都已經計算過了，所以它們的出口狀態是可以獲得的。如果控制流圖包含循環，那麼就需要一個更高級的算法。

控制流分析（Control flow analysis）簡稱CFA，是一種確認程式控制流程的靜態代碼分析技術。控制流程會以控制流圖來表示。對於函數編程語言及面向對象程式設計，CFA都是指計算控制流程的算法。

對於像是Scheme之類有高階函數的編程語言，不一定可以會程式中直接看出函數呼叫的目標，例如以下的程式片段

(lambda (f) (f x))

根據上述程式無法確認程序f是指什麼，此情形下的控制流分析需考慮何時會執行此程式碼，及當時的傳入值。抽象釋義、約束補償及型別系統都可以用來進行控制流分析。

關係數據庫的物理結構、查詢優化器和執行引擎是影響數據庫查詢性能的主要因素。數據庫物理結構的改變雖然不會影響應用的查詢結果，但會影響數據庫性能。早期的關係數據庫主要用於聯機事務處理,數據規模較小，通常進行查詢語句和執行引擎的優化，物理結構設計的重要性沒有充分得到體現。數據庫的物理結構是整個數據庫存儲的基礎，主要在設計階段確定而且具有持久性，也就是説,物理結構一旦確定，不會經常變化。一般在以下情況下會發生物理結構的優化推薦：

數據被移植到一個新的存儲系統；

數據庫的應用模式有了較大的變動,主要指的是元數據的變化；

數據庫的工作負荷(workload)有很大的變動,主要指的是查詢語句的使用變化；

數據庫性能明顯降低。

數據庫物理結構優化是指為數據庫系統的數據推薦合適的物理存儲位置或存儲結構，以及為查詢推薦合適的存取路徑，進而改進整個系統的性能。在數據倉庫還沒有發展起來之前，物理結構優化的早期產品一般只考慮索引這一種物理結構的優化。但是，隨着互聯網等技術的發展，數據倉庫技術的廣泛應用，為了進一步提高系統的性能，數據庫系統逐漸提供了對其他物理結構種類的支持，除了傳統的索引之外，還有物化視圖、無共享分區和多維聚集等。

索引(index)是數據庫系統中用於提高檢索查詢速度的數據組織，一般情況下可以顯著提升數據庫系統檢索查詢的性能，也可以快速檢索特定數據和範圍數據以及提升數據值唯一性等。通常在索引的選擇過程中，除了選擇最好的單一屬性索引之外，還需要逐漸考慮附加索引，以確定是否有更好的選擇方案。有些情況下，雖然創建新的索引提升了查詢效率，但卻嚴重降低了更新性能。因此，當判斷一個新的索引是否可用時，通常要考慮查詢和更新的性能組合。索引設計過程中需要考慮的關鍵問題包括：(1) 增加一個索引是否會對檢索有益；(2) 使

用什麼類型的索引；(3) 索引需要包括哪些屬性的組合；(4) 考慮索引對存儲空間的需求;(5) 在表更新時，索引是否還是有益的.綜合考慮上面的幾個因素，當一個索引的收益大於其開銷時，就應當創建並使用該索引，其中的收益和開銷都依賴於響應時間和吞吐量。當一個已用索引的性能變得較差時,需要選擇優化新的設計方案。索引優化是物理結構優化領域最早開始研究的問題。因此，關於 ISP 的算法有很多。 以下有兩種方法:一種是基於揹包子問題和基於拉格朗日分解的啓發式算法，這種方法適合應用在大規模 ISP問題上；另一種方法是基於線性規劃的分支界限法，這種方法通過預處理過程降低候選索引集的大小來提高索引

的選擇效率。在 ISP 問題上，以上方法都存在效率低下和優化質量不高的問題，比如啓發式算法在索引方案產生之前,由於候選索引各自收益或者價值的相互作用，導致其最後得到的不一定是最好的優化方案.更重要的是，自動優化技術大都依賴於如果假設分析接口，實現對某個查詢的索引集合的收益的精確評價，如果工作負荷集比較大，再加上針對每個查詢的巨大的解決方案集合，整個優化過程就會依賴於大量的如果假設調用,顯著增加了優化推薦過程的代價或成本。為了進一步解決效率問題，提出了一種截然不同的優化方法。利用 60 多年前在線性規劃領域的研究成果來解決ISP 問題，證明了基於快速如果假設分析的索引優化問題等價於簡潔的二進制整數規劃(BIP)問題。BIP 的引出，使優化過程只需進行少量的如果假設調用，利用線性規劃現有的方法高效地解決了索引的選擇優化問題。基於線性規劃的方法解決物理結構優化問題近幾年才開始廣泛研究和應用 ^[2]  。

物化視圖(materialized view)是用於保存在基表上進行連接或聚集等耗時較多的操作結果的一種數據庫對象。物化視圖存儲基於原始數據表的檢索數據，這樣在執行查詢時就可以直接訪問物化視圖,避免重複進行耗時的操作，從而加快得到結果的速度。

利用物化視圖能夠顯著改善磁盤 I/O 和檢索查詢性能，主要來源於以下4方面因素：(1) 利用專用磁盤生成視圖,避免 I/O 資源的競爭；(2) 物化視圖可能會比基表小很多，這為每次詢的磁盤 I/O 性能帶來很大的收益；(3) 降低多表之間的連接成本，減少計算量；(4) 對於經常訪問的查詢來説,收益倍增.物化視圖對應用透明，增加和刪除物化視圖不會影響應用程序中 SQL 語句的正確性和有效性。物化視圖的缺點是需要佔用存儲空間，當基表發生變化時，物化視圖也應刷新。同步更新問題嚴重降低了物化視圖的使用性能，因此在設計和使用時必須考慮更新性能。