Incremental maintenance of materialized views containing one-to-N lossless joins

Abstract

A method and apparatus are provided for performing incremental refreshes to materialized views defined by one-to-N lossless joins. Each base table of the materialized view is selected to be processed as the current "selected table". The processing of the current selected table varies depending on whether the selected table is the right side table of an outer join. If the selected table is not the right table of an outer join, then the selected table is processed by (1) deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during the batch window, and (2) inserting rows into the materialized view based on updates and inserts into the selected table that occurred during the batch window. If the selected table is the right table of an outer join, then changes made to the selected table are processed in a way that reduces the number of changes that have to be made to the materialized view. According to one embodiment of the invention, operations performed during the incremental refresh are performed by issuing database statements (e.g. SQL queries) to a database server. The incremental refresh techniques described herein are "memoryless" in that they do not require a record of the sequence of changes that were made during a batch window. Techniques are described for performing the incremental refresh steps through the use of database commands and queries.

Claims

What is claimed is:

1. A method for performing, after a batch window, an incremental refresh of a materialized view defined by a lossless one-to-n join, the method comprising the steps of:

establishing a base table of the materialized view as a selected table;

if the selected table is the right table of an outer join, then updating the materialized view to reflect deletions to the selected table by processing each row (Tj) that combines with a changed row in the selected table as follows

if Tj only combines in the materialized view with changed rows of the selected table, then the rows in the materialized view that contain Tj are removed from the materialized view and replaced with a row in which selected columns are set to NULL; and

if Tj combines in the materialized view with both changed and unchanged rows of the selected table, then the rows in the materialized view that result from Tj combining with changed rows are deleted, leaving only the rows in which Tj combines with unchanged rows of the selected table.

2. The method of claim 1 further comprising the steps of:

if the selected table is not the right table of an outer join, then performing the steps of

deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during the batch window; and

inserting rows into the materialized view based on updates and inserts into the selected table that occurred during the batch window.

3. The method of claim 1 further comprising the steps of:

if the selected table is the right table of an outer join, then updating the materialized view to reflect insertions to the selected table by performing the steps of

removing from the materialized view any rows that exist in the materialized view for rows from the left side of the outer join that, prior to the batch window, did not combine with any rows of the selected table but which, after the batch window, combine with at least one changed row of the selected table; and

inserting into the materialized view rows formed by combinations that result from the changed rows in the selected table.

4. The method of claim 1 wherein the step of replacing with a row in which selected columns are set to NULL includes replacing with a row in which columns corresponding to OJGraph(Ti), where Ti is the selected table.

5. The method of claim 1 wherein the step of updating the materialized view to reflect deletions to the selected table includes the step of setting to NULL selected columns of rows in the materialized view that are derived from rows in left side of the join (Tj) that join with exactly one row in the selected table that was deleted.

6. The method of claim 3 wherein the step of updating the materialized view to reflect insertions to the selected table includes the step of setting NULL values in selected columns of a particular set of rows in the materialized view to new values, where the particular set of rows includes those rows that are derived from rows in left side of the join (Tj) that join with exactly one changed row in the selected table.

7. The method of claim 1 wherein the step of updating the materialized view to reflect deletions to the selected table is performed by executing queries on tables.

8. The method of claim 1 further including the steps of:

storing change data that indicates changes made to base tables of the materialized view without tracking the order of the changes,

identifying a set of changed rows based on the change data, the set of changed rows including rows of the selected table that have been changed since a previous refresh operation;

performing the step of updating the materialized view based on the set of changed rows.

9. The method of claim 1 further comprising the steps of:

determining whether, during the batch window, the only changes made to the selected table were inserts; and

if the selected table is the right table of an outer join and the only changes made to the selected table during the batch window were inserts, then skipping the step of updating the materialized view to reflect deletions.

10. The method of claim 2 further comprising the steps of:

determining whether, during the batch window, the only changes made to the selected table were inserts; and

if the selected table is not the right table of an outer join and the only changes made to the selected table during the batch window were inserts, then skipping the step of deleting rows from the materialized view.

11. The method of claim 3 further comprising the steps of:

determining whether, during the batch window, the only changes made to the selected table were deletes or drop partitions; and

if the selected table is the right table of an outer join and the only changes made to the selected table during the batch window were deletes or drop partitions, then skipping the step of updating the materialized view to reflect insertions to the selected table.

12. The method of claim 1 wherein:

rowids from base tables of the materialized view are stored in the materialized view;

the rowids stored in the materialized view indicate the partitions to which corresponding rows base tables belong;

the method further includes the steps of

determining when the only change to the selected table during the batch window is that a partition was dropped;

inspecting the materialized view to identify rows of interest in the materialized view, said rows of interest being rows that include values from the dropped partition; and

deleting the rows of interest for an inner join.

13. The method of claim 1 wherein the materialized view includes a plurality of base tables, the method further comprising the steps of:

performing said incremental refresh operation by iteratively processing each of said plurality of base tables as said selected table;

detecting a crash during the incremental refresh operation prior to processing all of the plurality of base tables; and

