1. Field of the Invention
The present invention is directed to processing update and insert operations applied against a relational database.
2. Description of the Related Art
Many database systems implement a special program referred to as a “loader” to transfer large volumes of data into a database. A loader loads tables, enforces referential integrity, builds indexes, and maintains materialized views defined on the table. For example, one loader program is a Red Brick® Table Management Utility (TMU) for the IBM® Red Brick® Warehouse, a relational database optimized for dimensional analysis. For more information on the TMU, see the IBM® RedBrick® Table Management Utility (TMU) Reference Guide Version 6.2 available from International Business Machines Corporation.
UPSERT operations may be performed to load data (“input rows”) into a table. In a typical UPSERT operation, when an input row matches a primary key of an existing row in a table, that input row is designated as an update row and is used to update a matched existing row. When the input row has a new primary key, the input row is designated as an insert row and is inserted into the table. A primary key index entry is built for each input row that is inserted into the table. When the UPSERT operation is performed row by row for a set of input rows to be inserted into the table, with a primary key index entry built for each inserted row, the processing may become very slow due to the increased Input/Output (I/O) overhead for building each primary key index entry. For ease of reference, this row-by-row approach will be referred to herein as a “non-optimized UPSERT” operation.
An INSERT operation for an input row includes an insertion of the input row into a table, as well as, insertions into the indexes associated with that table. A non-optimized insertion would process input rows one by one, adding index entries one at a time. This causes random I/O access, which slows down the insert operation.
Instead of inserting index entries directly into an index, a technique (that will be referred to herein as an “optimized index inserting” technique for ease of reference) performs a delayed batch insertion. The optimized index inserting technique places new index entries, sorted in index primary key order, into, for example, a reserved memory area. These index entries may be referred to as “sorted index entries.” For optimized building of multiple indexes, possibly in parallel, there may be multiple such index batches in, for example, individual memory areas.
Once a sufficient batch of index entries is collected, the different batches are then merged into their respective indexes. For the optimized index inserting technique, since the index modification is in key order (not random), the overhead is very small. Each index is associated with an index tree. An enhanced merge technique may build mini-subtrees for the new index entries, which are then linked into the base index tree of the relevant index.
During the sort-merge operation, rows that violate the primary key constraint are identified, and are termed “duplicates.” In particular, when a set of input rows are being processed, if a first row with a first primary key is received for which the primary key is not found in an associated index, the first row is inserted into the table, without adding a primary key for the row into the associated index. Then, if a second row with the first primary key (i.e., the same primary key as the first row) is received, it is determined that the primary key is not found in the associated index, and the second row is inserted into the table. These batch-sort-merge cycles repeat until the input rows are exhausted. When processing of a set of input rows is done, the first row remains in the table, and any rows in the table with the same primary key are termed “duplicate input rows” or “input duplicates.” Then, the input duplicates are removed from the tables (because they were inserted into the tables already) along with any entries from corresponding non-unique indexes. The input duplicates may then be placed in a separate file (e.g., a “discard file” or a temporary discard table) for any investigations and/or processing desired by the user. That is, the optimized index inserting technique inserts the first row in a set of input duplicates and discards the remaining input duplicates.
Performance testing and customer feedback have indicated that the optimized index inserting technique, which is capable of being parallelized for multiple indexes, may be 20 times faster than a non-optimized index insertion.
Another technique will be referred to herein as an “optimized UPSERT” operation for ease of reference. The optimized UPSERT operation also improves the performance of UPSERT operations by performing index rebuilds for batches of inserted rows, rather than for each inserted row.
In particular, for optimized UPSERT operations, the input rows are a combination of new entries and updates to existing entries in a table. A lookup of the primary index is used to identify whether an input row is an insert (if no entries exist in the primary index) or whether its an update (if an entry already exists in the primary index). For a non-optimized UPSERT, all index entries are added or updated row by row, and no delayed batch indexing takes place.
For optimized UPSERT operations, if an input row is an update, indexes and the table data are immediately updated, and no delayed batching index building occurs. On the other hand, if the input row is identified as an insert row, the row data is inserted into the table immediately, but the index entries for insert rows are built with the optimized index inserting technique (i.e., the new index entries are added to a temporary index building space area and inserted into relevant indexes later as a batch operation).
The UPSERT operation observes the order of the input rows, i.e., for rows with the same primary key value, the values of the last such row are applied to the table last. This is to preserve the semantic of UPSERT operations that dictate that the later rows update previous data. A typical optimized UPSERT operation has a large percentage (e.g., 90%) of insertions and a smaller percentage of updates (e.g., 10%). The optimized UPSERT operation improves performance.
In optimized UPSERT operations, input duplicates, found during the sort-merge performed for the optimized index inserting for insert rows, are typically stored in discard files. However, the input duplicates are not really duplicates. Instead, the semantics of the input duplicates are very different than for simple INSERT operations. For optimized UPSERT operations, the input duplicates are updates to the previously inserted rows (i.e., “Updates to Inserts”).
FIG. 1 illustrates tables used in an example of an UPSERT operation. For ease of reference, a table holding input rows may be referred to herein as an input table, and a table to which the input rows are applied may be referred to herein as an output table. Output table 100 has two columns A and B, with column A representing the primary key and column B holding other data. Before an UPSERT operation is performed, there is one row in output table 100. Input table 110 lists input rows that are to be processed by an UPSERT operation, and table 120 lists how the optimized UPSERT operation and the non-optimized UPSERT operation would characterize each input row.
If a non-optimized UPSERT operation (i.e., row-by-row processing) is performed, input rows (1,2) and (1,3) have the primary key value 1, and, because there already is a row (1,1) in the table with primary key value 1, there is a primary key match for input rows (1,2) and (1,3). Thus, input rows (1,2) and (1,3) are identified as update rows and are processed to update the existing row (1,1) directly. Also, input row (2,2) would be identified as an insert, and a primary key index entry would be built immediately. Therefore, input row (2,4) would have been correctly identified as an update to the existing row (2,2). Input row (3,3) would be identified as an insert, since there are no existing rows in output table 100 with a primary key value of 3. Output table 140 illustrates the table after the non-optimized UPSERT operation has been performed.
On the other hand, an optimized UPSERT operation would identify input rows (2,2), (2,4) and (3,3) as inserts, since there are no existing rows in output table 100 with a primary key value of 2 or 3, and would identify input rows (1,2) and (1,3) as updates. Moreover, rows (2,2) and (2,4) both have the same primary key value 2, and would be identified as input duplicates by the optimized UPSERT operation. In particular, with the optimized UPSERT operation, since a primary key match for input row (2,2) would not have been found, the input row would be identified as an insert, and the primary key entry for input row (2,2) would be placed in, for example, a sorting memory area. When row (2,4) is encountered, since the building of index entries has been delayed, the index entry for (2,2) would not have been merged into the index yet, and input row (2,4 ) would also be categorized as an insert and put into the sorting area. The fact that input rows (2,2) and (2,4) are duplicates is found out either while sorting the index entries or while these index entries are merged into the index. Both these input duplicates are categorized as insert rows.
Thus, there is a change of semantics for input row (2,4). Input row (2,4) had been initially categorized as an insert row, rather than as an update row, by the optimized UPSERT operation. The optimized UPSERT operation discards the input duplicates, except for the last one. That is, the optimized index building for UPSERT operations would have retained the last input row and discarded the previous rows as duplicates to retain the semantics of an UPSERT (‘update’) where the last change is preserved. On the other hand, the optimized index inserting for INSERT operations would have retained the first input row and discarded the rest as duplicates. So, for this example, the last row (2,4) would have been inserted, and the previous row (2,2) would have been discarded to a discard file by the optimized UPSERT operation. Output table 130 illustrates the table after the non-optimized UPSERT operation has been performed.
Discard of duplicates may work for INSERT operations, but not for UPSERT operations, because the input duplicates are really “updates to inserts” in the optimized UPSERT operation. Mis-categorizing “updates to inserts” as inserts could actually cause semantically incorrect results in various situations.
For example, when a “RETAIN” operation is used for a column, if an input row is an update row, the RETAIN operator for a column indicates that the existing value for that column should be kept. If the input row is an insert row, the column default value is used. This is a practical feature in real life, for example, where the starting date on a customer record, needs to be retained (i.e. never updated). If for example, there had been a RETAIN operator on column B in output table 100 of FIG. 1, for input duplicates (2,2) and (2,4), the result would need to be (2,2), not (2,4). Categorizing (2,4) as an insertion would thus pick value 4 instead of 2 for column B, which would be an error.
Also, aggregation operators (e.g., ADD, MAX, MIN etc.) may be specified to cumulate the results of a particular column. One usage is to aggregate the sales column of several orders. Assuming, for example, that column B in output table 100 of FIG. 1, uses the ADD aggregation operator, input values for column B, would add to existing values of column B in output table 100. If the row is an insert row, the insert row is inserted and no ADD operation for this new value of column B takes place. If the input row is an update row, the input value is added to the existing column value in output table 100. The result of applying input rows (2,2) and (2,4) then should be (2,6), but with the optimized UPSERT operation, row (2,2) would have been rejected as a duplicate, and the result would be (2,4), which is incorrect.
Also, the optimized UPSERT operation may not process input duplicates correctly when complex expressions and/or conditions are to be processed. For instance, in some cases, inserts/updates may need to be performed when certain conditions are met, otherwise, the input row may be rejected. For example, a condition for an optimized UPSERT operation may be: “UPSERT those rows where the sum of the existing value of B and the input value of B does not exceed 5”. If the input row is an insert row, this condition is not applicable because an existing value for B does not exist, and the input row would be inserted into a table. If input row (2,4) of table 120 had been identified as an update row (e.g., as was the case for the non-optimized UPSERT operation) and input row (2,2) had been inserted into output table 100, then the sum of the input value of 4 and the value of column B of 2 would have been 6, and input row (2,4) would have been rejected, based on this condition. However, since input row (2,4) is identified as an insert row by the optimized UPSERT operation, this condition would not apply and input row (2,4) would not be rejected, which is again an incorrect choice.
There may be other errors possible with the optimized UPSERT operation when there are complex expressions used, involving the use of existing column data values and input values. In some cases, the column values themselves may be computed incorrectly. For example, for an expression such as “value for column B is the average of the existing value and the input row value,” mis-classification of a row as an input row could result in the wrong value being calculated for column B (e.g., the erroneous result row of(2,2) for the input row (2,4), instead of the correct row (2,3) (for an insert (2,2) and an update of (2,4)).
In addition, a SQL MERGE operation has been proposed and includes a WHEN MATCHED clause to differentiate the action on insert or update rows. The mis-categorization of a row, by a set based processing similar to the optimized UPSERT operation, would cause a wrong treatment of the input row. For more information on SQL MERGE, see, for example, Oracle 9i SQL Reference, Release 2 (9.2), Part Number A96540-02.
As a partial solution for the problem of discarded input duplicates, users may decide to manually reprocess the discard file of input duplicates through the non-optimized (row-by-row) UPSERT operation. Unfortunately, this reprocessing approach may not yield consistent results in all situations, especially when complex expressions and conditional evaluations are involved. Under those circumstances, users either need to deal with the inconsistency, or choose to use slower row-by-row non-optimized UPSERT operations.
Thus, although the optimized UPSERT operation is useful, there is a need in the art for improved processing of input duplicates.