用於通過使用解壓縮圖進行數據訪問的系統和方法

2023-07-22 10:52:46 1

用於通過使用解壓縮圖進行數據訪問的系統和方法
【專利摘要】本公開涉及用於通過使用解壓縮圖進行數據訪問的系統和方法。提供實現和利用用於解壓縮資料庫系統中的數據的技術的方法和設備，包括電腦程式產品。接收屬於壓縮數據集內的數據子集的查詢。通過使用成本模型評估一個或多個解壓縮策略。成本模型包含估計的過濾因子。基於一個或多個解壓縮策略的評估結果，選擇低成本解壓縮策略。在壓縮數據集內定位代表請求的數據子集的一個或多個字節。通過使用選擇的解壓縮策略僅解壓縮與數據子集對應的壓縮數據的一部分，同時使剩餘的數據集保持壓縮狀態。
【專利說明】用於通過使用解壓縮圖進行數據訪問的系統和方法

【技術領域】
[0001] 本發明涉及資料庫系統，更特別地，涉及用於資料庫系統中的壓縮和解壓縮技術。 資料庫系統管理大量的數據，並且一般使用數據壓縮作為用於減少用於容納數據對象的盤 和/或內存存儲器的量的手段。

【背景技術】
[0002] 例如，可從 Armonk, NY 的 International Business Machines Corporation 得到 的DB2資料庫系統提供存儲器優化特徵，該存儲器優化特徵為了減少盤空間和存儲器基礎 構架要求，利用明顯壓縮盤上的數據的壓縮特徵的組合。由於盤存儲器系統常常可能是數 據庫解決方案中最昂貴的部件，因此即使存儲器子系統的很小的減少也可導致整個資料庫 解決方案的明顯的成本節省。在DB2資料庫系統中使用的一些數據壓縮技術中包括行壓 縮、自適應行壓縮和XML壓縮。
[0003] 雖然各種壓縮技術一般明顯節省內存和存儲器使用，但它們在訪問數據時也引起 更多地使用中央處理單元（CPU)資源（即，更高的CPU使用）。因此，有利的是具有減少當 僅需要訪問壓縮數據的一部分時所需要的CPU資源的量的技術。


【發明內容】

[0004] 根據本發明的一個實施例，提供實現和利用用於解壓縮資料庫系統中的數據的技 術的方法和設備，包括電腦程式產品。接收屬於壓縮數據集內的數據子集的查詢。通過 使用成本模型評估一個或多個解壓縮策略。成本模型包含估計的過濾因子。基於一個或多 個解壓縮策略的評估結果，選擇低成本解壓縮策略。在壓縮的數據集內定位代表請求的數 據子集的一個或多個字節。通過使用選擇的解壓縮策略，僅解壓縮與數據子集對應的壓縮 數據的一部分，同時使剩餘的數據集保持在壓縮狀態。
[0005] 在以下的附圖和說明書中闡述本發明的一個或多個實施例的細節。藉助於說明書 和附圖以及權利要求，本發明的其它特徵和優點將十分明顯。

【專利附圖】

【附圖說明】
[0006] 圖1是示出根據一個實施例的用於解壓縮數據的處理（100)的流程圖。
[0007] 圖2示出可根據一個實施例使用的計算機體系結構（200)。
[0008] 在各附圖中，類似的附圖標記表示類似的要素。

