• / 19
  • 下載費用:30 金幣  

增量式地更新統計.pdf

摘要
申請專利號:

CN201380076186.2

申請日:

2013.04.30

公開號:

CN105164675A

公開日:

2015.12.16

當前法律狀態:

撤回

有效性:

無權

法律詳情: 發明專利申請公布后的視為撤回 IPC(主分類):G06F 17/30申請公布日:20151216|||專利申請權的轉移IPC(主分類):G06F 17/30登記生效日:20180611變更事項:申請人變更前權利人:慧與發展有限責任合伙企業變更后權利人:安提特軟件有限責任公司變更事項:地址變更前權利人:美國德克薩斯州變更后權利人:美國加利福尼亞州|||專利申請權的轉移IPC(主分類):G06F 17/30登記生效日:20161025變更事項:申請人變更前權利人:惠普發展公司,有限責任合伙企業變更后權利人:慧與發展有限責任合伙企業變更事項:地址變更前權利人:美國德克薩斯州變更后權利人:美國德克薩斯州|||實質審查的生效IPC(主分類):G06F 17/30申請日:20130430|||公開
IPC分類號: G06F17/30; G06F17/18 主分類號: G06F17/30
申請人: 惠普發展公司,有限責任合伙企業
發明人: C·拉克什米納拉亞; R·科舒魯; 陳啟凡; H·澤勒
地址: 美國德克薩斯州
優先權:
專利代理機構: 北京德琦知識產權代理有限公司11018 代理人: 康泉; 宋志強
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201380076186.2

授權公告號:

||||||||||||

法律狀態公告日:

2019.02.22|||2018.06.29|||2016.11.16|||2016.01.13|||2015.12.16

法律狀態類型:

發明專利申請公布后的視為撤回|||專利申請權、專利權的轉移|||專利申請權、專利權的轉移|||實質審查的生效|||公開

摘要

增量更新統計包括,對數據庫中的數據庫列的行進行采樣以生成第一樣本;在生成第一樣本后,對數據庫列的修改的行的子集進行采樣以生成第二樣本;基于所述第一樣本和第二樣本,確定數據庫列是否發生分布變化;以及響應于確定存在分布變化,更新關于所述數據庫列的數據庫統計。

權利要求書

權利要求書
1.  一種用于增量式地更新統計的方法,包括:
對數據庫中的數據庫列的行進行采樣以生成第一樣本;
在所述第一樣本生成后,對所述數據庫列的修改的行的子集進行采樣以生成第二樣本;
基于所述第一樣本和所述第二樣本確定所述數據庫列是否發生分布變化;以及
響應于確定存在分布變化,相應地更新關于所述數據庫列的數據庫統計。

2.  根據權利要求1所述的方法,其中所述數據庫統計包括唯一條目計數,行計數,每直方圖區間的頻度的頻率以及整個直方圖統計頻度的頻率。

3.  根據權利要求1所述的方法,其中基于所述第一樣本和所述第二樣本確定所述數據庫列是否發生分布變化包括:確定與使用統計測試得出存在分布變化的結論關聯的置信度水平。

4.  根據權利要求3所述的方法,其中所述統計測試基于比較兩個時間段中的統計平均值和類似地兩個時間段中的統計方差。

5.  根據權利要求3所述的方法,其中所述統計測試在所述樣本被視為相關時是成對t-測試。

6.  根據權利要求3所述的方法,其中所述統計測試在所述數據的分布不符合正態分布的假設時是非參數測試、柯爾莫哥洛夫-斯米爾諾夫測試、其他的統計測試或其組合。

7.  根據權利要求3所述的方法,其中響應于確定存在分布變化更新關于所述數據庫列的數據庫統計包括:響應于置信度水平大于預定的置信度水平閾值而更新所述數據庫統計。

8.  根據權利要求1所述的方法,其中所述第一樣本是所述數據庫列中的行的至少百分之一。

9.  根據權利要求1所述的方法,進一步包括:基于所述數據庫統計,執行查詢計劃優化任務。

10.  根據權利要求1所述的方法,其中對所述數據庫列的修改的行的子集進行采樣以生成第二樣本包括:通過將所述第一樣本與來自所修改的行的子集的刪除和插入進行組合來生成所述第二樣本。

11.  一種用于增量式地更新統計的系統,包括:
采樣引擎,用于對數據庫中的數據庫列的行進行采樣以生成第一樣本,并且在生 成所述第一樣本之后,對所述數據庫列的修改的行進行采樣以生成第二樣本;
確定引擎,用于基于所述第一樣本和第二樣本確定是否發生分布變化;以及
更新引擎,用于響應于確定存在分布變化,更新關于所述數據庫列的唯一條目計數、行計數、直方圖區間的頻度的頻率、整個直方圖統計的頻度的頻率。

