Adaptive cell-specific dictionaries for frequency-partitioned multi-dimensional data

• US 8,442,988 B2
• Filed: 11/04/2010
• Issued: 05/14/2013
• Est. Priority Date: 11/04/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Draese, Oliver, Hrle, Namik, Koeth, Oliver, Li, Tianchao, Raman, Vijayshankar, Stolze, Knut
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US12/939,605
• Publication Number:
  US 20120117064A1
• Time in Patent Office: 922 Days
• Field of Search: None
• US Class Current: 707/750
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A cell-specific dictionary is applied adaptively to adequate cells, where the cell-specific dictionary subsequently optimizes the handling of frequency-partitioned multi-dimensional data. This includes improved data partitioning with super cells or adjusting resulting cells by sub-dividing very large cells and merging multiple small cells, both of which avoid the highly skewed data distribution in cells and improve the query processing. In addition, more efficient encoding is taught within a cell in case the distinct values that actually appear in that cell are much smaller than the size of the column dictionary.

Claims

1. A computer-based method comprising the steps of:

(a) maintaining a global dictionary for each column in a plurality of columns associated with a database table;

(b) partitioning each column in said plurality of columns into one or more partitions;

(c) forming a plurality of cells, each cell formed by grouping a plurality of partitions;

(d) maintaining at least one cell-specific dictionary for at least one cell among said plurality of cells;

(e) receiving a query to compile and execute against said database table;

(f) adaptively applying said at least one cell-specific dictionary for said at least one cell when said at least one cell crosses a boundary of column partitions or when compression can be improved;

(g) compiling and executing said received query based on said application of at least one cell-specific dictionary for said at least one cell of said database table and said global dictionary for remainder of cells or columns;

(h) outputting said results of said compilation and execution step, and

wherein said partitioning comprising partitioning each column individually to form said plurality of cells as cross products, and super-cells are formed to avoid splitting cells that otherwise fall below a predetermined cell threshold.

2. The computer based method of claim 1, wherein said cell-specific dictionary describes a mapping from bit codes to values in a base dictionary.

3. The computer-based method of claim 2, wherein said mapping is based on references or pointers.

4. The computer-based method of claim 1, wherein large cells are further split, said splitting comprising:

starting with a data set consisting of rows and columns, collecting frequencies of values in each column into histograms, and partitioning columns such that the most frequent values are encoded with short codes, thereby grouping the data into sub-cells and reducing the overall code size.

5. The computer-based method of claim 1, wherein smaller cells are merged into at least one bigger cell to improve compression.

6. The computer-based method of claim 1, wherein said computer-based method is implemented over a network.

7. The computer-based method of claim 6, wherein said network is a Local Area Network (LAN) or a Wide Area Network (WAN).

8. A computer-based method comprising the steps of:

(a) maintaining a global dictionary for each column in a plurality of columns associated with a database table;

(b) partitioning said each column in said plurality of columns into one or more partitions;

(c) forming a plurality of cells, each cell formed by grouping a plurality of partitions;

(d) maintaining at least one cell-specific dictionary for at least one cell among said plurality of cells;

(e) processing any of the following post-processing cell adjustments;

split processing or merge processing,

said split processing comprising;

splitting at least a single cell among said plurality of cells into two sub-cells and forming a cell-specific dictionary for each of said sub-cells;

said merge processing comprising;

merging at least two cells among said plurality of cells into a larger cell and forming a cell-specific dictionary as a superset of said at least two cells'"'"' dictionaries;

(f) receiving a query to compile and execute against said database table;

(g) adaptively applying said cell-specific dictionary/dictionaries for sub-cells, merged sub-cells, or split cells when at least one cell crosses a boundary of column partitions or compression can be improved;

(h) compiling and executing said received query based on said adaptive application of said cell-specific dictionary/dictionaries for sub-cells, merged sub-cells, or split cells and said global dictionary for remainder of cell(s) or columns; and

(i) outputting said results of said compilation and execution step.

9. The computer based method of claim 8, wherein said cell-specific dictionary describes a mapping from bit codes to values in a base dictionary.

10. The computer-based method of claim 9, wherein said mapping is based on references or pointers.

11. The computer-based method of claim 8, wherein said method further comprises the steps of:

