Database management system with improved indexed accessing

• US 5,778,354 A
• Filed: 06/07/1995
• Issued: 07/07/1998
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Tandem Computers Incorporated (HP Inc.)
• Inventors: Birdsall, David W., Jain, Rohit N., Yaghmai, Hedieh, Leslie, Harry A.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/481,649
• Time in Patent Office: 1,126 Days
• Field of Search: 395/602, 395/603, 395/182.02, 395/200.03, 395/709, 395/705, 707/2, 707/3
• US Class Current: 707/715
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A database management system (DBMS) provided with a multi-dimensional improved indexed accessing capability using keyed index searching. Individual search keys are constructed from general expression statements created in the DBMS compiler from search queries supplied to the DBMS. Each key column represents another dimension, and both ranges and IN lists can be specified in the search query and used as the predicate values in multiple columns. Missing predicate values in the search query are interpreted as a specification of the minimum and maximum values for the associated search key column. During compile time, the DBMS compiler produces general expressions to be used by the DBMS executor during run time to create the search keys. The DBMS compiler evaluates search queries by associating predicates with clusters and disjunct numbers assigned to each individual disjunct in the search query expression. The DBMS executor uses the general expression from the compiler and eliminates any conflicts among same column predicates, removes redundancies in predicate values and disjuncts and reduces the number of records to be accessed to the minimum required to complete the search query. The individual search keys are generated in the same order as the index to which the search pertains (i.e., increasing or decreasing order).

Claims

1. A method of constructing search keys for searching a multi-column table in a database using search keys constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said method comprising the steps of:

(a) evaluating the predicate values corresponding to the values of the preselected columns of the table specified by the search query;

(b) for each predicate value specified as a range of values, assigning equivalent range values to the corresponding preselected column;

(c) for each predicate value specified as an IN list of values, assigning equivalent values to the corresponding preselected column;

(d) for each unspecified predicate value, assigning a range of values to the corresponding preselected column; and

(e) using the assigned equivalent values from steps (b)-(d) to construct individual search keys for searching the table;

wherein a search query includes a plurality of disjuncts; and

wherein said step (a) of evaluating includes the step of assigning a unique disjunct number to each of said plurality of disjuncts.

2. The method of claim 1 wherein said step of assigning disjunct numbers includes the step of assigning an individual disjunct number to an IN list predicate.

3. The method of claim 1 wherein said step (a) of evaluating includes the steps of associating predicates to clusters and associating clusters to disjunct numbers.

4. A method of constructing search keys for searching a multi-column table in a database using search keys constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said method comprising the steps of:

(a) evaluating the predicate values corresponding to the values of the preselected columns of the table specified by the search query;

(b) for each predicate value specified as a range of values, assigning equivalent range values to the corresponding preselected column;

(c) for each predicate value specified as an IN list of values, assigning equivalent values to the corresponding preselected column;

(d) for each unspecified predicate value, assigning a range of values to the corresponding preselected column; and

(e) using the assigned equivalent values from steps (b)-(d) to construct individual search keys for searching the table;

wherein said equivalent range values assigned in step (b) are specified as the lo and hi values of the corresponding preselected column.

5. A method of constructing search keys for searching a multi-column table in a database using search keys constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said method comprising the steps of:

(a) evaluating the predicate values corresponding to the values of the preselected columns of the table specified by the search query;

(b) for each predicate value specified as a range of values, assigning equivalent range values to the corresponding preselected column;

(c) for each predicate value specified as an IN list of values, assigning equivalent values to the corresponding preselected column;

(d) for each unspecified predicate value, assigning a range of values to the corresponding preselected column; and

(e) using the assigned equivalent values from steps (b)-(d) to construct individual search keys for searching the table;

wherein said step (e) of using includes the step of eliminating conflicting predicate values from the same column to reduce the number of potential predicate values for searching that column.

6. A method of constructing search keys for searching a multi-column table in a database using search keys constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said method comprising the steps of:

(a) evaluating the predicate values corresponding to the values of the preselected columns of the table specified by the search query;

(b) for each predicate value specified as a range of values, assigning equivalent range values to the corresponding preselected column;

(c) for each predicate value specified as an IN list of values, assigning equivalent values to the corresponding preselected column;

(d) for each unspecified predicate value, assigning a range of values to the corresponding preselected column; and

(e) using the assigned equivalent values from steps (b)-(d) to construct individual search keys for searching the table;