【具體實施方式】
[0009] 如上所述，諸如DB2資料庫系統的許多資料庫系統當前壓縮整個行，並且在需要 訪問行中的任意列時解壓縮整個行。但是，當針對表運行查詢時，經常僅需要訪問行中的列 的子集（或者表中的頁內的行的子集）。這裡描述的實施例通過提供為了提供特定查詢所 需要的數據而確定需要擴展解壓縮數據的哪個部分的方式，大大改善了僅需要訪問行的一 部分的查詢的性能。
[0010] 所屬【技術領域】的技術人員知道，本發明的各個方面可以實現為系統、方法或計算 機程序產品。因此，本發明的各個方面可以具體實現為以下形式，即：完全的硬體實施方式、 完全的軟體實施方式（包括固件、駐留軟體、微代碼等），或硬體和軟體方面結合的實施方 式，這裡可以統稱為"電路"、"模塊"或"系統"。此外，在一些實施例中，本發明的各個方面 還可以實現為在一個或多個計算機可讀介質中的電腦程式產品的形式，該計算機可讀介 質中包含計算機可讀的程序代碼。
[0011] 可以採用一個或多個計算機可讀介質的任意組合。計算機可讀介質可以是計算機 可讀信號介質或者計算機可讀存儲介質。計算機可讀存儲介質例如可以是一但不限於一 電、磁、光、電磁、紅外線、或半導體的系統、裝置或器件，或者任意以上的組合。計算機可讀 存儲介質的更具體的例子（非窮舉的列表）包括：具有一個或多個導線的電連接、可攜式計 算機盤、硬碟、隨機存取存儲器（RAM)、只讀存儲器（ROM)、可擦式可編程只讀存儲器（EPROM 或快閃記憶體）、光纖、可攜式緊湊盤只讀存儲器（CD-ROM)、光存儲器件、磁存儲器件、或者上述的 任意合適的組合。在本文件中，計算機可讀存儲介質可以是任何包含或存儲程序的有形介 質，該程序可以被指令執行系統、裝置或者器件使用或者與其結合使用。
[0012] 計算機可讀的信號介質可以包括在基帶中或者作為載波一部分傳播的數據信號， 其中承載了計算機可讀的程序代碼。這種傳播的數據信號可以採用多種形式，包括一但不 限於一電磁信號、光信號或上述的任意合適的組合。計算機可讀的信號介質還可以是計算 機可讀存儲介質以外的任何計算機可讀介質，該計算機可讀介質可以發送、傳播或者傳輸 用於由指令執行系統、裝置或者器件使用或者與其結合使用的程序。
[0013] 計算機可讀介質上包含的程序代碼可以用任何適當的介質傳輸，包括一但不限 於一無線、有線、光纜、RF等等，或者上述的任意合適的組合。
[0014] 可以以一種或多種程序設計語言的任意組合來編寫用於執行本發明操作的計算 機程序代碼，所述程序設計語言包括面向對象的程序設計語言一諸如Java、Smalltalk、C++ 等，還包括常規的過程式程序設計語言一諸如"C"語言或類似的程序設計語言。程序代碼可 以完全地在用戶計算機上執行、部分地在用戶計算機上執行、作為一個獨立的軟體包執行、 部分在用戶計算機上部分在遠程計算機上執行、或者完全在遠程計算機或伺服器上執行。 在涉及遠程計算機的情形中，遠程計算機可以通過任意種類的網絡一包括區域網（LAN)或 廣域網（WAN)-連接到用戶計算機，或者，可以連接到外部計算機（例如利用網際網路服務提 供商來通過網際網路連接）。
[0015] 下面將參照根據本發明實施例的方法、裝置（系統）和電腦程式產品的流程圖 和/或框圖描述本發明。應當理解，流程圖和/或框圖的每個方框以及流程圖和/或框圖 中各方框的組合，都可以由電腦程式指令實現。這些電腦程式指令可以提供給通用計 算機、專用計算機或其它可編程數據處理裝置的處理器，從而生產出一種機器，使得這些計 算機程序指令在通過計算機或其它可編程數據處理裝置的處理器執行時，產生了實現流程 圖和/或框圖中的一個或多個方框中規定的功能/動作的裝置。
[0016] 也可以把這些電腦程式指令存儲在計算機可讀介質中，這些指令使得計算機、 其它可編程數據處理裝置、或其他設備以特定方式工作，從而，存儲在計算機可讀介質中的 指令就產生出包括實現流程圖和/或框圖中的一個或多個方框中規定的功能/動作的指令 的製造品（article of manufacture) 〇
[0017] 電腦程式指令也可被加載到計算機、其它可編程數據處理設備或其它裝置上， 以導致在計算機、其它可編程設備或其它裝置上執行的一系列的操作步驟產生計算機實現 的過程，使得在計算機或其它可編程設備上執行的指令提供用於實現在流程圖和/或框圖 塊中規定的功能/動作的處理。
[0018] 從圖1可以看出，根據一個實施例的用於解壓縮數據的處理（100)從接收屬於壓 縮數據集內的數據子集的查詢（步驟102)開始。一般地，在資料庫系統中，構建包含關於 需要訪問行的什麼列的信息的結構。例如，在DBS資料庫系統中，存在詳述需要什麼列以評 估特定查詢的謂詞以及需要檢索什麼列並將其輸出到用於使行具有資格的調用器的結構。 響應於接收查詢，資料庫系統詢問這些結構以確切地確定對於謂詞評估階段以及對於選擇 列表處理需要行的什麼部分（對於滿足謂詞的行需要返回的行）。例如，給定具有20個列 C1 - C20的表，會存在以下的查詢：
[0019] SELECT Cl, C17
[0020] FROM Tl
[0021] WHERE Cl = 12345 ；
[0022] 在這種情況下，查詢需要訪問列Cl以評估謂詞；並且，當謂詞為真時，需要訪問列 Cl和C17。出於解釋的目的，假定各列10位元組長且列以次序(：1、02、03、?20被存儲。在 這種情況下，列Cl佔據行中的字節位置1?10,並且，列C17佔據字節C161?C170。因此， 評估結構的代碼確定評估行的謂詞僅需要行的字節1?10。另外，對於以上的選擇列表，需 要Cl和C17,但是，由於以前對於謂詞評估而解壓縮了 C1，因此，如果實際返回行，那麼僅需 要解壓縮C17。因此，對於以上的查詢，可以使用以下的解壓縮策略：
[0023] 階段1解壓縮（即，對於謂詞評估需要列的解壓縮）：
[0024] 僅需要列Cl (行的字節1?10)。
[0025] 階段2解壓縮（對於選擇列表需要所有剩餘列的解壓縮）：
[0026] 由於已完成C1，因此僅需要列C17(行的字節161?170)。
[0027] 本領域技術人員理解，存在確保所有需要的列在它們被需要之前被解壓縮的多種 方式，並且，以上的二階段例子僅是一個示例性實施例。例如，作為以上方法的替代，階段1 可僅解壓縮列Cl和C17的所有字節。在其它的實施例中，可存在需要行的不同部分的更多 階段，即，可能是如果存在分組處理（group-by processing),則也可在附加階段中解壓縮 分組處理所需要的列。因此，處理評估一個或多個解壓縮策略（步驟104)。在圖1所示的 實施例中，使用具有估計的過濾因子的成本模型來提出最佳（如果過濾因子正確）解壓縮 方法。例如，如果已知需要nl個循環來解壓縮列C1，那麼需要nl7個循環來解壓縮列C17， 並且謂詞的過濾因子是0. 25 (即，所有行的1/4滿足謂詞），那麼可以期望每個解壓縮的成 本會是nl+(nl7*0. 25)個循環。類似地，如果用於解壓縮從Cl到C17的所有列的CPU時間 是nl…nl7,那麼如果nl…nl7小於（nl+(nl7*0. 25))個循環，則解壓縮整個行會更合理。 因此，通過在確定解壓縮策略時使用這種成本模型方法，能夠提出行訪問的最佳解壓縮策 略。本領域技術人員可以理解，這種成本模型是可擴展的，並允許對於解壓縮行/策略的不 同部分使用不同的軟體和/或硬體方法。基於步驟104中的壓縮策略的評估，選擇低成本 解壓縮策略（步驟106)。在本文中，還應注意，雖然在本例子中使用"循環"，但它不必是實 際循環。可出於選擇"最佳"解壓縮策略的目的，可使用允許在兩個或更多個解壓縮方法之 間進行適當比較的任意類型的"計數"或"CPU單元"。
[0028] 最後，使用選擇的解壓縮策略以實際訪問行並定位數據的請求的字節並解壓縮它 們（步驟108)。在以上的示例性查詢中，資料庫引擎現在獲知需要訪問壓縮行的字節1? 10,以評估謂詞。因此，作為解壓縮行的所有200個字節的替代，解壓縮邏輯被調用以僅解 壓縮前10個字節並然後停止。然後，可評估謂詞。如果謂詞評估為真，從而意味著需要返回 選擇列，那麼資料庫引擎會然後嘗試僅解壓縮列C17所需要的字節（字節161?170)。在 這種情況下，解壓縮算法被增強以處理壓縮數據的"子串"。為此，構建對於壓縮數據的各令 牌確切地確定令牌代表多少字節的結構。許多資料庫系統（包含DB2資料庫系統）當前使 用Lempel-Ziv壓縮，但是本領域技術人員可以理解，可以類似地處理大多數的其它壓縮算 法。例如，雖然Lempel-Ziv壓縮使用令牌，但其它的壓縮算法可使用知曉可變長度列的結 構並且可被用於確定當存在可變長度列時需要的字節序列的其它類型的單元或其它邏輯。
[0029] 例如，假定存在具有8個令牌的非常小的壓縮字典且每個具有以下的長度：
[0030]

