Database system with buffer manager providing per page native data compression and decompression

• US 5,794,228 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,047
• Time in Patent Office: 974 Days
• Field of Search: 395/601-606, 341/67, 707/1, 707/3, 707/2, 707/101, 707/205, 711/100, 711/177
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• 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 comprising user information, a method for storing and retrieving the database table comprising:

creating a plurality of data pages for storing user information on a storage device, each data page comprising a plurality of storage blocks and including information describing a type of information stored by the page and a preferred compression methodology for compressing user information stored by the page;

loading into memory user information from a particular data page by retrieving said particular data page and decompressing user information stored by the particular data page into a memory buffer;

modifying said user information which has been decompressed; and

storing the modified user information back in the particular data page by;

(i) determining the preferred compression methodology for the user information, by checking the information stored by the particular page describing the preferred compression methodology,

(ii) compressing the modified user information into a memory buffer, using said preferred compression methodology, and

(iii) storing the compressed modified user information back into the particular data page;

wherein said database table presents user information in row and column format, and wherein user information for a particular column is stored on one or more particular data pages such that each of said particular data pages stores user information only for said particular column.

2. The method of claim 1, further comprising:

determining whether the compressed modified user information still fits on the particular data page;

if the compressed modified user information no longer fits on the particular data page, locating another data page having sufficient storage space for storing the compressed modified user information;

storing the compressed modified user information on the located other data page; and

freeing up the storage space previously occupied by the user information.

3. The method of claim 1, wherein said compression methodology employed for a particular data page is selected by the system based on the type of user information stored by the data page.

4. The method of claim 1, wherein said compression methodology is a selected one of Leading Key, LZW, LZS, and Run-Length Encoding compression methodology.

5. The method of claim 1, wherein said loading and storing in the system are performed by a cache manager, and wherein said compressing and decompressing are performed as native services of the cache manager such that said compressing and decompressing are transparent to a user of said user information.

6. The method of claim 1, wherein at least one data page comprises user information from a particular column having data values of a particular data type, and wherein bits of the particular data type which are unused by the user information are eliminated from storage.

7. The method of claim 6, wherein said particular data type is an integer data type, and wherein bits of the particular data type which are unused by the user information comprise at least some high-order bits of the integer data type.

8. The method of claim 1, further comprising:

for each column of the database table, linking together data pages which store user information from a particular column to form a page-chain for that column.

9. The method of claim 8, further comprising:

storing in a system catalog sufficient information for each page chain so that the system can display a logical view of said database table in row and column format.

10. The method of claim 8, wherein at least two data pages within the system employ different compression methodologies, so that different compression methodologies may be simultaneously employed for storing the database table.

11. The method of claim 1, wherein said database table presents user information is row and column format, and wherein each data page only stores user information for a particular column, said particular column comprising low cardinality data, so that enhanced compression can be realized from increased data redundancy of storing low cardinality data together.

12. A database system comprising:

a computer having a processor and a memory buffer;

a storage device for storing a database table comprising a plurality of data records;

a cache manager, interposed between said memory buffer and said storage device, for loading data records from said storage device and storing data records back to said storage device, said data records being stored on data pages;

compression means, operably integrated with said cache manager, for automatically compressing data records which the cache manager stores back to said storage device; and

decompression means, operably integrated with said cache manager, for automatically decompressing data records which the cache manager retrieves from said storage device;

wherein compression and decompression are performed as native services of said cache manager, in a manner which is transparent to clients requesting use of said data records, and wherein said data records comprises different types of user information arranged into different columns of the database table, wherein user information for a particular column is stored in at least one data page for the column, and wherein said cache manager selects a particular type of compression and decompression, on a page-by-page basis.

13. The system of claim 12, wherein said cache manager selects a particular type of compression and decompression, based on what type of information is stored by said data records.