12.  根據權利要求11所述的系統,進一步包括置信度引擎,用于確定得出存在分布變化的結論的置信度水平。

13.  根據權利要求11所述的系統,其中所述置信度引擎進一步使用統計測試確定所述置信度水平。

14.  根據權利要求11所述的系統,其中所述統計測試包括:兩個樣本的t-測試、成對t-測試、非參數測試、柯爾莫哥羅夫-斯米爾諾夫測試、基于兩個時間段的統計平均值相互比較的測試、基于兩個時間段的統計方差相互比較的測試或其組合。

15.  一種用于增量式地更新統計的計算機程序產品,包括:
非瞬態計算機可讀存儲介質,所述非瞬態計算機可讀存儲介質包括嵌入到其中的計算機可讀程序代碼,所述計算機可讀程序代碼包括程序指令,在所述程序指令被執行時,引起處理器:
對數據庫中的數據庫列的行進行采樣以生成第一樣本;
在所述第一樣本生成后,對所述數據庫列的行的子集進行采樣以生成第二樣本,所述子集包括刪除的行、插入的行以及更新的行;
建立表示所述第一樣本和所述第二樣本的行的布隆過濾器;
基于所述第一樣本和第二樣本確定所述子集是否發生分布變化;以及
響應于確定存在分布變化,更新關于所述數據庫列的唯一條目計數、行計數、和直方圖區間的頻度的頻率,以及整個直方圖統計的頻度的頻率。

說明書

