SQL-based database system with improved indexing methodology

• US 5,918,225 A
• Filed: 03/20/1997
• Issued: 06/29/1999
• 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 W., Chen, Yong Min, French, Clark D., Yach, David
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/820,864
• Time in Patent Office: 831 Days
• Field of Search: 707/1, 707/3, 707/4, 707/101, 707/103, 707/503, 1/1, 705/5, 705/37, 395/182.13, 395/183.02, 395/183.14, 379/113, 345/127, 711/3, 330/84, 330/124 R, 330/151, 455/12.7, 455/13.3, 455/127, 455/573
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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. The system builds the value lookup table for tracking unique values in the cells. As additional unique values are inserted into the column of the user'"'"'s table (i.e., maintained as the row-ordered cell array), the system assigns a small unique integer value to each unique user value. Instead of storing the original (wide) data value into the row-ordered array, the system instead stores the new (narrow) integer number into the row-ordered array. In response to a user request to retrieve a value for a given row number, the system fetches the appropriate chunk of the row-ordered array and retrieves the small integer value. This small integer value is then used to index into the value lookup table, for reconstituting the actual user data.

Claims

1. In a computer system having a database for storing and retrieving information from database tables, each database table presenting user information as rows of data records divided into columns of information, each column for storing data values of a particular data type, a method for indexing a database table of interest comprising:

selecting a particular column of the database table of interest to index;

allocating a value lookup table for the particular column, said value lookup table storing an entry representing each unique value present in said particular column; and

creating an index for the particular column by creating a cell array of identifiers, said cell array including a a linear sequence of cells such that each cell corresponds to one of the data records in the database table of interest, and wherein each cell stores an identifier referencing an entry in the value lookup table storing a data value which is equal to the data value stored in the particular column by the corresponding data record.

2. The method of claim 1, wherein said particular column stores data values in row-ordered fashion, and wherein said cell array stores identifiers in a corresponding row-ordered fashion.

3. The method of claim 1, wherein each identifier represents an offset into the value lookup table for identifying a particular entry thereat.

4. The method of claim 3, wherein each identifier comprises an integer value.

5. The method of claim 4, wherein each identifier comprises a relatively small integer value.

6. The method of claim 4, wherein each identifier comprises an integer value having a data width of about 8-32 bits.

7. The method of claim 6, wherein each identifier comprises an integer value having a data width which is more preferably about 8-16 bits.

8. The method of claim 6, wherein each identifier comprises an integer value having a data width which is most preferably about 8 bits.

9. The method of claim 1, wherein the data type for the particular column comprises an alphanumeric data type.

10. The method of claim 1, wherein the data type for the particular column comprises a text-based data type.

11. The method of claim 1, wherein said database table of interest employs column-based storage, such that data values of the particular column are stored on data pages which are separate from data pages employed for storing data values of other columns.

12. The method of claim 11, further comprising:

compressing the database table of interest by eliminating storage of said particular column.

13. The method of claim 1, further comprising:

determining the data value for a particular data record of the particular column by;

locating in the cell array a cell which corresponds to the particular record,

retrieving from the located cell a value lookup identifier stored thereat, and

determining the data value for the particular record by retrieving from the value lookup table the data value stored by an entry which is referenced by the retrieved identifier.

14. The method of claim 1, wherein each entry of the value lookup table further stores a reference count for indicating how many times the entry'"'"'s unique value occurs in the particular column being indexed.

15. The method of claim 14, further comprising:

removing from the value lookup table any entry whose reference count has reached zero.

16. The method of claim 1, further comprising:

receiving a request to insert new records into the particular column; and

as each new unique value is encountered in records being inserted, appending to the value lookup table an entry representing the new unique value encountered.

17. The method of claim 16, further comprising:

for each new record inserted, inserting into the cell array a new cell having an identifier which references an entry in the value lookup table which represents the data value for the new record at the particular column.

18. The method of claim 17, further comprising:

as each new cell array is inserted, setting the reference count of the entry in the value lookup table to represent that the entry is being referenced.

19. The method of claim 1, further comprising:

associating with at least one entry of the value lookup table a bitmap for indicating those records of the particular column which store the data value represented by said at least one entry.

20. The method of claim 1, wherein said value lookup table stores a number of unique entries on the order of less than or equal to about 256, and wherein each identifier comprises an integer having a data width of less than or equal to about 8 bits.

21. The method of claim 1, wherein each identifier comprises an integer having a data width which is a multiple of one byte.

22. The method of claim 1, further comprising:

receiving a request to insert new records, said new records having additional unique values which cannot be represented within the then-current value lookup table as a result of the then-current data width employed by the identifiers; and

accommodating the new unique values in the value lookup table by increasing the data width employed by the identifiers to a larger size.

23. The method of claim 22, wherein said identifiers are increased from a data width of about 8 bits to one of about 16 bits.

24. The method of claim 22, further comprising:

updating the cell array such that each cell stores an identifier employing the larger data width.

25. The method of claim 24, further comprising:

allocating additional resources for the value lookup table such that the value lookup table can accommodate additional new unique values.

26. A database system comprising:

a computer having a database storing information in at least one database table, each database table comprising data records for presenting information in row and column format, said at least one database table being stored in a row-ordered, column-based fashion; and

means for indexing a particular column from a database table of interest comprising by creating an index comprising a linear array of cells, said means including;

a value lookup table storing one entry for each distinct value present in the column of interest, and

means for representing each data value in the column of interest with a corresponding identifier stored in a corresponding cell of the linear array of cells which references an entry in the value lookup table corresponding to the data value being represented.

27. The system of claim 26, wherein each identifier represents an offset into the value lookup table for identifying a particular entry thereat.

28. The system of claim 26, wherein each identifier comprises an integer value.

29. The system of claim 26, wherein each identifier comprises a relatively small integer value.

30. The system of claim 26, wherein each identifier comprises an integer value having a data width of about 8-32 bits.

31. The system of claim 26, wherein each identifier comprises an integer value having a data width which is more preferably about 8-16 bits.

32. The system of claim 26, wherein each identifier comprises an integer value having a data width which is most preferably about 8 bits.

33. The system of claim 26, wherein the data type for the particular column comprises an alphanumeric data type.

34. The system of claim 26, wherein the data type for the particular column comprises a text-based data type.

35. The system of claim 26, wherein said database table of interest employs column-based storage, such that data values of the particular column are stored on data pages which are separate from data pages employed for storing data values of other columns.

36. 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 indexing columns of the database table comprising:

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 a particular column of a database table are all stored together in at least one data page associated with the particular column;

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; and

creating an index on at least one particular column comprising a linear cell array by;

constructing a list of distinct data values stored by said at least one particular column, and

substituting for each data value stored by said at least one particular column an identifier referencing an entry in said list having a data value equal to the data value being replaced.

37. The method of claim 36, wherein said index is a composite index derived from multiple columns.

38. The method of claim 36, wherein said at least one particular column stores data values in row-ordered fashion, and wherein said index comprises a cell array storing identifiers in a corresponding row-ordered fashion.

39. The method of claim 36, wherein each identifier represents an offset into the list for identifying a particular entry thereat.

40. The method of claim 39, wherein each identifier comprises an integer value.