Database system with methodology for storing a database table by vertically partitioning all columns of the table

• US 5,794,229 A
• Filed: 12/11/1995
• Issued: 08/11/1998
• Est. Priority Date: 04/16/1993
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: White, Peter, French, Clark
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/570,183
• Time in Patent Office: 974 Days
• Field of Search: 395/601-612, 395/603, 707/2, 707/3, 707/10, 707/205, 705/35, 711/100, 711/171
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A Client/Server Database System with improved methods for performing database queries, particularly DSS-type queries, is described. The system includes one or more Clients (e.g., Terminals or PCs) connected via a Network to a Server. In general operation, Clients store data in and retrieve data from one or more database tables resident on the Server by submitting SQL commands, some of which specify "queries"--criteria for selecting particular records of a table. The system implements methods for storing data vertically (i.e., by column), instead of horizontally (i.e., by row) as is traditionally done. Each column comprises a plurality of "cells" (i.e., column value for a record), which are arranged on a data page in a contiguous fashion. By storing data in a column-wise basis, the system can process a DSS query by bringing in only those columns of data which are of interest. Instead of retrieving row-based data pages consisting of information which is largely not of interest to a query, column-based pages can be retrieved consisting of information which is mostly, if not completely, of interest to the query. The retrieval itself can be done using more-efficient large block I/O transfers. The system includes data compression which is provided at the level of Cache or Buffer Managers, thus providing on-the-fly data compression in a manner which is transparent to each object. Since vertical storage of data leads to high repetition on a given data page, the system provides improved compression/decompression.

Claims

1. In a computer system having a database storing a database table, said database table presenting user information as rows of data records divided into columns of information, each column representing a particular category of information, a method for storing the database table by vertically partitioning each and every column of the database table without regard to storage devices available to the system, the method comprising:

irrespective of storage devices available to the system, creating for each column of the database table at least one associated data page for storing data values for the column;

for each data record of the database table, storing the data value for each column of the data record in one of the at least one data page associated with the column, so that data values for each particular column of a database table are all stored together in at least one data page associated with said each particular column; and

for each column, linking together all of said at least one data page associated with the column to form a page chain for the column, so that each page chain stores together all of the data values for a particular column of the database table.

2. The method of claim 1 wherein some of the data pages for a given page chain are stored contiguously on a storage device.

3. The method of claim 2, further comprising:

receiving a query which requires the database to retrieve from storage all of the data pages for a particular column; and

retrieving the data pages for the particular column using large block input/output transfer for the computer system.

4. The method of claim 3, wherein each data page stores 64K of data values and wherein said large block input/output transfer includes retrieving a 64K data page in a single read operation.

5. The method of claim 1, further comprising:

receiving a query for testing the data values of a particular column against a user-specified query condition; and

when executing the query, retrieving only the data pages associated with the particular column.

6. The method of claim 1, wherein said linking step includes:

storing in each data page a pointer for referencing another data page storing data values for the same column, thereby forming a page chain of data pages for each column.

7. The method of claim 1, further comprising:

storing a system catalog referencing the first data page of each page chain, so that a logical view of the database table in row/column format can be reconstructed by retrieving data values from said page chains.

8. The method of claim 7, further comprising:

receiving a user request to alter the database table by deleting a particular column; and

satisfying said user request by deleting the column from the system catalog and freeing storage occupied by data pages for the particular column.

9. The method of claim 7, further comprising:

receiving a user request to alter the database table by adding a new column; and

satisfying said user request by creating a new page chain for the new column and adding the column to the system catalog.

10. The method of claim 1, further comprising:

receiving a user request for performing an aggregation operation on a particular column of the database table; and

satisfying the user request by successively retrieving the data pages associated with the particular column and applying the aggregate operation to successive ones of the data values stored on each of the data pages retrieved.

11. The method of claim 10, wherein the aggregate operation includes a selective one of average value, maximum value, minimum value and summation of values, for the particular column.

12. The method of claim 10, wherein said retrieving step is accomplished by retrieving only the data pages associated with the particular column.

13. The method of claim 10, wherein the aggregate operation includes a selective one of an SQL AVG, MAX, MIN, and SUM operation, for the particular column.

14. The method of claim 1, wherein each data page includes a page header specifying a particular type of compression which is suitable for the data values stored on the data page.

15. The method of claim 14, further comprising:

compressing the data values stored on each data page according to the type of compression specified by the page header for the data page.

16. A database system comprising:

a computer having at least one processor and a memory;

a storage device for storing a database table;

a display device for presenting said database table to a user in row and column format;

means for creating a vertical partition for each and every column of the database table, each vertical partition having data values for only a single column of the database table; and

means for transferring each vertical partition to and from the storage device, so that at least some data values for a particular column are stored together at a contiguous location on the storage device

wherein said means for creating a vertical partition for each column includes;

forming a vertical page chain for each column, said vertical page chain storing only those data value of the records which correspond to the column for the page chain.

17. The system of claim 16, wherein each column comprises a category of information of the database table.

18. The system of claim 17, wherein each row comprises a record of the database table storing particular data values for each category of information.

19. The system of claim 16, wherein at least one column comprises data values having a fixed length and wherein the data pages for said at least one column store data values in fixed-length cells.

20. The system of claim 16, further comprising:

query processing means for receiving a user query about data values stored in a particular column, said query processing means including means for executing the query by scanning only the data pages for the particular column.

21. The system of claim 16, further comprising:

data compression means for compressing each data page according to a type of compression specified on a page-by-page basis.

22. The system of claim 21, wherein said type of compression is selected from leading key compression, LZS compression, LZW compression, and Run-Length Encoding compression.

23. The system of claim 16, wherein said means for transferring includes:

large block transferring means for retrieving data values of a particular vertical partition as a single large block.

24. The system of claim 23, wherein said single large block comprises a 64K storage block.