partitioning each column individually to form said plurality of cells as cross products; and

forming super-cells by avoid splitting cells that otherwise fall below a predetermined cell threshold.

12. The computer-based method of claim 8, wherein large cells are split, said splitting comprising:

starting with a data set consisting of rows and columns, collecting frequencies of values in each column into histograms, and partitioning columns such that the most frequent values are encoded with short codes, thereby grouping the data into sub-cells and reducing the overall code size.

13. The computer-based method of claim 8, wherein said computer-based method is implemented over a network.

14. The computer-based method of claim 13, wherein said network is a Local Area Network (LAN) or a Wide Area Network (WAN).

15. An article of manufacture comprising computer storage medium storing computer readable program code which, when executed by a computer, implements a computer-based method comprising the steps of:

(a) maintaining a global dictionary for each column in a plurality of columns associated with a database table;

(b) partitioning each column in said plurality of columns into one or more partitions;

(c) forming a plurality of cells, each cell formed by grouping a plurality of partitions;

(d) maintaining at least one cell-specific dictionary for at least one cell among said plurality of cells;

(e) receiving a query to compile and execute against said database table;

(f) adaptively applying said at least one cell-specific dictionary for said at least one cell when said at least one cell crosses a boundary of column partitions or when compression can be improved;

(g) compiling and executing said received query based on said application of at least one cell-specific dictionary for said at least one cell of said database table and said global dictionary for remainder of cells or columns;

(h) outputting said results of said compilation and execution step, and

wherein said partitioning comprising partitioning each column individually to form said plurality of cells as cross products, and super-cells are formed to avoid splitting cells that otherwise fall below a predetermined cell threshold.

16. The article of manufacture of claim 15, wherein said cell-specific dictionary describes a mapping from bit codes to values in a base dictionary, said mapping based on references or pointers.

17. The article of manufacture of claim 15, wherein large cells are further split, said splitting comprising:

starting with a data set consisting of rows and columns, collecting frequencies of values in each column into histograms, and partitioning columns such that the most frequent values are encoded with short codes, thereby grouping the data into sub-cells and reducing the overall code size.

18. The article of manufacture of claim 15, wherein smaller cells are merged into at least one bigger cell to improve compression.

19. An article of manufacture comprising computer storage medium storing computer readable program code which, when executed by a computer, implements a computer-based method comprising the steps of:

(a) maintaining a global dictionary for each column in a plurality of columns associated with a database table;

(b) partitioning said each column in said plurality of columns into one or more partitions;

(c) forming a plurality of cells, each cell formed by grouping a plurality of partitions;

(d) maintaining at least one cell-specific dictionary for at least one cell among said plurality of cells;

(e) processing any of the following post-processing cell adjustments;

split processing or merge processing,

said split processing comprising;

splitting at least a single cell among said plurality of cells into two sub-cells and forming a cell-specific dictionary for each of said sub-cells;

said merge processing comprising;

merging at least two cells among said plurality of cells into a larger cell and forming a cell-specific dictionary as a superset of said at least two cells'"'"' dictionaries;

(f) receiving a query to compile and execute against said database table;

(g) adaptively applying said cell-specific dictionary/dictionaries for sub-cells, merged sub-cells, or split cells when at least one cell crosses a boundary of column partitions or compression can be improved;

(h) compiling and executing said received query based on said adaptive application of said cell-specific dictionary/dictionaries for sub-cells, merged sub-cells, or split cells and said global dictionary for remainder of cell(s) or columns; and

(i) outputting said results of said compilation and execution step.

20. The article of manufacture of claim 19, wherein said cell-specific dictionary describes a mapping from bit codes to values in a base dictionary.

21. The article of manufacture of claim 20, wherein said mapping is based on references or pointers.

22. The article of manufacture of claim 19, wherein said method further comprises the steps of:

partitioning each column individually to form said plurality of cells as cross products;

and forming super-cells by avoid splitting cells that otherwise fall below a predetermined cell threshold.

23. The article of manufacture of claim 19, wherein large cells are split, said splitting comprising:

starting with a data set consisting of rows and columns, collecting frequencies of values in each column into histograms, and partitioning columns such that the most frequent values are encoded with short codes, thereby grouping the data into sub-cells and reducing the overall code size.