after said crash, processing each base table again as said selected table without regard to whether the base table had been processed prior to said crash.

14. A method for performing, after a batch window, an incremental refresh of a materialized view defined by a lossless one-to-n join, the method comprising the steps of:

establishing a base table of the materialized view as a selected table;

if the selected table is the right table of an outer join, then updating the materialized view to reflect insertions to the selected table by performing the steps of

removing from the materialized view any rows that exist in the materialized view for rows from the left side of the outer join that, prior to the batch window, did not combine with any rows of the selected table but which, after the batch window, combine with at least one changed row of the selected table; and

inserting into the materialized view rows formed by combinations that result from the changed rows in the selected table.

15. The method of claim 14 further comprising the steps of:

if the selected table is not the right table of an outer join, then performing the steps of

deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during the batch window; and

inserting rows into the materialized view based on updates and inserts into the selected table that occurred during the batch window.

16. A computer-readable medium bearing instructions for performing an incremental refresh, after a batch window, of a materialized, lossless, one-to-n join view, the instructions including instructions for performing the steps of:

establishing a base table of the materialized view as a selected table;

if the selected table is the right table of an outer join, then updating the materialized view to reflect deletions to the selected table by processing each row (Tj) that combines with a changed row in the selected table as follows

if Tj only combines in the materialized view with changed rows of the selected table, then the rows in the materialized view that contain Tj are removed from the materialized view and replaced with a row in which selected columns are set to NULL; and

if Tj combines in the materialized view with both changed and unchanged rows of the selected table, then the rows in the materialized view that result from Tj combining with changed rows are deleted, leaving only the rows in which Tj combines with unchanged rows of the selected table.

17. The computer-readable medium of claim 16 further comprising instructions for performing the steps of:

if the selected table is not the right table of an outer join, then performing the steps of

deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during the batch window; and

inserting rows into the materialized view based on updates and inserts into the selected table that occurred during the batch window.

18. The computer-readable medium of claim 16 further comprising instructions for performing the steps of:

if the selected table is the right table of an outer join, then updating the materialized view to reflect insertions to the selected table by performing the steps of

removing from the materialized view any rows that exist in the materialized view for rows from the left side of the outer join that, prior to the batch window, did not combine with any rows of the selected table but which, after the batch window, combine with at least one changed row of the selected table; and

inserting into the materialized view rows formed by combinations that result from the changed rows in the selected table.

19. The computer-readable medium of claim 16 wherein the step of replacing with a row in which selected columns are set to NULL includes replacing with a row in which columns corresponding to OJGraph(Ti), where Ti is the selected table.

20. The computer-readable medium of claim 16 wherein the step of updating the materialized view to reflect deletions to the selected table includes the step of setting to NULL selected columns of rows in the materialized view that are derived from rows in left side of the join (Tj) that join with exactly one row in the selected table that was deleted.

21. The computer-readable medium of claim 18 wherein the step of updating the materialized view to reflect insertions to the selected table includes the step of setting NULL values in selected columns of a particular set of rows in the materialized view to new values, where the particular set of rows includes those rows that are derived from rows in left side of the join (Tj) that join with exactly one changed row in the selected table.

22. The computer-readable medium of claim 16 wherein the step of updating the materialized view to reflect deletions to the selected table is performed by executing queries on tables.

23. The computer-readable medium of claim 16 further including instructions for performing the steps of:

storing change data that indicates changes made to base tables of the materialized view without tracking the order of the changes,

identifying a set of changed rows based on the change data, the set of changed rows including rows of the selected table that have been changed since a previous refresh operation;

performing the step of updating the materialized view based on the set of changed rows.

24. The computer-readable medium of claim 16 further comprising instructions for performing the steps of:

determining whether, during the batch window, the only changes made to the selected table were inserts; and

if the selected table is the right table of an outer join and the only changes made to the selected table during the batch window were inserts, then skipping the step of updating the materialized view to reflect deletions.

25. The computer-readable medium of claim 17 further comprising instructions for performing the steps of:

determining whether, during the batch window, the only changes made to the selected table were inserts; and

if the selected table is not the right table of an outer join and the only changes made to the selected table during the batch window were inserts, then skipping the step of deleting rows from the materialized view.

26. The computer-readable medium of claim 18 further comprising instructions for performing the steps of:

determining whether, during the batch window, the only changes made to the selected table were deletes or drop partitions; and

if the selected table is the right table of an outer join and the only changes made to the selected table during the batch window were deletes or drop partitions, then skipping the step of updating the materialized view to reflect insertions to the selected table.

27. The computer-readable medium of claim 16 wherein:

rowids from base tables of the materialized view are stored in the materialized view;

the rowids stored in the materialized view indicate the partitions to which corresponding rows base tables belong;

the computer-readable medium further includes instructions for performing the steps of

determining when the only change to the selected table during the batch window is that a partition was dropped;

inspecting the materialized view to identify rows of interest in the materialized view, said rows of interest being rows that include values from the dropped partition; and

deleting the rows of interest for an inner join.

28. The computer-readable medium of claim 16 wherein the materialized view includes a plurality of base tables, the computer-readable medium further comprising instructions for performing the steps of:

