最佳化技術

在計算機系統中，為了提高系統或程式的性能，經常需要用到最佳化技術。最佳化技術是指通過一定的方法或策略使系統或程式有關性能提高。最佳化技術不只是對計算機哪一方面進行最佳化，而是在多個領域使用最佳化技術進行最佳化，如記憶體、代碼結構等。

基本介紹

• 中文名：最佳化技術
• 外文名：optimization technique
• 學科：計算機
• 定義：使系統或程式有關性能提高
• 目的：提高性能
• 領域：計算機系統

簡介

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

數據流分析

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

數據流分析試圖獲得程式中每一點的特定信息。通常，在基本塊(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 的引出，使最佳化過程只需進行少量的如果假設調用，利用線性規劃現有的方法高效地解決了索引的選擇最佳化問題。基於線性規劃的方法解決物理結構最佳化問題近幾年才開始廣泛研究和套用。

物化視圖

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

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