wherein said step (e) of using includes the step of eliminating redundant values specified by the disjuncts to minimize the number of search keys required to fulfill the search query.

7. A computer system for storing and providing user access to data in stored database objects, said system comprising:

a memory for storing said database objects;

a communications interface through which user database queries are relayed to said computer system from a user workstation, and through which query results from said computer system are made available to the user workstation;

a processor for controlling interactions between said memory and said communications interface in response to a search query received from a user workstation and specifying predicate values corresponding to values of preselected columns of a multi-column table;

a computer program for causing said processor to construct individual search keys in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said computer program including a first procedure for evaluating the predicate values specified by the search query;

a second procedure for assigning equivalent range values for each predicate value specified in the search query as a range of values, to the corresponding preselected column;

a third procedure for assigning equivalent values for each predicate value specified in the search query as an IN list of values, to the corresponding preselected column;

a fourth procedure for assigning a range of values to the corresponding preselected column for each unspecified predicate value; and

a fifth procedure for constructing individual search keys from the equivalent values assigned by the first through fourth procedures;

wherein a search query includes a plurality of disjuncts; and

wherein said first procedure causes said processor to assign a unique disjunct number to each of the plurality of disjuncts in the search query.

8. The system of claim 7 wherein the first procedure causes said processor to assign an individual disjunct number to an IN list predicate.

9. The system of claim 7 wherein the first procedure causes said processor to associate predicates to clusters and associate clusters to disjunct numbers.

12. A computer system for storing and providing user access to data in stored database objects, said system comprising:

a memory for storing said database objects;

a communications interface through which user database queries are relayed to said computer system from a user workstation, and through which query results from said computer system are made available to the user workstation;

a processor for controlling interactions between said memory and said communications interface in response to a search query received from a user workstation and specifying predicate values corresponding to values of preselected columns of a multi-column table;

a computer program for causing said processor to construct individual search keys in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said computer program including a first procedure for evaluating the predicate values specified by the search query;

a second procedure for assigning equivalent range values for each predicate value specified in the search query as a range of values, to the corresponding preselected column;

a third procedure for assigning equivalent values for each predicate value specified in the search query as an IN list of values, to the corresponding preselected column;

a fourth procedure for assigning a range of values to the corresponding preselected column for each unspecified predicate value; and

a fifth procedure for constructing individual search keys from the equivalent values assigned by the first through fourth procedures;

The system of claim 8 wherein the fifth procedure causes said processor to eliminate redundant values specified by the disjuncts in order to minimize the number of search keys required to fulfill the search query.

10. A computer system for storing and providing user access to data in stored database objects, said system comprising:

a memory for storing said database objects;

a communications interface through which user database queries are relayed to said computer system from a user workstation, and through which query results from said computer system are made available to the user workstation;

a processor for controlling interactions between said memory and said communications interface in response to a search query received from a user workstation and specifying predicate values corresponding to values of preselected columns of a multi-column table;

a computer program for causing said processor to construct individual search keys in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said computer program including a first procedure for evaluating the predicate values specified by the search query;

a second procedure for assigning equivalent range values for each predicate value specified in the search query as a range of values, to the corresponding preselected column;

a third procedure for assigning equivalent values for each predicate value specified in the search query as an IN list of values, to the corresponding preselected column;

a fourth procedure for assigning a range of values to the corresponding preselected column for each unspecified predicate value; and

a fifth procedure for constructing individual search keys from the equivalent values assigned by the first through fourth procedures;

wherein the equivalent range values assigned by the processor in response to the second procedure are specified as the lo and hi values of the corresponding predicate column.

11. A computer system for storing and providing user access to data in stored database objects, said system comprising:

a memory for storing said database objects;

a communications interface through which user database queries are relayed to said computer system from a user workstation, and through which query results from said computer system are made available to the user workstation;

a processor for controlling interactions between said memory and said communications interface in response to a search query received from a user workstation and specifying predicate values corresponding to values of preselected columns of a multi-column table;

a computer program for causing said processor to construct individual search keys in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, said computer program including a first procedure for evaluating the predicate values specified by the search query;

a second procedure for assigning equivalent range values for each predicate value specified in the search query as a range of values, to the corresponding preselected column;

a third procedure for assigning equivalent values for each predicate value specified in the search query as an IN list of values, to the corresponding preselected column;

a fourth procedure for assigning a range of values to the corresponding preselected column for each unspecified predicate value; and