【權利要求】
1. 一種用於解壓縮資料庫系統中的數據的計算機實現的方法，包括： 接收屬於壓縮數據集內的數據子集的查詢； 通過使用成本模型評估一個或多個解壓縮策略，所述成本模型包含估計的過濾因子； 基於一個或多個解壓縮策略的評估結果，選擇低成本解壓縮策略； 在壓縮數據集內定位代表請求的數據子集的一個或多個字節；和 通過使用選擇的解壓縮策略僅解壓縮與數據子集對應的壓縮數據的一部分，同時使剩 餘的數據集保持壓縮狀態。
2. 根據權利要求1的方法，其中，數據子集包含W下之一：資料庫表的行中的列的子 集；資料庫表的行內的列或字節的子集；和資料庫表的頁內的行的子集。
3. 根據權利要求1的方法，其中，解壓縮策略包含兩個或更多個解壓縮階段。
4. 根據權利要求1的方法，其中，評估一個或多個解壓縮策略包含計算用於僅解壓縮 行內的列的子集的成本並且比較計算的成本與解壓縮行內的所有列。
5. 根據權利要求1的方法，其中，在壓縮數據集內定位代表請求的數據子集的一個或 多個字節包含： 確定代表壓縮數據的一定數量的字節的單元；和 確定需要解壓縮什麼單元W到達代表壓縮數據集內的請求的數據子集的一個或多個 字節。
6. 根據權利要求5的方法，還包括： 存儲每行的圖，所述圖描述對於每個單元的開始的偏移。
7. 根據權利要求6的方法，其中，所述圖被存儲為資料庫系統的內存緩衝器中的陣列。
8. 根據權利要求5的方法，其中，每個可變長度列的前面是描述可變長度列的長度的 數字。
9. 根據權利要求1的方法，其中，解壓縮在行的開始處開始。
10. 根據權利要求1的方法，其中，解壓縮在行的結尾處開始。
11. 一種用於解壓縮資料庫系統中的數據的系統，包括： 被配置為接收屬於壓縮數據集內的數據子集的查詢的設備； 被配置為通過使用成本模型評估一個或多個解壓縮策略的設備，所述成本模型包含估 計的過濾因子； 被配置為基於一個或多個解壓縮策略的評估結果選擇低成本解壓縮策略的設備； 被配置為在壓縮數據集內定位代表請求的數據子集的一個或多個字節的設備；和 被配置為通過使用選擇的解壓縮策略僅解壓縮與數據子集對應的壓縮數據的一部分、 同時使剩餘的數據集保持壓縮狀態的設備。
【文檔編號】G06F17/30GK104462176SQ201410476850
【公開日】2015年3月25日 申請日期:2014年9月18日 優先權日:2013年9月19日
【發明者】R·W·利勒 申請人:國際商業機器公司