performing said incremental refresh operation by iteratively processing each of said plurality of base tables as said selected table;

detecting a crash during the incremental refresh operation prior to processing all of the plurality of base tables; and

after said crash, processing each base table again as said selected table without regard to whether the base table had been processed prior to said crash.

29. A computer-readable medium comprising sequences of instructions for performing an incremental refresh, after a batch window, of a materialized view defined by a lossless one-to-n join, the computer-readable medium comprising instructions for performing the steps of:

establishing a base table of the materialized view as a selected table;

if the selected table is the right table of an outer join, then updating the materialized view to reflect insertions to the selected table by performing the steps of

removing from the materialized view any rows that exist in the materialized view for rows from the left side of the outer join that, prior to the batch window, did not combine with any rows of the selected table but which, after the batch window, combine with at least one changed row of the selected table; and

inserting into the materialized view rows formed by combinations that result from the changed rows in the selected table.

30. The computer-readable medium of claim 29 further comprising instructions for performing the steps of:

if the selected table is not the right table of an outer join, then performing the steps of

deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during the batch window; and

inserting rows into the materialized view based on updates and inserts into the selected table that occurred during the batch window.

31. A database system including:

a plurality of base tables;

a one-to-n lossless materialized join view derived from said base tables;

a mechanism for identifying changes that occur to said base tables during a batch window;

a database server configured to incrementally refresh said materialized view by performing the steps of:

establishing a base table of the materialized view as a selected table;

if the selected table is the right table of an outer join, then updating the materialized view to reflect deletions to the selected table by processing each row (Tj) that combines with a changed row in the selected table as follows

if Tj only combines in the materialized view with changed rows of the selected table, then the rows in the materialized view that contain Tj are removed from the materialized view and replaced with a row in which selected columns are set to NULL; and

if Tj combines in the materialized view with both changed and unchanged rows of the selected table, then the rows in the materialized view that result from Tj combining with changed rows are deleted, leaving only the rows in which Tj combines with unchanged rows of the selected table; and

if the selected table is not the right table of an outer join, then performing the steps of

deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during the batch window; and

inserting rows into the materialized view based on updates and inserts into the selected table that occurred during the batch window.

32. A database system including:

a plurality of base tables;

a one-to-n lossless materialized join view derived from said base tables;

a mechanism for identifying changes that occur to said base tables during a batch window;

a database server configured to incrementally refresh said materialized view by performing the steps of:

establishing a base table of the materialized view as a selected table;

if the selected table is the right table of an outer join, then updating the materialized view to reflect insertions to the selected table by performing the steps of

removing from the materialized view any rows that exist in the materialized view for rows from the left side of the outer join that, prior to the batch window, did not combine with any rows of the selected table but which, after the batch window, combine with at least one changed row of the selected table; and

inserting into the materialized view rows formed by combinations that result from the changed rows in the selected table; and

if the selected table is not the right table of an outer join, then performing the steps of

deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during the batch window; and

inserting rows into the materialized view based on updates and inserts into the selected table that occurred during the batch window.

Description

FIELD OF THE INVENTION

The present invention relates to database systems, and more specifically, to the maintenance of materialized views that contain one-to-n lossless joins.

BACKGROUND OF THE INVENTION

In a database management system (DBMS), data is stored in one or more data containers, each container contains records, and the data within each record is organized into one or more fields. In relational database systems, the data containers are referred to as tables, the records are referred to as rows, and the fields are referred to as columns. In object oriented databases, the data containers are referred to as object classes, the records are referred to as objects, and the fields are referred to as attributes. Other database architectures may use other terminology.

The present invention is not limited to any particular type of data container or database architecture. However, for the purpose of explanation, the examples and the terminology used herein shall be that typically associated with relational databases. Thus, the terms "table", "row" and "column" shall be used herein to refer respectively to the data container, record, and field.

Referring to FIG. 1, it illustrates two exemplary tables: table R (110) and table S (112). Table R has two columns, labeled "r.a" and "r.b", and table S has two columns labeled "s.a" and "s.c". To extract data from a table, users can issue queries that select columns from the table and, optionally, specify a criteria that determines which rows are to be retrieved. For example the SQL query "SELECT s.a from S WHERE s.b=2" requests the values from column s.a of table S for the rows in which the value in column s.b equals 2. In table S of FIG. 1, the only row that has the value 2 in the s.b column is row 124. Consequently, the query would cause the DBMS to return the value from the s.a column of row 124, which is 4.

For various reasons, it is not desirable for certain users to have access to all of the columns of a table. For example, one column of an employee table may hold the salaries for the employees. Under these circumstances, it may be desirable to limit access to the salary column to management, and allow all employees to have access to the other columns. To address this situation, the employees may be restricted from directly accessing the table. Instead, they may be allowed to indirectly access the appropriate columns in the table through a "view".

A view is a logical table. As logical tables, views may be queried by users as if they were a table. However, views actually present data that is extracted or derived from existing tables. Thus, problem described above may be solved by (1) creating a view that extracts data from all columns of the employee table except the salary column, and (2) allowing all employees to access the view.

