[發明專利]記錄查詢優化中的譜系

在審

• 申請號: 201980072723.3
• 申請日: 2019-10-29
• 公開（公告）號: CN112970011A
• 公開（公告）日: 2021-06-15
• 發明（設計）人: C·S·弗雷德曼;V·帕帕迪默斯
• 申請（專利權）人: 微軟技術許可有限責任公司
• 主分類號: G06F16/2452
• 分類號: G06F16/2452
• 代理公司: 北京市金杜律師事務所 11256
• 代理人: 黃倩

一種數據庫系統包括查詢優化器，查詢優化器以聲明性查詢語言將變換應用于輸入查詢的邏輯表示，以生成查詢執行計劃的表達式。查詢優化器針對每個規則應用存儲指示所應用的變換和變換的綁定的信息，該綁定指示輸入給變換的表達式。當新的查詢執行計劃將針對輸入查詢被生成時，查詢優化器針對原始查詢執行計劃中的表達式使用該存儲信息，以指導查詢優化器產生當前的查詢執行計劃，同時避免變換不被用于在原始查詢執行計劃中生成表達式。

背景技術

當前大多數數據庫系統都允許用戶以聲明性或非程序性語言(諸如結構化查詢語言(SQL))指定查詢。聲明性語言指定數據庫記錄必須滿足才能響應查詢的條件。當查詢是以這種方式指定時，數據庫系統會將查詢轉化為操作集合，通常稱為“查詢執行計劃”，這些操作在數據庫上被執行以執行該查詢。通常，查詢被變換為樹或圖表示，繼而被用于生成查詢執行計劃。這些操作通常采用程序性計算機語言的形式。有許多可能的操作以及操作的可能組合可以被執行以實現任何給定的查詢，其中一些比其他更有效。因此，數據庫系統嘗試找到最優的或至少合理有效的操作組合，作為給定查詢的查詢執行計劃。該過程被稱為“查詢優化”。

在查詢優化中，操作的可能組合通常可以被視為定義了用于優化過程的搜索空間的樹或圖。一些查詢可以具有成千上萬甚或更多的可能實現。

因此，查詢優化是在大的搜索空間上進行搜索的一種形式，以找到最優的或合理有效的解決方案。因此，一些查詢優化方法是自上而下的搜索，而一些則是自下而上的搜索；一些方法是深度優先搜索，而其他方法是廣度優先搜索。用于查詢優化的許多技術已在各種數據庫系統中被使用。通常，查詢優化的結果是數據庫操作組合的樹或圖表示，該數據庫操作映射到查詢的類似樹或圖表示。

查詢被解析以生成查詢的初始表示，通常為樹。在基于規則的自上而下的查詢優化方法中，該初始樹是通過應用變換規則來變換的。變換規則可以提供查詢的替代邏輯等效表示。變換規則可以提供實現部分查詢的可能操作。查詢優化的其他方法(諸如自下而上的方法)可以使用輸入查詢的不同邏輯表示，變換被應用于該不同邏輯表示以探索搜索空間。通常使用的變換類型取決于查詢的邏輯表示和所使用的搜索空間探索類型。應用這種變換的結果是用于實現查詢的許多替代方案。這些替代方案針對可能性能影響或計算成本而被評估。這種評估是在查詢優化過程期間執行的，并且通常會導致修剪一些變換，而導致這些變換不進一步用于探索搜索空間。應用所有可用的變換(其中多次調用這種變換)可能會導致實現查詢的大量可能的操作組合。

查詢優化消耗了數據庫系統的大量處理資源。查詢優化時間隨查詢的大小和復雜性呈指數增長。查詢執行計劃還可能消耗大量內存。當一些數據庫系統緩存查詢執行計劃時，如果出于一些常見原因，查詢執行計劃不再在緩存中，則查詢執行計劃可能需要針對查詢來重新計算。例如，緩存的替換策略可能會導致查詢執行計劃從緩存中被移除。作為另一示例，響應于系統重啟，緩存可以被清空，并且數據庫系統可以在重啟那些查詢之前針對幾個查詢執行查詢優化。作為另一示例，當關于數據庫性能的統計信息被更新時，這些統計信息可能會影響可能的操作組合的估計成本，并且數據庫系統可能會再次執行查詢優化。

發明內容

該發明內容被提供來以簡化的形式介紹對于下面在詳細描述中進一步被描述的概念的選擇。該發明內容既不旨在標識所要求保護的主題的關鍵或必要特征，也不旨在限制所要求保護的主題的范圍。

查詢優化器針對由變換生成的每個可能的表達式記錄指示該變換以及生成該表達式的輸入的數據。當表達式集合被選擇作為查詢執行計劃時，用于生成這些表達式的變換可以被標識。當查詢優化器第二次處理查詢時，所記錄的關于變換和被用于生成原始查詢執行計劃的輸入的數據可以被用于指導優化過程第二次產生原始查詢執行計劃。

在以下描述中，參考附圖，附圖形成該描述的一部分，并且在附圖中通過說明的方式示出了特定示例實現。在不脫離本公開的范圍的情況下，其他實現可以被進行。

附圖說明

圖1是示例計算環境的框圖，該示例計算環境包括執行查詢優化的數據庫系統。