用於以存儲高效的方式存儲表格數據的方法和系統的製作方法

2023-06-05 01:00:41 2

用於以存儲高效的方式存儲表格數據的方法和系統的製作方法
【專利摘要】用於以存儲高效的方式存儲表格數據的方法和系統被公開。本發明涉及在面向列的存儲系統中在具有列（C）和行（R）的表格數據結構（10）中存儲數據的方法，包括：a.將列（C）中的至少一個劃分為多個段（S），其中每個段（S）具有相關聯的單元尺寸，該單元尺寸指示相應段（S）中的數據項的最大尺寸；b.當將數據項存儲到所述段（S）中的一個中時，-判定該數據項的尺寸是否超過該段（S）的單元尺寸；並且-如果該數據項的尺寸超過該段（S）的單元尺寸，則適應性改變（120）該段（S）的單元尺寸以適應該數據項的尺寸；c.其中適應性改變（120）該段（S）的單元尺寸以適應該數據項的尺寸是獨立於所述多個段（S）中的其他段的單元尺寸而執行的。
【專利說明】用於以存儲高效的方式存儲表格數據的方法和系統
【技術領域】
[0001]本發明涉及用於在表格數據結構中存儲數據的方法和系統。
【背景技術】
[0002]現代計算機系統經常對表格數據進行操作，表格數據即構造為二維表格的數據，其中每個數據項(也稱為「單元」)可以通過其列和行號來尋址。支持這種表格數據結構的系統的流行示例是資料庫系統，例如關係資料庫系統。表格數據存儲方式底層的理論概念追溯到1970年代已經是科學研究的主題(對於概述，例如見G.Copeland等人的「A decomposition storage model」,關於數據管理的1985ACM SIGMOD國際會議會刊(SIGMOD 『85).ACM，紐約，NY, USA, 268-270 )?
[0003]因此，在概念層面上，表格數據可被理解為二維表格。然而，當存儲這種數據時，二維數據必須被串行化為一維比特序列以被存儲在底層計算機硬體的工作存儲器(例如RAM)和/或永久存儲裝置(例如硬碟驅動器)中。為此，多數傳統資料庫管理系統(DBMS)遵循所謂的面向行的方式，即二維表格被逐行存儲。另一種方式被所謂的面向列的DBMS遵循，其將其數據表格存儲為連串的列。兩種方式具有其單獨的優點和缺點，例如當需要在許多行上但是僅針對所有數據列的顯著更小的子集計算聚合時面向列的系統更加高效，這是因為讀取該更小數據子集可以比讀取全部數據更快。另一方面，當同時需要單個行中的許多列時以及當行尺寸相對小 時面向行的系統更加高效，這是因為整個行可以利用單次磁碟尋道取回。不管所使用的存儲策略，允許快速隨機訪問讀的物理存儲可以極大地提高操作速度。隨機訪問允許在必須讀取僅很少欄位和很少行的情況下進行查詢的情況下使讀取數據的數量最小化。其實現此是因為僅必須從存儲傳輸感興趣的單獨單元。如果一種類型的全部單元具有相同尺寸則尋找那些單獨單元是最容易並且最快的，這是因為然後可以通過簡單乘法來計算單元的地址。
[0004]影響這兩種方式的另一障礙在於表格中的數據極少是靜態的，這是因為新的行被頻繁地添加、刪除並且單元值可被改變。例如，如果一單元被添加到一列並且該單元不符合該列中每單元可用的比特數目，則該列的底層數據結構必須被適應性改變。尤其是在面向行的存儲模型中，改變列寬度(即每單元可用的比特數目)的成本可能是過高的，這是因為全部行必須被重新編碼，實際導致整個表被變換。
[0005]在面向列的存儲模型中，用於使數據結構適應性改變的簡單策略是使受影響的列的每個單元的比特數目增加。然而該策略具有兩個缺點，這兩個缺點如果列大則變得特別相關。首先，具有舊單元容量的舊結構的所有單元需要被轉換為具有增加單元容量的新結構。其次，只要該轉換在運行，則為舊和新數據結構一起分配的存儲器數量多於舊結構自己的兩倍。這在一方面意味著系統在轉換操作之外必須提供比實際所需多得多的存儲器。其次，對於操作環境現今通常提供的自動存儲器管理系統有額外的努力。
[0006]自動存儲器管理系統上的負荷在諸如嵌入式系統或者智慧型電話之類在計算能力和/或存儲器訪問速度方面具有極有限資源的設備中尤其成問題。在範圍的另一端，使用許多吉字節工作存儲器的大型伺服器級機器上的應用也遭遇由自動存儲器管理上的高負荷引起的問題以及由此帶來的計算能力和響應的損失。
[0007]總之，用於頻繁改變的表格數據的傳統壓縮面向列的存儲系統遭受以下缺點:用於轉換一列數據的增加的處理時間，以及臨時加倍的存儲器消耗(以及自動存儲器管理上的與之相關的負荷)。
[0008]因此本發明底下的技術問題是提供在存儲器和處理能力消耗方面更加資源高效的用於存儲表格數據的改進的方法和系統，由此至少部分地克服現有技術的上述缺點。