A view is defined by metadata referred to as a view definition. The view definition contains mappings to one or more columns in the one or more tables containing the data. Typically, the view definition is in the form of a database query. Columns and tables that are mapped to a view are referred to herein as base columns and base tables of the view, respectively.

The data presented by conventional views is gathered and derived on-the-fly from the base tables in response to queries that access the views. That data gathered for the view is not persistently stored after the query accessing the view has been processed. Because the data provided by conventional views is gathered from the base tables at the time the views are accessed, the data from the views will reflect the current state of the base tables. However, the overhead associated with gathering the data from the base tables for a view every time the view is accessed may be prohibitive.

A materialized view, on the other hand, is a view for which a copy of the view data is stored separate form the base tables from which the data was originally gathered and derived. The data contained in a materialized view is referred to herein as ("materialized data"). Materialized views eliminate the overhead associated with gathering and deriving the view data every time a query accesses the view.

However, to provide the proper data, materialized views must be maintained to reflect the current state of the base tables. When the base tables of a materialized view are modified, computer resources must be expended to both determine whether the modifications require corresponding changes to the materialized data, and to make the required corresponding changes. Despite the high cost associated with maintaining materialized views, using a materialized view can lead to a significant overall cost savings relative to a conventional view when the materialized view represents a set of data that is infrequently changed but frequently accessed.

Views are often based on joins of two or more row sources. A join is a query that combines rows from two or more tables or views. A join is performed whenever multiple tables appear in a query's FROM clause. The query's select list can select any columns from any of the base tables listed in the FROM clause.

Most join queries contain WHERE clause conditions that compare two columns, each from a different table. Such a condition is called a join condition. To execute a join, the DBMS combines pairs of rows for which the join condition evaluates to TRUE, where each pair contains one row from each table.

To execute a join of three or more tables, the DBMS first joins two of the tables based on the join conditions comparing their columns and then joins the result to another table based on join conditions containing columns of the joined tables and the new table. The DBMS continues this process until all tables are joined into the result.

In addition to join conditions, the WHERE clause of a join query can also contain other conditions that refer to columns of only one table. These conditions can further restrict the rows returned by the join query.

An equijoin is a join with a join condition containing an equality operator. An equijoin combines rows that have equivalent values for the specified columns. Query1 is an equijoin that combines the rows of tables R and S where the value in column r.a is the same as the value in column s.a:

QUERY1

SELECT *

FROM R, S

WHERE r.a=s.a;

FIG. 2a is a block diagram of a materialized view (MV 202) whose view definition is Query1. MV 202 has two rows 204 and 206. Row 204 results from combining row 114 of table R with row 120 of table S. Row 206 results from combining row 116 of table R with row 122 of table S. Row 118 of table R does not combine with any row in table S because no row in table S has the value 3 in column s.a.

The join illustrated by Query1 is a "simple" or "inner" join. With an inner join, rows that do not satisfy the join condition are not reflected in the join result. For example, row 118 did not satisfy the join condition relative to any rows in table S, so row 118 is not reflected in the resulting materialized view 202. In contrast, an outer join returns all rows that satisfy the join condition and those rows from one table for which no rows from the other satisfy the join condition.

FIG. 2b is a block diagram illustrating a materialized view 250 that results from an outer join between tables R and S. Materialized views that are formed by joins, such as materialized views 202 and 250, are referred to herein as materialized join views. Query2 illustrates the outer join query that defines materialized view 250.

QUERY2

SELECT *

FROM R, S

WHERE r.a(+)=s.a;

Query2 differs from Query1 in that the inner join operator "=" has been replaced with the outer join operator "(+)=". The table listed on the (+) side of the outer join operator is referred to as the outer join table. In query2, table R is the outer join table. All of the rows in the outer join table are reflected in the results of an outer join, whether or not they satisfy the join criteria with any rows in the other join tables.

As illustrated in FIG. 2b, the materialized view 250 that results from the outer join includes rows 252 and 254 that are identical to rows 204 and 206 of materialized view 202, respectively. However, materialized view 250 further includes row 256 which was produced when row 118 of table R failed to satisfy the join conditions any row in table S.

As with all types of materialized views, the materialized join views must be maintained so that the data contained therein reflects the current state of the base tables. Changes made to any of the base tables may necessitate changes in the materialized join view. Changes made to the base tables may include, for example, the insertion of new rows, the deletion of existing rows, and the update of existing rows.

In general, there are two approaches to causing a materialized view to reflect changes made to its base tables. One approach, referred to as a total refresh, involves discarding the current materialized view data and recomputing the entire materialized view based on the current state of the base tables. The clear disadvantage of performing a total refresh is that the performance penalty associated with recomputing the join view every time a base table is updated may outweigh the performance benefit achieved for not having to recompute the view every time it is accessed.

The second approach for maintaining a materialized view is referred to herein as incremental maintenance. With incremental maintenance, the materialized view is not recomputed every time a base table is changed. Instead, the DBMS determines what changes, if any, have to be made to the materialized view data in order for the materialized view data to reflect the changes to the base tables. Incremental maintenance significantly reduces the overhead associated with maintaining a materialized view when, for example, changes to the base table only require the insertion or deletion of a single row within the materialized view.