說明書增量式地更新統計
背景技術
在某些類型的數據庫中,比如關系型數據庫中,查詢計劃優化器使用關于數據庫的數據進行統計。響應于接收查詢,生成關于如何搜索數據庫的多個查詢計劃。查詢計劃優化器作出關于這些查詢計劃中的哪些將在最短時間內根據搜索查詢中的術語引起搜索數據庫的決定。依賴于數據庫,統計允許搜索查詢優化器在無需從頭計算關于數據庫的數據的信息的情況下,選擇查詢計劃。
附圖說明
附圖圖示本文描述的原理的各種示例并且是說明書的一部分。圖示的示例僅僅是示例并且不限制權利要求的范圍。
圖1是根據本文描述的原理的網絡上的數據庫的示例的示意圖。
圖2是根據本文描述的原理的數據庫列的樣本的示例的示意圖。
圖3是根據本文描述的原理的唯一條目計數估計器的示例的示意圖。
圖4A是根據本文描述的原理的布隆(bloom)過濾器的示例的示意圖。
圖4B是根據本文描述的原理的直方圖的示例的示意圖。
圖5是根據本文描述的原理從數據庫列的樣本刪除行的示例的示意圖。
圖6是根據本文描述的原理添加插入到的數據庫列的樣本的示例的示意圖。
圖7是根據本文描述的原理的布隆過濾器的示例的示意圖。
圖8是根據本文描述的原理的直方圖的示例的示意圖。
圖9是根據本文描述的原理用于增量式地更新數據庫統計的方法的示例的示意圖。
圖10是根據本文描述的原理的更新系統的示例的示意圖。
圖11是根據本文描述的原理的更新系統的示例的示意圖。
圖12是根據本文描述的原理的增量式地更新數據庫統計的過程的流程圖的示例的示意圖。
具體實施方式
為了提供查詢優化器有益的統計信息,統計被更新。然而,更新統計導致數據庫能力和處理資源耗盡。在某些情況下,因為資源被提供給更新統計,因此這種更新阻礙了其他操作的性能。
本文描述的原理包括在數據庫的數據分布已被確定在統計上保持不變時,用于利用較少工作且基于樣本估計統計更新統計的機制。該機制確定數據庫中的什么數據已經改變的足夠以值得更新統計,而不是僅基于樣本估計統計。這些原理包括用于增量式更新數據庫的方法。這種方法包括對數據庫中的數據庫列的行進行采樣以生成第一樣本,隨后在生成第一樣本之后,對數據庫列的修改的行的子集進行采樣以生成第二樣本,基于第一樣本和第二樣本確定數據庫列是否發生分布變化,并且響應于確定存在分布變化而更新關于數據庫列的數據庫統計。修改的行可包括刪除的行、插入的行、更新的行或其組合。
在下面的描述中,出于解釋的目的,為了提供本系統和方法的全面理解,提出了許多具體細節。然而,對本領域技術人員來說顯而易見的是,可在沒有這些具體細節的情況下實踐本裝置、提供和方法。說明書中提及的“示例”或類似語言意味著描述的特定的特征、結構或特性被包括在至少一個示例中,但不必在其他示例中。
圖1是根據本文描述的原理的網絡上的數據庫(100)的示例的示意圖。在此示例中,客戶設備(104)與網絡(102)通信,網絡(102)通信與數據庫(100)通信。
客戶設備(104)可以是用戶使用來與數據庫(100)通信的任何適當的設備。客戶設備(104)筆記本電腦、個人計算機、臺式機、電話、電子輸入板、電子設備、任何類型的客戶端設備或其組合。
用戶可以在客戶設備(104)的監視器上顯示的搜索查詢域中輸入搜索查詢。基于搜索查詢術語,查詢計劃生成器生成多個查詢計劃,多個查詢計劃可用于搜索數據庫(100)以從數據庫的內容中找到適當的搜索結果。查詢計劃優化器選擇查詢計劃優化器確定將用最短的時間搜索數據庫內容的多個查詢計劃中的一個。查詢計劃優化器至少部分地基于存儲在數據庫(100)中和描述數據庫內容的統計做出決定以選擇查詢計劃。例如,數據庫(100)可存儲直方圖、行計數、唯一條目計數、其它統計或其組合,以描述數據庫(100)中的列信息。此統計使查詢計劃優化器免于重新計算關于列中的數據的摘要信息。
在數據庫的數據存在很小的變換時,關于數據庫列的統計可基于樣本被估計,以避免數據可使用大量的資源來更新大量的統計。數據庫(100)包括更新系統(106),更新系統(106)在適當的時候更新描述數據庫列的至少之一的統計的至少之一。更新統計的適當時間是在統計分布具有統計改變時。
更新系統(106)可隨時間的變化讓數據的樣本進入數據庫的列,并且將樣本相互比較。如果樣本展現大的統計差異,則更新系統(106)可確定更新統計是適當的,而不是基于樣本估計統計。進一步,更新系統(106)還可確定用于總結樣本之間的大的統計差異的置信度的水平。預定的置信度閾值可包括95%置信度或在更新系統將使統計之一更新前被超越的一些其他置信度水平。
雖然此示例已經參照數據庫、查詢計劃生成器、查詢計劃優化器、更新系統以及其它部件的具體位置進行了描述,但是這些部件可以位于根據本文描述的原理的任何適當的位置。例如,更細系統可以位于網絡部件而不是數據庫上,或位于客戶設備上。另外,查詢計劃生成器和查詢計劃優化器也可以位于網絡部件而不是數據庫上,或位于客戶設備上。
圖2是根據本文描述的原理的數據庫列(202)的樣本(200)的示例的示意圖。在此示例中,數據庫列(202)存儲信息的多個行(204)。數據庫可包括額外的信息列。數據庫列的行(204)可包括任何適當數量的行。在某些示例中,數據庫列(202)可包括從僅幾行到數億行。
數據庫還包括與行關聯的統計,例如行的數量、唯一條目技術、其他統計或其組合。這些統計可以與查詢計劃優化器一起使用,該查詢計劃優化器選擇將占用最短時間來執行的查詢計劃。
通過計算唯一條目計數、一系列列值上的不相交區間的行計數的值對的更新統計表來執行直方圖收集。更新統計表是耗時操作,并且使用來自數據庫的存儲器、中央處理單元和輸入/輸出的大量資源,因為其使用“分組依據”(“group-by”)操作以及“分類”(“sort”)操作以計算列的唯一條目計數。數據庫管理系統利用抽樣以便減少該操作的成本。相應地,這減少了輸入的大小并且改善了相應時間。
更新系統在第一天從數據庫列取出行的樣本(200)。樣本(200)可以是來自數據庫列(202)的行的隨機樣本。取出樣本(200)可包括將選中行的值拷貝到同一列中。在某些示例中,樣本包括來自數據庫列(202)的所有行的至少1%。例如,如果數據庫列具有成百萬行,則樣本表將包括至少上萬行,該至少上萬行包含從數據庫列(202)的選中行拷貝的值。在一些示例中,樣本包括數據庫列的 行的多于1%。
更新系統可基于樣本(200)計算描述數據庫列的至少一些統計。例如,更新系統可基于樣本估計唯一條目計數統計。
雖然此示例已經參照數據庫列中行的具體數量和樣本的大小進行了描述,但是可根據本文描述的原理使用任何適當數量的行和樣本大小。進一步,更新系統可取出多個數據庫列的樣本并基于它們相應的樣本估計抽樣的數據庫列的每一個的統計。
圖3是根據本文描述的原理的唯一條目計數估計器(300)的示例的示意圖。在此示例中,更新系統的唯一條目計數估計器(300)基于樣本(200,圖2)估計唯一條目計數。唯一條目計數表示樣本(200,圖2)中的唯一值。例如,樣本(200,圖2)中的三行包括值11。因此,11構成一個唯一條目計數。一行包括值342。因此,342構成一個唯一條目計數。兩行包括值654。因此,654構成一個唯一條目計數。進一步,一行包括值56。因此,56構成一個唯一條目計數。結果,在圖3的示例中,唯一條目計數值是4。
圖4A是根據本文描述的原理的布隆(bloom)過濾器(400)的示例的示意圖。在此示例中,布隆過濾器(400)是包括表示樣本(200,圖2)的行的寄存器位圖(402)的數據結構。寄存器中的每一個表示來自樣本值的二進制值。如果在樣本的行中存在大于0的值,則相應的布隆過濾器寄存器將存儲值1。另一方面,如果樣本行具有0值,那么相應的布隆過濾器寄存器將存儲0。除了位圖(402),布隆過濾器還包括表示來自樣本的唯一條目計數的計數器(404)。例如,樣本包括具有唯一值11的三個條目計數。因此,計數器之一保持值3。另外,樣本包括654的兩個條目計數,因此,另一個計數器保持值2。進一步,樣本還包括一個唯一值342和56,因此,其他兩個計數器(404)值1以表示這些唯一條目計數。布隆過濾器的計數器(404)表示樣本的數據分布。
圖4B是根據本文描述的原理的直方圖(450)的示例的示意圖。在此示例中,直方圖(405)也表示樣本的數據分布。樣本的數據本分成值范圍。第一值范圍(451)覆蓋從0到50,第二值范圍(452)覆蓋從大于50到300,第三值范圍(453)覆蓋從大于300到100。每個值范圍(451、452、453)的第一列(454)表示樣本中的總行數,其包括適當的值范圍內的值。每個值范圍(451、452、453)的第二列(455)表示適當的值范圍內的那些行的唯一條目計數。在此示例中,更新系統基于直方圖的分布,參考直方圖(450)以確定數據庫列的分布。直方圖的分布表示樣本的分布。
圖5是根據本文描述的原理的來自數據庫列(504)的樣本(502)的刪除行(500)的示例的示意圖。在此示例中,隨時間的流逝抽樣第一樣本。例如,第一樣本可以在第一天采集,并且可在一小時、幾個小時、一天、幾天、一周、、其他時間段或其組合之后分析第一樣本的改變。在時間流逝期間,當數據庫列(504)中的行(500)被刪除或額外行被插入時,數據庫列(504)經歷改變。這種改變可在更新過程在數據庫列(504)上執行時發生。另外,這種改變可在用戶人工插入或刪除數據庫列中的行(500)時產生。被刪除的圖5的示例中的每一行被用箭頭(506)標記。數據庫列(504)的行(508)被用插入行替代,所以,因為第一樣本(502)被采集,盡管行(508)被刪除,但行(508)出現改變的值。
對應于數據庫列(504)的刪除的行的已經包括在樣本(502)中的行的每一個被從樣本(502)刪除。在此示例中,樣本(502)的行(512、514、516)被從樣本(502)中刪除以反映數據庫列(504)中的改變。
圖6是根據本文描述的原理的添加插入(600)到的數據庫列(604)的樣本(602)的示例的示意圖。在此示例中,僅采集數據庫列(604)刪除的行的隨機樣本。行的值在樣本表中表示。在此示例中,樣本(602)包括三行,其中三行中的兩行具有大于0的值。具有大于0的值的行的每一個被插入到之前被修改以反映數據庫列(604)的刪除行的樣本中。在此示例中,僅樣本行(606)被插入到樣本中。隨著樣本現在反映從樣本原始采集到刪除和插入的發生,因此樣本現在分類為第二樣本(608)。
圖7是根據本文描述的原理的布隆過濾器(700)的示例的示意圖。在此示例中,在來自第二樣本(608,圖6)的行計數的值大于0時,布隆過濾器(700)的位圖(702)的寄存器保持“1”。因為樣本中的行中的一個被刪除,因此其對應的寄存器保持“0”值。計數器(704)也表示第二樣本(608,圖6)中發現的唯一條目計數。
更新系統比較布隆過濾器的分布以確定分布差異的存在。例如,更新系統可比較來自表示第二樣本(608,圖6)的布隆過濾器(700,圖7)的計數器的唯一條目計數的分布與表示第一樣本(200,圖2)的布隆過濾器(400,圖4A)的計數器的唯一條目計數的分布。此處,分布是不同的,因為布隆過濾器(400,圖4A)有不同的唯一條目計數。響應于發現分布差異,例如唯一條目計數的改變,更新系統確定對第一樣本(200,圖2)估計的統計被更新。在其他示例中,布隆過濾器的比較未產生統計分布變化,則更新系統確定基于樣本繼續估計統計。在某些示例中,更新系統使用來自布隆過濾器的位圖的行計數來確定是否發生分布改變。
圖8是根據本文描述的原理的直方圖(800)的示例的示意圖。在此示例中,直方圖(800)表示更新的樣本的分布。更新系統比較圖4B(450,圖4B)中的直方圖的分布與圖8中直方圖(800)的分布。更新系統可比較唯一計數條目分布、行計數的分布、每直方圖區間的各頻率的頻率、整個直方圖統計、直方圖中描述的其他統計或其組合。如果選擇的統計的分布中存在變化,更新系統確定更新數據庫列的統計。
雖然上面已經參照使用布隆過濾器來確定第一樣本和第二樣本之間的分布變化描述了各示例,但是可使用任何適當的機制來確定分布變化。例如,概要表可用于替代布隆過濾器或與布隆過濾器組合來確定樣本之間的分布變化。在某些示例中,其他機制用于替代概要表和布隆過濾器或與概要表和布隆過濾器組合。另外,雖然上面已經參照不同的樣本大小、刪除行的具體數量以及插入行的具體數量描述了各示例,但是可根據本文描述的原理使用其他任何適當的樣本大小、刪除行的數量或插入行的數量。
圖9是根據本文描述的原理用于增量式地更新數據庫統計的方法的示例的示意圖。在此示例中,方法(900)包括對數據庫中的數據庫列的行進行采樣(902)以生成第一樣本,在生成第一樣本后,對數據庫的修改的行的子集進行采樣(904)以生成第二樣本,基于第一樣本和第二樣本確定(906)數據庫列是否發生分布變化,以及響應于確定存在分布變化而更新關于數據庫列的數據庫統計。修改的行可包括刪除的行、插入的行、更新的行或其組合。更新可被表示為其后伴隨新的值的插入的舊的值的刪除。
該方法可包括具有總體表T,其中表T是數據庫列。樣本表S表示樣本,其中S滿足條件基數|S|可以是至少min(1,000,000,|T|的1%)。在第一天,表T被表示為T1且在第一天樣本表被表示為S1。唯一條目計數被用S1估計。在第二天,T1被更新產生表T2,其中T2=T1-d1+i1,其中d1表示總體中的刪除且i1表示總體中的插入。相應地,S2=S1-ds1+is1,其中ds1表示樣本表中的刪除且is1表示樣本表中的插入。在第i天,樣本表被由Si=Si-1-dsi+isi,i=2,3,…,n,給定。因此,Si反映第i天數據的分布。
在第一天,更新系統建立表S1,且基于表S1估計唯一條目計數。進一步,更新系統為S1(每列一個布隆過濾器)的行建立計數布隆過濾器。針對具有高頻率的值,計數器可溢出。此外,更新系統可為這些值保持獨立的概要表。更新系統在計數布隆過濾器和概要表上存留S1。
在第二天,更新系統從S1刪除行。這些行被表示為ds1。更新系統還從表T 采集行的隨機樣本。該隨機樣本是is1,其被添加到S1以生成S2。隨機樣本由T1中避免刪除的樣本的觀察數據和插入的觀察數據的樣本組成。在第(i-1)天和第i天之間發生的插入的數量可通過更新系統跟蹤和存儲。因此,來自表T1的隨機樣本提供對插入的訪問。如果更新系統跟蹤更新之間的插入部分,則插入樣本可被按剩余的數據分布的比例繪制。
此外,在第二天,針對ds1的每一行,更新系統減去布隆過濾器和概要表中的相應的計數器至較低的值。同樣地,針對is1的每一行,更新系統增加布隆過濾器和概要表中的相應的計數器至較高的值。計數布隆過濾器為頻率提供新的值并且概要表提供斜交元件的新列表。更新系統還在計數布隆過濾器和概要表上存留S2。
更新系統提出假設的推理測試,以增量式地更新第i天的唯一條目計數。零假設為未改變偏斜統計。如果零假設被拒絕,使得第i-1天和第i天之間斜交中存在改變,那么更新統計確定從數據庫列重新更新統計。另一方面,如果零假設不被拒絕,其建議數據分布未改變,則更新系統基于增量數據集(其是來自超級集的樣本)更新唯一條目計數。更確切地,使{x11,x12,…,x1n}是從Si-1的列X得到的隨機樣本,并且{x21,x22,…,x2n}是從Si的列X得到的隨機樣本。基于隨機樣本,更新系統測試來自兩個隨機樣本的偏斜度的差異。如果偏斜度中不存在95%的置信度水平的統計差異,則即便一系列的刪除和插入,數據分布也將保持不變。在該示例中,更新系統基于從Si-1到Si的增量數據(第i-1天和第i天之間的變化)來增量式地估計唯一條目計數。第i-1天的增量數據不是Si,但樣本從超級集(Ti,2)產生。
增量式地更新統計可包括多個條件。如果行計數與唯一條目計數的比例在增量樣本中的更新循環上保持不變,那么唯一條目計數可線性地伸縮以找到Si中的唯一條目計數。進一步,如果存在從Si-1到Si的偏斜度的變化,那么更新系統可在樣本Si上啟動具有線性加權組合估計器的唯一條目數。另外,如果增量樣本非常大,即比|T|的0.1%大很多,則可根據本文描述的原理使用布隆過濾器實現方式。
在某些示例中,可將列X的值分為多個直方圖的區間,并且該可用于增量式地估計唯一條目數計數的方案可應用于單個區間。例如,直方圖區間可以包括200個區間,所以估計器僅與樣本大小的1/200一起工作。可以通過統計測試確定置信度水平。可以使用直方圖、布隆過濾器、另一機制或其組合執行測試。可以使用行計數、唯一條目計數、其他統計數據或其組合確定置信度水平。統計測試可以包括參數測試、非參數測試、其他類型的測試或其組合。
比較包括在更新(插入和刪除)前的時間段(t-1)采樣,以及在更新后的時間 段(t)采樣。考慮到在連續的兩個時間段中的隨機樣本Si-1和andSi,使得fi-1和fi表示如下定義的頻率:正好出現了“i”次的觀測數據(可為認為是“類”)的跟蹤的頻率的量。唯一條目計數計算與頻率(f)的分布相關。量的變化引起分布中出現偏斜度。置信引擎估計偏斜度變化程度,以確定是否批準重新計算唯一條目計數。在置信引擎的實現方式中,做出了下列假設:1)在時段ti-1,ti,中發生刪除和插入;2)采樣的數據為高斯分布;3)提取獨立的樣本。
針對參數的測試,使x11,x21,....,xn1是來自大小為n的正態分布的隨機樣本,并且是來自大小為m的正態分布的隨機樣本,其中和是未知的,來自時段tt-1,tt。還假設樣本是獨立的。
提出假設H0:μ1=μ2versusH1:μ1≠μ2。測試可被修改以測試是否H0:μ1-μ2=0versusH1:μ1-μ2≠0。由于總體方差是未知的,我們可以通過他們的樣本替換他們估計和可以使用下列公式計算樣本方差:
s12=1n-1Σi=1n(xi1-x‾1)2ands22=1mΣi=1m(x2i-x‾2)2]]>
用于測試假設的邏輯統計為由給定的統計平均值之差。平均值之差的方差是:
var(x‾1-x‾2)=var(x‾1)+var(x‾2)=σ12n+σ22m.]]>
假設總體方差是相向等,即樣本方差被合并以產生對總體方差的綜合估計。var(x‾1-x‾2)=var(x‾1)+var(x‾2)=σ12n+σ22m=σ2(1n+1m).]]>方差σ2通過綜合樣本方差估計:
Spooled2==(n-1)S12+(m-1)S22n+m-2]]>
測試統計被給出為:
t=(x‾1-x‾2)-(μ1-μ2)spooled2(1n+1m)~tn+m-2]]>
兩個樣本的t–測試適用于小樣本大小。在總體方差與相等時,可使用t-統計是適當的。該假設的驗證涉及執行方差齊性檢驗測試。如果兩個總體的方差是不相等的,則修改t–測試。該測試也被公認為貝倫斯-費舍爾(Behrens-Fisher)測試。t–測試對于比較獨立的樣本也是有效的。
成對的t–測試是用于比較兩個不同時間分布變化的統計測試,假設樣本在這兩個時段相關。測試典型地包括獲采樣本變化之前和之后時段對象上的測量結果。假設可以被表達為H0:μb=μaversusH1:μb≠μa。在一些示例中,測試可以被重寫為H0:μD=0versusH1:μD≠0,其中μD=μb-μa。用于測試假設的測試統計是:
tD=x‾D-μDsD/n=x‾DsD/n]]>
其中并且sD是之前的統計平均值和之后的統計平均值之間的差值的標準偏差。由于之前和之后的平均值是相關的,因此var(x‾D)=var(x‾b-x‾a)=var(x‾b)+var(x‾a)-2cov(x‾b,x‾a).]]>
兩個正相關的隨機變量的差的方差小于兩個獨立的隨機變量的差的方差,并且類似的,如果隨機變量是負相關的,那么差的方差將趨向于更大。因此成對差的t-統計調整測量結果之間的相關性。為了確定與頻率相關的樣本之間的統計顯著性,將計算的t-統計數據的絕對值與tn-1,α/2給出的理論t-分布的百分點相比較。如果t≤-tα/2或者t≥tα/2,則指示兩面測試的變化存在巨大的差異。對于單面測試,可適當的調整否定區域以得出相關推論。
可替代地,不依賴于采樣數據的正常假設的非參數測試可被稱為柯爾莫哥洛夫-斯米爾諾夫測試(Kolmogorov-Smirnov,K-S測試),其用來確定兩個數據集是否存在顯著差異。KS測試具有關于數據分布不用進行假設的優點。兩個樣本的KS測試是非參數假設測試,其可用來估計在每個數據集的數據范圍內兩個樣本數據向量Si-1和Si分布的累積分布函數(CDF)的差異。其中數據是數據集的元組。
兩面測試使用了兩個數據向量分布的CDF之間的最大絕對差值。其中測試統計為
D*=maxx(|F1(x)-F2(x)|),]]>
其中為x1值小于或等于x的比例。為x2值小于或等于x(分布中的一 個元組)的比例。測試統計數據D*用于計算樣本Si-1和Si差異顯著性的置信度水平。上面描述的這些測試可以被很容易的應用到考慮中的直方圖區間的行計數(RC)。
雖然已經參照具體測試對確定置信度水平進行了描述,但是根據本文描述的原理,可以使用任何適當的測試。進一步的,雖然已經參照使用具體的統計對確定置信度水平進行了描述,但是可以使用任何適當的統計。
圖10是根據本文描述的原理的更新系統(1000)的示例的示意圖。更新系統(1000)包括采樣引擎(1002)、確定引擎(1004)以及更新引擎(1006)。在此示例中,所述更新系統(1000)進一步包括置信度引擎(1008)、布隆過濾器引擎(1010),減量引擎(1012)以及增量引擎(1014)。引擎(1002、1004、1006、1008、1010、1012、1014)指的是執行指定功能的硬件和程序指令組合。每個引擎(1002、1004、1006、1008、1010、1012、1014)可以包括處理器和內存。所述程序指令存儲在存儲器中,并且使處理器執行引擎的指定功能。
采樣引擎(1002)對數據庫列進行采樣,或者對數據庫列的一部分進行采樣,以生成樣本。所述確定引擎(1004)確定在不同的時間采樣的樣本之間是否發生了統計分布變化。如果確定引擎(1004)確定存在分布變化,則更新引擎(1006)更新關于數據庫列的至少一個統計,例如唯一條目計數。否則,所述更新系統(1000)將基于最新的樣本估計統計數據。
更新系統具有分布變化存在的確定,置信度引擎(1008)確定置信度水平。只有在置信度水平高于預定閾值時的情況下,例如95%的置信度水平,更新引擎(1006)才可更新統計。
布隆過濾器引擎(1010)基于最初的樣本建立布隆過濾器并且填充布隆過濾器的寄存器。減量引擎(1012)減去布隆過濾器的計數器,以反映數據庫列的刪除的行。增量引擎(1014)增加對應于樣本中的插入的行的計數器。
圖11是根據本文描述的原理的更新系統(1100)的示例的示意圖。在此示例中,所述更新系統(1100)包括與存儲器資源(1104)通信的處理資源(1102)。處理資源(1102)包括至少一個處理器,以及用于處理程序化指令的其他資源。存儲器資源(1104)通常表示能夠存儲數據(例如更新系統(1100)使用的程序化指令或數據結構)的任何存儲器。存儲在存儲器資源(1104)中示出的程序化指令包括列采樣器(1106)、唯一條目計數估計器(1108)、布隆過濾器生成器(1110)、布隆過濾器填充器(1112)、刪除行確定器(1114)、修改的行采樣器(1116)、插入跟蹤器(1118)、布隆過濾器減量器(1120)、布隆過濾器增 量器(1122)、偏斜度比較器(1124)、唯一條目計數更新器(1126)以及搜索查詢計劃優化器(1128)。
存儲器資源(1104)包括計算機可讀存儲介質,計算機可讀存儲介質包含使任務由處理資源(1102)執行的計算機可讀程序代碼。計算機可讀存儲介質可以是有形的和/或非瞬態的存儲介質。計算機可讀存儲介質可以是非傳輸存儲介質的任何適當的存儲介質。計算機可讀存儲介質類型的非窮盡列表包括:非易失性存儲器、易失性存儲器、隨機存取存儲器、基于憶阻器的存儲器、只寫存儲器、快閃存儲器、電可擦除可編程只讀存儲器、磁存儲介質、其它類型的存儲器或其組合。
列采樣器(1106)表示程序化指令,在執行時,使處理資源(1102)對數據庫的列進行采樣。唯一條目計數估計器(1108)表示程序化指令,在執行時,使處理資源(1102)基于用列采樣器(1106)提取的樣本估計唯一條目計數。
布隆過濾器生成器(1110)表示程序化指令,在執行時,使處理資源(1102)建立布隆過濾器。布隆過濾器填充器(1112)表示程序化指令,在執行時,使處理資源(1102)基于樣本的總數,填充布隆過濾器的寄存器。刪除行確定器(1114)表示程序化指令,在執行時,使處理資源(1102)確定反映在樣本中的從數據庫列中刪除的行的數量。修改行采樣器(1116)表示程序化指令,在執行時,使處理資源(1102)對數據庫列中修改的行進行采樣。修改的行可包括刪除的行,插入的行,更新的行或其組合。插入跟蹤器(1118)表示程序化指令,在執行時,使處理資源(1102)跟蹤數據庫列中的插入。
布隆過濾器減量器(1120)表示程序化指令,在執行時,使處理資源(1102)減去與樣本中刪除的行對應的布隆過濾器的計數器。布隆過濾器增量器(1122)表示程序化指令,在執行時,使處理資源(1102)增加與樣本中插入的行對應的布隆過濾器的計數器。
偏斜度比較(1124)表示程序化指令,在執行時,使處理資源(1102)比較不同樣本之間的分布的偏斜度。唯一條目計數更新器(1126)表示程序化指令,在執行時,如果偏斜度比較(1124)基于布隆過濾器和/或直方圖的唯一計數確定樣本中存在統計分布變化,則使處理資源(1102)從數據庫列更新唯一條目計數。否則,估計唯一條目數(1108)會基于樣本繼續估計所述唯一條目數。搜索查詢計劃優化器(1128)表示程序化指令,在執行時,使處理資源(1102)基于最新的唯一條目計數選擇查詢計劃。
進一步,存儲器資源(1104)可以是安裝包的一部分。響應于安裝該安裝包, 存儲器資源(1104)的程序化指令可以從安裝包的源下載,例如便攜式介質、服務器、遠程網絡位置、其它位置或其組合。兼容本發明描述的原理的便攜式存儲介質包括DVD、CD、閃存、便攜式磁盤、磁盤、光盤、其它形式的便攜式存儲器或其組合。在其它例子中,程序指令已被安裝。此處,存儲器資源可以包括集成的存儲器,例如硬盤驅動器、固態硬盤驅動器等等。
在一些例子中,所述處理資源(1102)和存儲器資源(1104)可以位于同一的物理不見,例如服務器或網絡部件。存儲器資源(1104)可以是物理部件的主存儲器、高速緩存、寄存器、非易失性存儲器或物理部件的存儲器結構的其他部分。可替代地,存儲器資源(1104)可以通過網絡與處理資源(1102)通信。進一步,當程序化指令位于本地時,數據結構,例如庫且可以通過網絡連接從遠程位置訪問。因此,更新系統(1100)可以在用戶設備、服務器、服務器集合或其組合上實現。
圖11的更新系統(1100)可以是通用計算機的一部分。然而,在可替代的示例中,更新系統(1100)可以是專用集成電路的一部分。
圖12是根據本文描述的原理的增量式地更新數據庫統計的過程的流程圖(1200)的示例的示意圖。在此示例中,過程包括:在第一天,對數據庫列進行采樣(1202)以生成第一樣本,并且基于第一樣本估計(1204)唯一條目計數。過程還包括基于第一樣本填充(1206)布隆過濾器計數器且記錄布隆過濾器計數器中的唯一條目計數。過程進一步包括:修改(1208)行,例如刪除、插入或更新行,在第二天,自第一樣本生成后,在從數據庫列刪除的第一樣本中,在第二天對數據庫列的修改的行采樣(1210),以定位修改行中的插入。由于樣本中的刪除行,與較低頻率對應的布隆過濾器中的計數器被減去(1212)。同樣地,由插入行引起的與增加的頻率對應的計數器被增加(1214)到較高的值。
過程還包括確定(1216)表示不同樣本的布隆過濾器之間是否存在統計分布變化。如果確定不存在分布變化,則過程估計(1218)樣本上的列的唯一條目計數。另一方面,如果確定存在分布變化,則過程完全更新(1220)數據庫列中的唯一條目計數。
雖然上面已經參照生成第一樣本和生成第二樣本之間的具體時間期間描述了各示例,但根據本文描述的原理可使用任何適當的期間。進一步,雖然上面已經參照用于確定分布變化的具體機制描述了各示例,但根據本文描述的原理可使用使用用于確定分布變化的任何適當機制。
雖然已經參照具體的直方圖描述了該示例,但根據本文描述的原理可使用任 何適當類型的直方圖。進一步,雖然已經參照具體的布隆過濾器描述了該示例,但根據本文描述的原理可使用任何適當類型的布隆過濾器。另外,雖然上面已經參照具體的統計描述了各示例,但根據本文描述的原理可使用任何適當類型的統計。
已經提供前面的描述僅用于說明和描述描述的原理的示例。該描述目的不在于窮舉或將這些原理限制到公開的任何精確的形式。根據上述教導,許多修改和變形是可能的。

關 鍵 詞:
增量 更新 統計
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:增量式地更新統計.pdf
鏈接地址:http://www.rgyfuv.icu/p-6409741.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图