【發明內容】

[0009]該問題根據本發明的一個方面由一種在面向列的存儲系統(例如資料庫、資料庫管理系統(即包括資料庫和用於訪問該資料庫的處理邏輯的系統)，或者任何其他可操作來存儲表格數據的存儲系統，即一般指「表格存儲裝置」)中在具有列和行的表格數據結構中存儲數據的方法解決。在權利要求1的實施例中，該方法包括以下步驟:
[0010]a.將列中的至少一個劃分為多個段，其中每個段具有相關聯的單元尺寸，該單元尺寸指示相應段中的數據項的最大尺寸；
[0011]b.當將數據項存儲到所述段中的一個中時，
[0012]-判定該數據項的尺寸是否超過該段的單元尺寸；並且
[0013]-如果該數據項的尺寸超過該段的單元尺寸，則適應性改變該段的單元尺寸以適應該數據項的尺寸；
[0014]c.其中適應性改變該段的單元尺寸以適應該數據項的尺寸是獨立於所述多個段中的其他段的單元尺寸而執行的。
[0015]因此，該實施例基於將表格的一個或多個列分割為稱為段的更小子單元的一般概念。段中的每個數據項具有由該段的單元尺寸指示的相同尺寸(例如，為存儲數據項而分配的比特數目)，但是不同的段可具有不同的單元尺寸。這樣，可以具有例如具有兩個段的列，其中第一段存儲僅具有128個比特的數據項，而第二段存儲具有256個比特的數據項。可見，當一超過一表格段的最大單元尺寸的新數據項被添加到該表格段時，該方式具有相當大的優勢。這是因為在這種情況下，僅受影響的段的單元尺寸需要被適應性改變(在這種情況下:被增加)以適應新數據項的尺寸，而其他段無需被適應性改變。這在性能(因為僅列的子集即受影響的段需要被適應性改變)和存儲器消耗(因為段可被選擇為僅需要最小量的存儲容量)方面都是有益的。總之，將列分割為多個子單元(段)允許更細粒度的存儲器優化。應當注意到，因為優選當新數據項將被存儲到表格中時執行對受影響段的單元尺寸的適應性改變，因此上述方式尤其靈活、動態並且自尋最優。然而，在每個段級別上適應性改變單元尺寸的一般概念在可替代實施例中還可以獨立於用於存儲新數據項的特定請求而被例如周期性地(例如作為背景進程)或者被管理員手動地使用。
[0016]在本發明的另一方面，每個段具有指示相應段中的數據項的最大數目的相關段尺寸(當然，段尺寸在列之間可以不同)。優選地，一列的所有段具有相同的段尺寸。因此，不僅段內的單獨數據項的尺寸可被上邊界(上述單元尺寸)限制，每個段所允許的數據項的數目也被(通過段尺寸)限制。選擇最佳的段尺寸可導致相當大的性能和存儲器使用提高，如下面將會更加詳細說明的。另外，如果給定列的所有段具有相同段尺寸，則單獨數據項的地址計算尤其快速和高效。
[0017]另外，該方法可包括基於底層硬體系統的特性，例如工作存儲器與處理器之間的帶寬，來確定最佳段尺寸的步驟。除此之外或者作為替代，確定最佳段尺寸的步驟可以基於關於表格數據結構中存儲的數據的統計和/或關於對表格數據結構的數據執行的添加、更新和/或移除操作的頻率的統計。另外，確定最佳段尺寸的步驟可被以如下方式執行:(a)當數據被添加、更新和/或移除時自動地(即，對最佳段尺寸的確定是自動(即自尋最優)並動態的)；(b)自動並周期性地(即自動和非動態的)，和/或(c)手動地。
[0018]因為權利要求1的實施例的方法在面向列的存儲系統中操作，因此表格數據結構的列優選被相繼地存儲在存儲系統的工作存儲器和/或永久存儲裝置中。因此，該方面遵循在上面的介紹部分中說明的面向列的方式(也稱為列式表格存儲)。該方面對於使表格數據的存儲器消耗最小化尤其有效，這是因為一個列的數據項(通常)具有相同的數據類型和類似的存儲器消耗。當然，其在一整個新列需要被添加到現有表格時也是有利的，這是因為在這種情況下該新列可被簡單地附加到串行化的一維數據結構。換言之，基於列對數據值分段尤其有利，這是因為一個特定列的值通常落入相同的值範圍並且因而各自具有類似的存儲器需求。行的單元反之通常具有非常不同的存儲器需求。將面向列的分段與面向列的存儲模型相結合尤其有利，這是因為如果面向行的存儲模型被使用，則改變單元尺寸將需要複製/移動段的所有單元而不僅僅是特定列的單元。應當注意到，雖然在面向列的方式中數據通常按照列來存儲，但是特定列不一定是連續的，這是因為如果其段中的一個已必須被適應性改變以應對單元尺寸的改變，則其可能不再位於其在存儲器中的原始位置。
[0019]另外，該方法可包括提供將數據項映射到整數值的字典數據結構以及將整數值而非數據項存儲在表格數據結構中的另外步驟。因此，代替實際的數據項(例如，具有值「Smith」的「文本」類型的數據項)，僅簡單整數值(例如「123」)被存儲在表格中和/或相應地存儲在串行化的存儲器表示中，這導致更少的存儲器消耗，這是因為數據被有效地壓縮。為了實現這種壓縮，將數據項映射到整數值(在「Smith」= 「123」的意義上)的字典然後被提供，使得數據可被解析。
[0020]優選地，適應性改變段的單元尺寸以適應數據項的尺寸包括選擇在相應列中存儲最大數據項所需的最小數目的比特。這樣，表格數據結構的存儲器表示可被保持地儘可能的小。
[0021]本發明還針對於包括用於實現上述方法中的任一種方法的指令的電腦程式。最後，一種用於在具有列和行的表格數據結構中存儲數據的面向列的存儲系統也被提供，其中該系統包括用於將列中的至少一個劃分為多個段的裝置，其中每個段具有相關聯的單元尺寸，該單元尺寸指示相應段中的數據項的最大尺寸；用於將數據項存儲到所述段中的一個、適用於判定該數據項的尺寸是否超過該段的單元尺寸，並且如果該數據項的尺寸超過該段的單元尺寸則適應性改變該段的單元尺寸以適應該數據項的尺寸的裝置；其中適應性改變該段的單元尺寸以適應該數據項的尺寸是獨立於所述多個段中的其他段的單元尺寸而執行的。
[0022]對本發明的系統的實施例的其他有利修改在其他從屬權利要求中被定義。將會認識到系統的這種實施例可被適應性改變為根據上述方法中的任一種來執行。【專利附圖】