Incremental maintenance can be either immediate or deferred. Immediate incremental maintenance requires the materialized join view to be updated to reflect a change to a base table immediately in response to the change is made to the base table. Deferred incremental maintenance allows changes to the base tables to be made over a period of time (a "batch window") without updating the materialized view. After the end of the batch window, the materialized view is updated to reflect all of the changes that were made during the batch window.

Deferred incremental maintenance of a materialized join view is difficult for a variety of reasons. First, changes may have occurred to more than one of the base tables of the materialized join view during the batch window. Second, the changes may take many forms, including insertions, deletions and updates. Third, the changes may have been made in a particular sequence that is critical to the effect of the changes. For example, a value in a base table may have been updated twice during the batch window. The sequence of the updates dictates that the value of the second update must be reflected in the materialized join view, not the value of the first update.

Based on the foregoing, it is clearly desirable to provide a method and system for performing incremental maintenance on a materialized join view. Specifically, it is desirable to provide a method and system for determining how a materialized join view should be updated in response to updates made to the base tables of the materialized join view. It is further desirable to provide a method for performing deferred incremental maintenance of materialized join views in a way that does not require a persistent tracking of the sequence of updates to the base tables. It is further desirable to provide a method for performing incremental maintenance of materialized join views that are defined by queries that contain outer joins.

SUMMARY OF THE INVENTION

A method and apparatus are provided for performing incremental refreshes to materialized views defined by one-to-N lossless joins. Each base table of the materialized view is selected to be processed as the current "selected table".

The processing of the current selected table varies depending on whether the selected table is the right side table of an outer join. If the selected table is not the right table of an outer join, then the selected table is processed by:

(1) deleting rows from the materialized view based on rows of the selected table that have been updated or deleted in the selected table during a batch window; and

(2) inserting rows into the materialized view based on updates and inserts into the selected table that occurred during a batch window.

If the selected table is the right table of an outer join, then deletions to the selected table are processed by processing each row (Tj) that combines with a changed row in the selected table according to the rules:

(1) if Tj only combines in the materialized view with changed rows of the selected table, then the rows in the materialized view that contain Tj are removed from the materialized view and replaced with a row in which selected columns are set to NULL; and

(2) if Tj combines in the materialized view with both changed and unchanged rows of the selected table, then the rows in the materialized view that result from Tj combining with changed rows are deleted, leaving only the rows in which Tj combines with unchanged rows of the selected table.

If the selected table is the right table of an outer join, then insertions to the selected table are performed by

(1) removing from the materialized view any rows that exist in the materialized view for rows from the left side of the outer join that, prior to the batch window, did not combine with any rows of the selected table but which, after the batch window, combine with at least one changed row of the selected table; and

(2) inserting into the materialized view rows formed by combinations that result from the changed rows in the selected table.

According to one embodiment of the invention, operations performed during the incremental refresh are performed by issuing database statements (e.g. SQL queries) to a database server.

The incremental refresh techniques described herein are "memoryless" in that they do not require a record of the sequence of changes that were made during a batch window. Techniques are described for performing the incremental refresh steps through the use of database commands and queries.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1 is a block diagram of two tables;

FIG. 2a is a block diagram of the result of an inner join on the tables illustrated in FIG. 1;

FIG. 2b is a block diagram of the result of an outer join on the tables illustrated in FIG. 1;

FIG. 3 is a block diagram of a computer system on which an embodiment of the invention may be implemented;

FIG. 4a is a block diagram of two base tables at time T1;

FIG. 4b is a block diagram of a materialized view defined by an outer join on the base tables in FIG. 4a at time T1;

FIG. 4c illustrates changes made to the tables in FIG. 4a during a batch period;

FIG. 5 is a flowchart that illustrates the steps involved in an incremental refresh operation according to one embodiment of the invention;

FIG. 6a is a block diagram of the tables from FIG. 4a at time T2, after the changes shown in FIG. 4c have been made;

FIG. 6b is a block diagram of the materialized view of FIG. 4b after it has been incrementally refreshed according to an embodiment of the invention; and

FIG. 7 is a flowchart that illustrates the steps for processing the right side of an outer join during an incremental refresh according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

A method and apparatus for performing deferred incremental maintenance of materialized join views is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

HARDWARE OVERVIEW

FIG. 3 is a block diagram that illustrates a computer system 300 upon which an embodiment of the invention may be implemented. Computer system 300 includes a bus 302 or other communication mechanism for communicating information, and a processor 304 coupled with bus 302 for processing information. Computer system 300 also includes a main memory 306, such as a random access memory (RAM) or other dynamic storage device, coupled to bus 302 for storing information and instructions to be executed by processor 304. Main memory 306 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 304. Computer system 300 further includes a read only memory (ROM) 308 or other static storage device coupled to bus 302 for storing static information and instructions for processor 304. A storage device 310, such as a magnetic disk or optical disk, is provided and coupled to bus 302 for storing information and instructions.