a fifth procedure for constructing individual search keys from the equivalent values assigned by the first through fourth procedures;

wherein the fifth procedure causes said processor to eliminate conflicting predicate values from the same column to reduce the number of potential predicate values for searching that column.

13. A computer program product comprising a computer usable medium having computer readable code embodied therein for constructing individual search keys for searching a multi-column table in a database, the search keys being constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, the computer program product comprising:

first computer readable program code devices configured to cause a computer to evaluate the predicate values specified by the search query and corresponding to the values of the preselected columns of the table;

second computer readable program code devices configured to cause a computer to assign, for each predicate value specified as a range of values, equivalent range values to the corresponding preselected column;

third computer readable program code devices configured to cause a computer to assign, for each predicate value specified as an IN list of values, equivalent values to the corresponding preselected column;

fourth computer readable program code devices configured to cause a computer to assign, for each unspecified predicate value, a range of values to the corresponding preselected column; and

fifth computer readable program code devices configured to cause a computer to use said equivalent values to construct individual search keys;

wherein a search query includes a plurality of disjuncts; and

wherein said first computer readable program code devices are configured to cause a computer to assign a unique disjunct number to each of said plurality of disjuncts.

14. The computer program product of claim 13 wherein the computer is caused to assign an individual disjunct number to an IN list predicate.

15. The computer program product of claim 13 wherein said first computer readable program code devices are configured to cause the computer to associate predicates to clusters and clusters to disjunct numbers.

16. A computer program product comprising a computer usable medium having computer readable code embodied therein for constructing individual search keys for searching a multi-column table in a database, the search keys being constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, the computer program product comprising:

first computer readable program code devices configured to cause a computer to evaluate the predicate values specified by the search query and corresponding to the values of the preselected columns of the table;

second computer readable program code devices configured to cause a computer to assign, for each predicate value specified as a range of values, equivalent range values to the corresponding preselected column;

third computer readable program code devices configured to cause a computer to assign, for each predicate value specified as an IN list of values, equivalent values to the corresponding preselected column;

fourth computer readable program code devices configured to cause a computer to assign, for each unspecified predicate value, a range of values to the corresponding preselected column; and

fifth computer readable program code devices configured to cause a computer to use said equivalent values to construct individual search keys;

wherein the equivalent range values assigned by the computer in response to said second computer readable program code devices are specified as the lo and hi values of the corresponding predicate column.

17. A computer program product comprising a computer usable medium having computer readable code embodied therein for constructing individual search keys for searching a multi-column table in a database, the search keys being constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, the computer program product comprising:

first computer readable program code devices configured to cause a computer to evaluate the predicate values specified by the search query and corresponding to the values of the preselected columns of the table;

second computer readable program code devices configured to cause a computer to assign, for each predicate value specified as a range of values, equivalent range values to the corresponding preselected column;

third computer readable program code devices configured to cause a computer to assign, for each predicate value specified as an IN list of values, equivalent values to the corresponding preselected column;

fourth computer readable program code devices configured to cause a computer to assign, for each unspecified predicate value, a range of values to the corresponding preselected column; and

fifth computer readable program code devices configured to cause a computer to use said equivalent values to construct individual search keys;

wherein the fifth computer readable program code devices are additionally configured to cause the computer to eliminate conflicting predicate values from the same column to reduce the number of potential predicate values for searching that column.

18. A computer program product comprising a computer usable medium having computer readable code embodied therein for constructing individual search keys for searching a multi-column table in a database, the search keys being constructed in accordance with a search query specifying predicate values corresponding to values of preselected columns of the table, the search keys including names of the preselected columns of the table and associated predicate values, the computer program product comprising:

first computer readable program code devices configured to cause a computer to evaluate the predicate values specified by the search query and corresponding to the values of the preselected columns of the table;

second computer readable program code devices configured to cause a computer to assign, for each predicate value specified as a range of values, equivalent range values to the corresponding preselected column;

third computer readable program code devices configured to cause a computer to assign, for each predicate value specified as an IN list of values, equivalent values to the corresponding preselected column;

fourth computer readable program code devices configured to cause a computer to assign, for each unspecified predicate value, a range of values to the corresponding preselected column; and

fifth computer readable program code devices configured to cause a computer to use said equivalent values to construct individual search keys;

wherein said fifth computer readable program code devices are additionally configured to cause the computer to eliminate redundant values specified by the disjuncts to minimize the number of search keys required to fulfill the search query.