【附圖說明】
[0023]在以下詳細描述中，本發明的當前優選實施例是參考以下附圖來描述的:
[0024]圖1:根據本發明實施例的具有被劃分為多個段的兩列的示例性表格數據結構；
[0025]圖2A:在添加新行之前的根據本發明實施例的示例性表格數據結構；
[0026]圖2B:在新行被添加之後的圖2A中的示例性表格數據結構；
[0027]圖3:圖示出根據本發明實施例的添加行的過程的流程圖；
[0028]圖4:圖示出根據本發明實施例的更新行的過程的流程圖；
[0029]圖5:圖示出根據本發明實施例的適應性改變段的單元尺寸的過程的流程圖；
[0030]圖6:根據現有技術的表格數據結構的示意性圖示。
【具體實施方式】
[0031]本發明總地涉及用於以特別存儲高效的方式在計算機系統的(有限)主存儲器中存儲表格數據的技術。如在多數資料庫系統或者其他表格存儲裝置中使用的表格數據結構在概念層次上可被理解為行和列的二維表格，其中單獨的數據單元被存儲。
[0032]圖6示出了這種表格數據結構的簡單示例，即存儲僱員及其薪酬的數據的表格。如在圖6中可見，該示例性表格包括四個列Cl，…，C4以及三個行R1，…，R3。然而將會認識到，本發明支持具有任意數目的列C和行R的表格數據結構。因此，表格數據可被理解為一表格數據結構,其中該表格的每個列可以具有不同的數據類型,而一個特定列內的每個單元的數據類型對於整個列而言是相同的。在上面的示例中，列C2 「姓」和C3 「名」的所有單元包括文本(例如數據類型為「String (字符串)」)，而列Cl "EmpId (僱員ID)」和C4 「薪酬」的單元包括數字(例如數據類型為「整數」)。
[0033]本發明的實施例允許在表格可能巨大的同時使計算機系統的有限存儲器能夠容納儘可能多的數據。本發明的實施例還允許通過在不完全重建表格的情況下通過添加行R來使表格增長。另外，本發明的實施例允許在不完全重建表格的情況下替換和/或刪除值。此外，全部列C可被容易地添加、替換和/或移除。所有這些問題被本發明的某些實施例通過使用具有被劃分為多個段S的可變字寬度的列C的表格表示並且通過智能在線算法管理該表格來解決。
[0034]在下面，本發明的優選實施例的三個特性被描述，即(a)列式表格存儲，(b)經由字典的壓縮以及(C)通過對最佳數據類型的選擇的壓縮。然而，本發明還包括僅具有這些特性的子集的實施例，以及沒有特性(a)_ (c)中的一個而是只有下面進一步說明的其他特性的其他實施例。例如，對表格數據結構的列進行分段的本發明概念在面向行的存儲系統中也將是一般可想到的。
[0035]列式表格存儲
[0036]如上面說明的，表格數據結構，例如圖6中的表格，在概念上是二維數據結構。然而，當這種數據結構被存儲到底層計算機系統的工作存儲器(例如RAM)和/或永久存儲裝置(例如硬碟驅動器)中時，存儲系統必須將該二維結構串行化為一維的一系列字節以供作業系統寫入到RAM、硬碟驅動器或者兩者。
[0037]為此,所謂的面向行的存儲系統將行R中的所有單元一起串行化，然後將下一行中的單元串行化，諸如此類。考慮到圖6中的示例性表格，這將產生以下:[0038]1，Smith, Joe, 40000; 2，Jones, Mary, 50000; 3，Johnson, Cathy, 44000;
[0039]另一方面，所謂的面向列的存儲系統將列C中的所有單元一起串行化，然後將下一列C中的單元串行化，諸如此類:
[0040]I, 2, 3;Smith, Jones, Johnson;Joe, Mary, Cathy;40000, 50000, 44000;
[0041]因此，在該策略中，列C被表示為單元的序列。列C的所有單元具有相同的數據類型。每個單元通過指定該單元的列C和行R編號來尋址。對於每個地址僅有最多一個單元。表格中的記錄(即行)的數據遍布於表格中的所有列C，但是在列C中的每一個中可以在相同的行號下找到。
[0042]列C可以具有多個不同數據類型之一，例如整數、浮點數、文本、時間戳等。在概念上，列C是列數據類型的單元序列，其中每個單元可以通過其行號來訪問。
[0043]如果列C中的所有單元具有均一尺寸，則行號是在單元序列中的位置。然後某一給定行R中的單元可被直接尋址，而無需對其進行搜索。
[0044]經由子典的壓縮
[0045]字典可被用來將單獨複雜值映射到更簡單的值上。在文本數據的情況下，這意味著每個獨特字符序列被映射到整數值上。該字典壓縮在值在列C中發生多次的情況下壓縮數據，因為反覆出現的文本在字典中僅被存儲一次。這是流行的DEFLATE壓縮算法的核心思想之一。
[0046]被應用於列式存儲(見上面)，這意味著僅整數值被存儲在列單元中。字典然後被用於在解釋查詢和彙編響應時從文本轉化為整數以及從整數轉化為文本。在本發明的實施例中，所有單元包含簡單整數這一事實減少了查詢處理時間，這是因為在表格中搜索值時無需文本解析。
[0047]通過選擇最佳數據類型的壓縮
[0048]一般而言，給定表格的存儲器消耗應當被最小化，使得其允許使存儲器能夠容納更多數據同時減少對存儲器總線和高速緩存的負荷，從而導致更高的查詢處理速度。因此使用儘可能少的比特來表示列C中的單獨整數是可取的。仍然，如果所有單元具有相同容量(即比特數目)並且地址計算是行號和單元容量的簡單相乘，則對單獨單元的隨機訪問是最快的。因此，單元容量優選對於所有單元是相同的，但是同時僅存儲當前在列C中的最大整數所需的最小數目的比特被使用。
[0049]列分段
[0050]通過將每個列C分割為多個段S，可以實現較之現有技術策略在存儲器消耗方面的相當大的改進。每個段S優選包含相同數目的單元，使得通過行號尋址的段S可被容易地計算。仍然，在不同的列C之間，每個段S的單元數目可以不同。
[0051]列C的所有段S共有相同的數據類型，但是每個段S具有其自己的單元容量(也稱作「單元尺寸」，即列內的單獨數據項/單元的容量/尺寸)。如果一個段S需要增長為更大的單元容量，則其可以這樣做而無需對其他一個或多個段S進行任何改變。各段S的單元容量然後可以不同。
[0052]圖1示出了包括兩個列C (標記為「持續時間」和「數量」)和12個行R (編號為「O」至「11」)的表格的簡單示例。可見，列Cl 「持續時間」被分割為跨越行O至5的第一段SI並被分割為跨越行6至11的第二段S2。列C2 「數量」被分割為分別跨越行O至3、4至7以及8至11的三個段S3-S5(即列Cl中的段具有段尺寸6，並且列C2中的段具有段尺寸4)。在圖1中可見，每個段S的單元可具有不同的尺寸，即段S可具有不同的單元容量(由段的不同寬度圖示出；注意到例如段S3具有比段S4更大的單元容量)。在一特定列C內，所有段具有相同的列尺寸(儘管可以想到本發明的替代實施例，其中一特定列內的段的段尺寸可以不同)。
[0053]如果新行R將被添加到表格，則其在任意空閒行號下被添加，並且針對每個列C檢查對應的列段S是否具有適合於存儲新單元值的單元容量。如果單元容量不足夠，則列段S被具有足夠容量的新列段S替換並且現有值被遷移到新列段S中。
[0054]可詵特徵:折衷
[0055]段尺寸(即段S中的單元的最大數目)可被用於調整當將數據遷移到新列中時所需的額外臨時存儲器的量。另外，如果段S被分配用於存儲許多單元，但是在給定時刻僅包含很少，則存儲器被浪費。由於這兩種原因，更小的段尺寸是優選的。然而，這兩個目的需要被彼此平衡。首先，如果段S極小並且眾多，則每個段S的存儲器開銷變得過高。其次，對連續數據的存儲器訪問通常更快。更長、中等尺寸的段S因而可能最終導致更快的查詢處理。
[0056]單元容量增長因素影響必須執行段遷移操作的頻率。其還影響浪費的存儲器的量，如果單元容量大於單元中存儲的值所需的話。當選擇單元容量時，因而存在在這兩個目標之間的折衷。
[0057]可詵特徵:自話應段尺寸設置(sizing)
[0058]為了使本發明針對所有數據星座接近最佳地工作，提議了朝著期望的折衷目標自動調整參數的機制。
[0059]一般而言,段尺寸應當適合執行環境的屬性。絕對最小段尺寸應當使得從主存儲器到處理器核心的帶寬被最大地利用。存儲器布置和高速緩存尺寸在這方面也起作用。測量可被用於為具體環境尋找良好段尺寸。
[0060]如果存在被認為對於某一執行環境而言「最佳」的尺寸，則其將被用數據字表達，而非用單元數目表達。為了具有按照字數目的最佳段尺寸，選擇在段S使用最佳單元尺寸的情況下產生每個段S的最佳字數目的(按照單元數目的)段尺寸可能是好主意。例如，如果按照字的最佳段尺寸是128並且多數單元具有兩個字的尺寸，則64個單元是最佳段尺寸。關於現有數據的統計可被用於預測新段S的良好參數。
[0061]如果數據被完全再導入，則再導入之前的列內容的統計可以在行R的預期總數方面為新段S的尺寸設置提供良好指導。還可以重用現有的段S，但是那麼無法執行對尺寸設置的優化。
[0062]除了段尺寸即每個段的最大單元數目之外，所分配的單元尺寸(即單元容量)還對存儲器消耗以及可能還對需要將段S變換為更大段尺寸的頻率有大影響。列值的現有單元的最小和最大值對於通過更新或添加而到來的新值而言經常是良好的預測器。因此，如果新段S被分配有足夠大的單元尺寸，則許多將段S變換為更大單元尺寸的變換可被避免。
[0063]更新和移除的頻率也可被用作指導。如果這些操作經常導致段S被變換為不同的單元尺寸，則段S很可能應當更小，因為這可以限制對單獨變換操作的努力。
[0064]本發明的方法的優詵實施例[0065]在下面，將通過對表格數據結構執行的若干操作來描述實現本發明的優選方式。
[0066]從行讀取數據
[0067]從行R讀取數據對於每個應當被讀取的列C需要:
[0068]1.將行號解碼為列C中的段號以及段S內的編號。
[0069]2.從段S讀取單元值。
[0070]3.如果列C具有相關字典(見上面)，則將單元值從簡單整數轉化為更加複雜的數據類型。
[0071]添加行
[0072]將新行R添加到表格數據結構的過程在圖3中被圖示出。該過程在步驟100(「尋找空閒行」)處開始。為了添加新行R，首先空閒行號必須被找到(例如最高現有行號加一)。然後，新的單元值需要被添加到所確定的行R中，每一個被添加到其相應的列C (參考步驟105)。讓我們假定單元值只是整數並且任何字典操作(見上面)已經發生。
[0073]為了將單元值添加到列C，行號必須被解碼為對應的段號以及段S內的單元號(參考步驟110)。當所有段S具有相同尺寸時，解碼是通過將行號除以段尺寸來實現的(讓第一個行號是零)。由此得到的商是段號並且餘數是段S內的單元號。
[0074]如果尚不存在具有給定段號的段S (因為行號對應於表格尺寸)，則新的段S被創建(參考步驟115)。新的段S必須具有與表格的相應列中的現有段S相同的長度(也稱作「段尺寸」)。其單元尺寸可按照如上面進一步說明地確定。當然，其至少應當如容納將被添加的新單元值所需一樣大。
[0075]在行R的段S已經存在的替代情況下，必須確保新單元值適合現有段的單元尺寸。如果不，則段單元尺寸必須被增長，即擴大(參考步驟120)，這在下面被進一步描述。
[0076]在任何情況下，段S然後準備好容納新值並且新值可被寫入適當的單元(參考步驟 125)。
[0077]如在圖3中示出，該過程針對表格的所有其他列C以相同方式迭代(參考步驟105)直到全部已被擴展有新值為止。
[0078]以上操作的一個示例在圖2A和2B中被示出，其中新的行「30; 1235」被添加到現有表格。這裡，新的行將被添加在所有已經存在的行之後。因為圖2A的表格已經包括行O至9，因此新的行被添加作為行號10。在該示例中，行號10落入兩個列的第二段。然而，在列「數量」中，第二段具有對新值「1235」而言過小的單元值(因為該段的尺寸當前被設置為容宿單元「87」、「24」、「12」和「7」)。因此，段單元尺寸在值可被添加之前被增長。結果在圖2B中被示出，圖2B圖示出列「數量」的第二段被增長(注意與圖2A相比更大的寬度)以容納新單元值「1235」。
[0079]增長段單元尺寸
[0080]增長/擴大段單元尺寸的過程(參考圖3中的步驟120)在圖5中被示出。類似於創建新段S的過程，新的單元尺寸必須被選擇(參考圖5中的步驟130)，其至少應當如新添加的單元值所需一樣大。此後，新的段S被分配(參考步驟135)並且舊的段S被逐單元複製到其中(參考步驟140)。最終，對舊的段S的引用被改變為指向新的段S(參考步驟145)並且分配給舊的段S的存儲器被釋放(參考步驟150)。
[0081]審新行[0082]在圖4中示出的更新現有單元值的過程類似於在圖3中示出的添加新的單元值的策略。
[0083]移除行
[0084]移除可以通過將移除的行R標記為「移除」或者通過將最後一行R複製到移除的行R的位置(其接下來可能需要段遷移)來實現。在前一情況下，步驟「尋找空閒行」(圖3中的步驟100)必須檢查表格以尋找被標記為移除的行，並且如果不存在，則返回最後一行R之後的行R的編號。在後一情況下，其可以在之前不檢查標記的情況下直接返回該編號。
[0085]術語表
[0086]單元:表格中值所位於的空間。單元可以通過指定其行和列號來尋址。
[0087]單元尺寸:數據單元可以保存的信息量，其還決定了其所佔據的主存儲器的量。
[0088]段尺寸:段中的數據單元的最大數量。
[0089]字:如在這裡使用的，在底層計算機系統中可尋址的最小存儲器單元。
[0090]用於添加、更新和刪除行的偽代碼
[0091]在下面，本發明的優選實施例的實現方式通過偽代碼列表的方式被說明。下劃線的文本指示數據類型或者過程聲明的開始。斜體文本包含注釋。縮進很重要。
[0092]數據結構
[0093]表格由以下各項組成:
[0094]列(從O向上編號)
[0095]最大行號(最大使用行號)
[0096]空閒行號的列表
[0097]列由以下各項組成:
[0098]段
[0099]段尺寸
[0100]段由以下各項組成:
[0101]單元
[0102](可以通過檢查任何單元來確定單元容量)
[0103]單元是:
[0104]整數單元(具有η個比特)
[0105]或者浮點單元
[0106]η比特整數單元應當包含在η比特的存儲器中存儲的一個二進位編碼的整數。_7]行由以下各項組成:
[0108]欄位(從O向上編號,其中編號對應於表格的列號)
[0109]欄位是:
[0110]整數欄位，
[0111]浮點欄位
[0112]或者文本欄位
[0113]為了簡單，我們在這裡僅考慮整數欄位和整數列。
[0114]過程
[0115]如何將新行添加到表格:[0116]挑選任何空閒行號y
[0117]對於該行的每個整數欄位
[0118]確定對應於該欄位的列
[0119]將欄位值添加到該列的第y個單元
[0120]對於該行的每個其他欄位
[0121](為了簡潔而被省略)
[0122]在給定行號I的情況下如何更新表格中的行:
[0123]對於該行的每個整數欄位
[0124]確定對應於該欄位的列
[0125]將該列的第y個單元設置為欄位值
[0126]對於該行的每個其他欄位
[0127](為了簡潔而被省略)
[0128]如何從表格中移出行:
[0129]將行號標記為空閒
[0130]將行號包括在空閒行的列表中
[0131]如何讀取表格的所有行:
[0132]對於從O到最大行號的每個行號
[0133]如果該行號未被標記為空閒
[0134]則讀取*該行
[0135]*=代而插入任何其他動作。
[0136]在給定列類型的情況下如何初始化新表格:
[0137]將最大行號設置為O
[0138]創建空閒行號的空列表
[0139]對於每個列
[0140]創建列記錄
[0141]初始化該列記錄
[0142]如何初始化新的列記錄:
[0143]將列尺寸選擇為
[0144](一個變體，不同選項在上面被討論)
[0145]以下各項中的最大值(
[0146]按照字的最小段尺寸/預期單元尺寸，
[0147]預期表格尺寸/100)
[0148](假定預期尺寸是正確的，這樣每個段包含更大表格的正好1%;如果表格預期是小的，則我們具有各自具有最小合理段尺寸的更少段)
[0149]存儲段尺寸
[0150]存儲段的空列表
[0151]如何桃詵仵何宇閒行號:
[0152]如果空閒行號的列表是空的
[0153]則增加表格的最大行號並且返回該最大行號[0154]否則從列表中移除第一號碼並且返回該第一號碼
[0155]如何將欄位值添加到列的第X個單元:
[0156]單元X的段號y被除以列的段尺寸
[0157]段內的單元號z是該除法的餘數
[0158]如果列沒有第y個段，則
[0159]確定足夠用於欄位值的單元容量
[0160]創建具有該容量的段
[0161]將段的第z個單元設置為欄位值_2]如何將列的第X個單元設置為值V:
[0163]單元X的段號y被除以列的段尺寸
[0164]段內的單元號z是該除法的餘數
[0165]將第y個段的第z個單元設置為值V
[0166]如何將段的第X個單元設置為值V:
[0167]如果欄位值不適合該段的單元容量，則
[0168]確定足夠用於該欄位值的單元容量
[0169]用具有該容量的新段來替代該段
[0170]將該欄位值二進位編碼到第X個單元中
[0171]如何創建具有給定單元容暈的段:
[0172]創建單元的數組
[0173]其中數組長度是預設段尺寸
[0174]並且其中單元的比特欄位正好寬到足以用於希望的單元容量創建包含該數組的新段
[0175]將該段添加到列的段列表(在最後一個位置中)
[0176]如何用具有給定單元容暈的新段來替代舊段
[0177]確定該舊段的使用單元容量
[0178]新單元容量是使用容量和給定容量中的最大值
[0179]創建具有新單元容量的新段
[0180]將單元從舊段變換到新段
[0181]在列的段列表中用新段替代舊段
[0182]如果沒有自動垃圾回收:
[0183]釋放為舊段分配的存儲器
[0184]如何確定段的使用單元容暈:
[0185]結果:=0
[0186]對於段的每個單元
[0187]確定足夠用於單元值的單元容量X
[0188]如果x>結果
[0189]則結果:=X
[0190]返回結果
[0191]如何將單元從舊段變換到新段:[0192]兩個段必須具有相同尺寸
[0193]對於舊段中的每個單元
[0194]將單元值變換為新段的單元的比特欄位寬度
[0195]將變換後的值寫入到新段中具有相同索引的單元
[0196]總結
[0197]在諸如資料庫管理系統或其他存儲系統的現代計算機系統處理表格數據中，在底層計算機系統的有限可用存儲器中處理大表格的問題是困難問題。通過將表格視為一系列的列而非行並且對這些列使用分段(基於相等的段尺寸設置)，本發明的優選實施例採用了與傳統策略相比不同的方式。這繼而使得能夠提供用於在有限存儲器中高效處理大表格的機制以及優化對非均一數據的折衷的自適應機制。
【權利要求】
1.一種在面向列的存儲系統中在具有列(C)和行(R)的表格數據結構(10)中存儲數據的方法，其中該方法包括以下步驟: a.將列(C)中的至少一個劃分為多個段(S)，其中每個段(S)具有相關聯的單元尺寸，該單元尺寸指示相應段(S)中的數據項的最大尺寸； b.當將數據項存儲到所述段(S)中的一個中時， -判定該數據項的尺寸是否超過該段(S)的單元尺寸；並且 -如果該數據項的尺寸超過該段(S)的單元尺寸，則適應性改變(120)該段(S)的單元尺寸以適應該數據項的尺寸； c.其中適應性改變(120)該段(S)的單元尺寸以適應該數據項的尺寸是獨立於所述多個段(S)中的其他段的單元尺寸而執行的。
2.如權利要求1所述的方法，其中，每個段(S)具有相關聯的段尺寸，該段尺寸指示相應段(S )中的數據項的最大數目。
3.如權利要求2所述的方法，其中，列(C)中的所有段(S)具有相同段尺寸。
4.如權利要求2或3所述的方法，包括基於底層硬體系統的特性，例如工作存儲器與處理器之間的帶寬，來確定最佳段尺寸的步驟。
5.如在先權利要求2-4中任一項所述的方法，包括基於關於所述表格數據結構(10)中存儲的數據的統計來確定最佳段尺寸的步驟。
6.如在先權利要求2-5中任一項所述的方法，包括基於對所述表格數據結構(10)中的數據執行的添加、更新和/或移除操作的頻率來確定最佳段尺寸的步驟。
7.如在先權利要求2-6中任一項所述的方法，其中，確定最佳段尺寸的步驟當數據被添加、更新和/或移除時自動執行、自動並周期性地執行，和/或手動地執行。
8.如在先權利要求中任一項所述的方法，其中，所述表格數據結構(10)的列(C)被一個接一個地存儲在所述存儲系統的工作存儲器和/或永久存儲裝置中。
9.如在先權利要求中任一項所述的方法，還包括提供將數據項映射到整數值的字典數據結構以及將所述整數值而非所述數據項存儲在所述表格數據結構中的步驟。
10.如在先權利要求中任一項所述的方法，其中，適應性改變(120)所述段(S)的單元尺寸以適應所述數據項的尺寸包括選擇將最大數據項存儲在相應列(C)中所需的最小數目的比特。
11.一種包括用於實現根據在先權利要求1-10中任一項的方法的指令的電腦程式。
12.—種用於在具有列(C)和行(R)的表格數據結構(10)中存儲數據的面向列的存儲系統，其中該系統包括: a.用於將列(C)中的至少一個劃分為多個段(S)的裝置，其中每個段(S)具有相關聯的單元尺寸，該單元尺寸指示相應段(S)中的數據項的最大尺寸； b.用於將數據項存儲到所述段(S)中的一個的裝置，其適用於: -判定該數據項的尺寸是否超過該段(S)的單元尺寸；並且 -如果該數據項的尺寸超過該段(S)的單元尺寸，則適應性改變(120)該段(S)的單元尺寸以適應該數據項的尺寸； c.其中適應性改變(120)該段(S)的單元尺寸以適應該數據項的尺寸是獨立於所述多個段(S)中的其他段的單元尺寸而執行的。
13.如權利要求12所述的系統，其中，每個段(S)具有相關聯的段尺寸，該段尺寸指示相應段(S)中的數據項的最大數目，其中優選地列(C)中的所有段(S)具有相同段尺寸。
14.如權利要求13所述的系統，包括用於基於底層硬體系統的特性，例如工作存儲器與處理器之間的帶寬，來確定最佳段尺寸的裝置。
15.如在先權利要求13或14中任一項所述的系統,包括基於關於所述表格數據結構 (10)中存儲的數據的統計來確定最佳段尺寸的裝置。
【文檔編號】G06F17/30GK103631838SQ201310258423
【公開日】2014年3月12日 申請日期:2013年6月26日 優先權日:2012年8月24日
【發明者】丹尼爾·烏爾裡克·史瑞克 申請人:軟體股份公司