Computer system 300 may be coupled via bus 302 to a display 312, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device 314, including alphanumeric and other keys, is coupled to bus 302 for communicating information and command selections to processor 304. Another type of user input device is cursor control 316, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 304 and for controlling cursor movement on display 312. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

The invention is related to the use of computer system 300 for performing deferred incremental maintenance of materialized join views. According to one embodiment of the invention, deferred incremental maintenance of materialized join views is performed by computer system 300 in response to processor 304 executing one or more sequences of one or more instructions contained in main memory 306. Such instructions may be read into main memory 306 from another computer-readable medium, such as storage device 310. Execution of the sequences of instructions contained in main memory 306 causes processor 304 to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

The term "computer-readable medium" as used herein refers to any medium that participates in providing instructions to processor 304 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device 310. Volatile media includes dynamic memory, such as main memory 306. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus 302. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punchcards, papertape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave as described hereinafter, or any other medium from which a computer can read.

Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions to processor 304 for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 300 can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus 302. Bus 302 carries the data to main memory 306, from which processor 304 retrieves and executes the instructions. The instructions received by main memory 306 may optionally be stored on storage device 310 either before or after execution by processor 304.

Computer system 300 also includes a communication interface 318 coupled to bus 302. Communication interface 318 provides a two-way data communication coupling to a network link 320 that is connected to a local network 322. For example, communication interface 318 may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 318 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 318 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link 320 typically provides data communication through one or more networks to other data devices. For example, network link 320 may provide a connection through local network 322 to a host computer 324 or to data equipment operated by an Internet Service Provider (ISP) 326. ISP 326 in turn provides data communication services through the world wide packet data communication network now commonly referred to as the "Internet" 328. Local network 322 and Internet 328 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 320 and through communication interface 318, which carry the digital data to and from computer system 300, are exemplary forms of carrier waves transporting the information.

Computer system 300 can send messages and receive data, including program code, through the network(s), network link 320 and communication interface 318. In the Internet example, a server 330 might transmit a requested code for an application program through Internet 328, ISP 326, local network 322 and communication interface 318. In accordance with the invention, one such downloaded application provides for deferred incremental maintenance of materialized join views as described herein.

The received code may be executed by processor 304 as it is received, and/or stored in storage device 310, or other non-volatile storage for later execution. In this manner, computer system 300 may obtain application code in the form of a carrier wave.

TERMS AND NOTATION

For the purpose of explanation, the following terms and conventions are used herein to describe embodiments of the invention:

The notation "><" is used herein as an inner join operator. Thus, T1><T2 indicates an inner join between tables T1 and T2.

The notation ".fwdarw." is used herein as an outer join operator. Thus, T1.fwdarw.T2 indicates an outer join between tables T1 and T2, where table T1 is the outer table.

A join between T1 and T2 is referred to as a "lossless join" when all rows in T1 are reflected in the result of the join. The join that produced materialized view 202 is not a lossless join because row 118 of table R is not reflected in materialized view 202. The join that produced materialized view 250 is a lossless join because all of the rows of table R are reflected in materialized view 250. All outer joins are lossless joins by definition because all rows in the outer table of an outer join are always reflected in the result of the outer join.

A join between T1 and T2 is referred to as a "one-to-one join" when rows in T1 combine with no more than one row in T2. The joins that produced materialized views 202 and 250 are both one-to-one because no row in table R is joined to more than one row in table S. However, if for example table S had a row X where s.a equals 2 and s.c equals 7, then row 116 would combine with both that row X and row 122. Because table R would have a row that combined with more than one row from table S, a join between the two tables would not be a one-to-one join.

One way to ensure that ajoin between T1 and T2 will be one-to-one is to impose a uniqueness constraint on the join column of T2. If all values in the join column of T2 are unique, then no more than one row in T2 will have a value in its join column that matches any given value in the join column of T1.

A join between T1 and T2 is referred to as a "one-to-N join" when no constraints prevent rows in Ti from combining with more than one row in T2.

Based on the foregoing definitions, a join between T1 and T2 is a "one-to-N lossless join" when all rows of T1 are reflected in at least one row produced by the join.

The label "MV" is used to refer to a materialized join view. The query defining an MV has the form:

    ______________________________________
              MV: select
                <sel-cols>
               from
                T1, T2, T3, . . . , Tn
               where
                <join.sub.-- preds>
    ______________________________________

    ______________________________________
    Dlt.sub.-- Ti = select unique rid from SNLog.sub.-- Ti
           where
            scn > :Last.sub.-- Refresh.sub.-- SCN and
            scn < :Current.sub.-- Start.sub.-- SCN;
    ______________________________________

    ______________________________________
            VTi =select Ti.* from Ti, Dlt.sub.-- Ti
             where
              Ti.rowid = Dlt.sub.-- Ti.rid;
    ______________________________________

    ______________________________________
    Tmp.sub.-- mv = select rowid, Tj.sub.-- rid, Ti.sub.-- rid from MV
    where
    Ti.sub.-- rid in (select rid from Dlt.sub.-- Ti);
    ______________________________________

    ______________________________________
    * Create table Tmp.sub.-- mvcnt.sub.-- rids(Tj.sub.-- rid, count)
    Tmp.sub.-- mvcnt.sub.-- rids = select Tj.sub.-- rid, count(*) from MV
    where
    Tj.sub.-- rid in (select Tj.sub.-- rid from Tmp.sub.-- mv) and
    Ti.sub.-- rid not null
    group by Tj.sub.-- rid;
    ______________________________________

    ______________________________________
    * Create table Tmp.sub.-- cnt(Tj.sub.-- rid, dif, count)
    Tmp.sub.-- cnt = select a.Tj.sub.-- rid, (a.count-b.count), a.count
    from Tmp.sub.-- mvcnt.sub.-- rids a, (select Tj.sub.-- rid, count(*) from
    Tmp.sub.-- mv
    group by Tj.sub.-- rid)b
    where
    a.Tj.sub.-- rid = b.Tj.sub.-- rid;
    ______________________________________

    ______________________________________
     update MV
     set
    column-of(OJGraph(Ti)) = null
     where
    rowid in (select a.MV.sub.-- rid from Tmp.sub.-- mv a, Tmp.sub.-- cnt b
    where
    a.Tj.sub.-- rid = b.Tj.sub.-- rid and
    b.dif = 0   and
    b.count = 1;
    );
    ______________________________________

    ______________________________________
    delete from MV
    where
    rowid in (select a.MV.sub.-- rid from Tmp.sub.-- mv a, Tmp.sub.-- cnt b
    where
    a.Tj.sub.-- rid = b.Tj.sub.-- rid and
    b.count > 1;
    );
    ______________________________________

    ______________________________________
    insert into MV
    select a.mv-columns-of(.about.OJGraph(Ti)), (mv-columns-of(OJGraph(Ti)=
    null))
    from Tmp.sub.-- mv a, Tmp.sub.-- cnt b
    where
    a.Tj.sub.-- rid = b.Tj.sub.-- rid and
    b.dif =0    and
    b.count > 1;
    ______________________________________

    ______________________________________
    New.sub.-- mv = select <sel-cols> . . . with all Ti replaced by VTi
    from
    T1, T2, T3, . . . , Ti, . . . , Tn
    where
    <join-preds> ; . . . with all Ti replaced by VTi
    ______________________________________

    ______________________________________
    Tmp.sub.-- mv.sub.-- rids = select Tj.sub.-- rid from MV
    where
    Tj.sub.-- rid in (select Tj.sub.-- rid from New.sub.-- mv) and
    Ti.sub.-- rid not NULL
    ______________________________________

    ______________________________________
           * Create table Tmp.sub.-- newcnt(Tj.sub.-- rid, count)
            Tmp.sub.-- newcnt = select Tj.sub.-- rid, count(*)
            from New.sub.-- mv
             group by Tj.sub.-- rid;
    ______________________________________

    ______________________________________
    update MV
    (select
    mv-columns-of-OJGraph(Ti), columns-of(OJGraph(Ti))
    from
    MV, New.sub.-- mv, Tmp.sub.-- newcnt
    where
    Tmp.sub.-- newcnt.count=1 and
    Tmp.sub.-- newcnt.Tj.sub.-- rid not in (select Tj.sub.-- rid from
    Tmp.sub.-- mv.sub.-- rids)
    and
    New.sub.-- mv.Tj.sub.-- rid = Tmp.sub.-- newcnt.Tj.sub.-- rid and
    MV.Tj.sub.-- rid = New.sub.-- mv.Tj.sub.-- rid
    set
    mv-columns-of-OJGraph(Ti) = columns-of(OJGraph(Ti));
    ______________________________________

    ______________________________________
    delete from MV
    where
    MV.Tj.sub.-- rid in (select Tj.sub.-- rid from Tmp.sub.-- newcnt
            where
             Tmp.sub.-- newcnt.count>1 and
             Tmp.sub.-- newcnt.count.Tj.sub.-- rid not in
              (select Tj.sub.-- rid from Tmp.sub.-- mv.sub.-- rids)
           );
    ______________________________________

    ______________________________________
    insert into MV
    select New.sub.-- mv.* from New.sub.-- mv, Tmp.sub.-- newcnt
    where
           New.sub.-- mv.Tj.sub.-- rid= Tmp.sub.-- newcnt.Tj.sub.-- rid and
           Tmp.sub.-- newcnt.count > 1;
    ______________________________________

    ______________________________________
    insert into MV
    select
    <sel-cols>      . . . with all Ti replaced by VTi
    from
    VTi, T2, T3, . . . , Tn
    where
    <join-preds>;   . . . with all Ti replaced by VTi
    ______________________________________

    ______________________________________
    Dlt.sub.-- X = select unique rid from SNLog.sub.-- X
           where
            scn > :T1 and
            scn < :T2;
    ______________________________________

    ______________________________________
             VX =select X.*from X, Dlt.sub.-- X
              where
               X.rowid = Dlt.sub.-- X.rid;
    ______________________________________

    ______________________________________
               insert into MV
               select
                 *
               from
                VX, Y
               where VX.a(+)=y.a
    ______________________________________

    ______________________________________
    Dlt.sub.-- Y = select unique rid from SNLog.sub.-- Y
           where
            scn > :T1 and
            scn < :T2;
    ______________________________________

    ______________________________________
            VY =select Y.*from Y, Dlt.sub.-- Y
             where
              Y.rowid = Dlt.sub.-- Y.rid;
    ______________________________________

    ______________________________________
    * Create table Tmp.sub.-- mvcnt.sub.-- rids(X.sub.-- rid, count)
    Tmp.sub.-- mvcnt.sub.-- rids = select X.sub.-- rid, count(*) from MV
    where
    X.sub.-- rid in (select X.sub.-- rid from Tmp.sub.-- mv)and
    Y.sub.-- rid not null
    group by X.sub.-- rid;
    ______________________________________

    ______________________________________
    * Create table Tmp.sub.-- cnt(X(.sub.-- rid, dif, count)
    Tmp.sub.-- cnt = select a.X.sub.-- rid, (a.count-b.count), a.count
    from Tmp.sub.-- mvcnt.sub.-- rids a, (select X.sub.-- rid, count(*)
            from Tmp.sub.-- mv
              group by X.sub.-- rid) b
    where
    a.X.sub.-- rid = b.X.sub.-- rid;
    ______________________________________

    ______________________________________
    update MV
    set
    columns-of(OjGraph(Y)) = null
    where
    rowid in (select a.MV.sub.-- rid from Tmp.sub.-- mv a, Tmp.sub.-- cnt b
    where
            a.X.sub.-- rid = b.X.sub.-- rid and
            b.dif = 0
                   and
            b.count = 1;
    );
    ______________________________________

    ______________________________________
    delete from MV
    where
    rowid in (select a.MV.sub.-- rid from Tmp.sub.-- mv a, Tmp.sub.-- cnt b
            where
             a.X.sub.-- rid = b.X.sub.-- rid and
             b.count > 1;
    );
    ______________________________________

    ______________________________________
    insert into MV
    select a.mv-columns-of(.about.OJGraph(Y)),
    (mv-columns-of(OJGraph(Y)=null))
    from Tmp.sub.-- mv a, Tmp.sub.-- cnt b
    where
    a.X.sub.-- rid = b.X.sub.-- rid and
    b.dif = 0    and
    b.count > 1;
    ______________________________________

    ______________________________________
    Tmp.sub.-- mv.sub.-- rids = select X.sub.-- rid from MV
    where
    X.sub.-- rid in (select X.sub.-- rid from New.sub.-- mv) and
    Y.sub.-- rid not NULL
    ______________________________________

    ______________________________________
    * Create table Tmp.sub.-- newcnt(X.sub.-- rid, count) gives the number of
    times
    a X row is in New.sub.-- mv.
    Tmp.sub.-- newcnt = select X.sub.-- rid, count(*)
    from New.sub.-- mv
    group by X.sub.-- rid;
    ______________________________________

    ______________________________________
    update MV
    (select
    mv-columns-of-OJGraph(Y), columns-of(OJGraph(Y))
    from
    MV, New.sub.-- mv, Tmp.sub.-- newcnt
    where
    Tmp.sub.-- newcnt.count=1 and
    Tmp.sub.-- newcnt.X.sub.-- rid not in (select X.sub.-- rid from
    Tmp.sub.-- mv.sub.-- rids) and
    New.sub.-- mv.X.sub.-- rid = Tmp.sub.-- newcnt.X.sub.-- rid and
    MV.X.sub.-- rid = New.sub.-- mv.X.sub.-- rid
    set
    mv-columns-of-OJGraph(Y) = columns-of(OJGraph(Y));
    ______________________________________

    ______________________________________
    delete from MV
    where
    MV.X.sub.-- rid in (select X.sub.-- rid from Tmp.sub.-- newcnt
    where
    Tmp.sub.-- newcnt.count>1 and
    Tmp.sub.-- newcnt.count.X.sub.-- rid not in
              (select X.sub.-- rid from Tmp.sub.-- mv.sub.-- rids)
    );
    ______________________________________

    ______________________________________
    insert into MV
    select New.sub.-- mv.* from New.sub.-- mv, Tmp.sub.-- newcnt
    where
    New.sub.-- mv.X.sub.-- rid = Tmp.sub.-- newcnt.X.sub.-- rid and
    Tmp.sub.-- newcnt.count > 1;
    ______________________________________

• Inventors
  Witkowski, Andrew; Dias, Karl;
• Assignee
  Oracle Corporation (Redwood Shores, CA)
• Published
  Sep-26-2000
• Current US Classes:
  707/102
  707/103R
  707/2
  707/4
  707/6
• Application #
  109115
• International Classes
  G06F 017/30
• Field of Search
  707/2-4 707/6-7 707/10 707/102 707/103 705/26-27 705/34 706/16 709/204 717/2
• Examiner
  Alam; Hosain T.
• Agent
  Palermo; Hickman Truong & Becker, LLP, Hickman; Brian D.
• US Patent References:
  5584024
  5812840
  5970482
  5974407
  5991754