It might seem that a bi-temporal database will have a lot more data in it than a conventional database, and will consequently take a lot longer to process. It is true that the size of a bi-temporal database will be larger than that of an otherwise identical database which contains only current data about persistent objects. But in our consulting engagements, which span several decades and dozens of clients, we have found that in most mission-critical systems, temporal data is jury-rigged into ostensibly non-temporal databases.

There are any number of ways that this may happen. For example, in some systems a version date is added to the primary key of selected tables. In other systems, more advanced forms of best practice versioning (as described in Chapter 4) are employed. Sometimes, history will be captured by triggering an insert into a history table every time a particular non-temporal table is modified. Another approach is to generate a series of periodic snapshot tables that capture the state of a non-temporal table at regular intervals.

Of course, a database with no temporal data at all will certainly be smaller than the same database with temporal data. But adding up the overhead associated with embedded best practice versioning, or with triggered history, periodic snapshots or some combination of these and other techniques, the amount of data in a so-called non-temporal database may be as much or even more than the amount of data in a bi-temporal database.

Throughout this book, we have been using the terms “non-temporal database” and “conventional database” as equivalent expressions. But now we have a reason to distinguish them. From now on, we will call a database “non-temporal” only if it contains no temporal data about persistent objects at all. ¹ And from now on, we will use the term “conventional database” to refer to databases that may or may not contain temporal data about persistent objects (and that usually do), but that do not contain explicitly bi-temporal tables and instead incorporate temporal data by using variations on one or more of the ad hoc methods we have described.

At the level of individual tables, a table lacking temporal data will clearly have less data than an otherwise identical table that also contains temporal data. But even if a table has more data than another table, it may perform nearly as well as that other table because response times are usually not linear to the amount of data in the target table.

Response times will be approximately linear to the amount of data in the table in the case of full table scans, but will almost never be linear for direct access reads. A direct (random) read to a table with five million rows will perform almost as well as a direct read to a table with only one million rows, provided that the table is indexed properly and that the number of non-leaf index levels is the same. And, in most cases, they will be the same, or very close to it.

In addition, when adding in the overhead of triggers of an exponentially growing number of dependents, and of the often inefficient SQL used to access and maintain data in conventional databases, it is likely that using the AVF to manage temporal data in an Asserted Versioning database will prove to be a more efficient method of managing temporal data than directly invoking DBMS methods to manage temporal data in a conventional database.

The physical sequence of columns within an index has a significant impact on the performance of queries that use that index. Our objective is to get to the desired row in a table with the minimum amount of I/O activity against the index, followed by a single direct read to the table itself. So in determining the sequence of columns in an index, a good idea is to put the most frequently used lookup columns in the leftmost (initial) nodes of the index. These columns are often the columns that make up the business key, or perhaps some other identifier such as the primary key, or a foreign key.

Against asserted version tables, most queries will be similar to queries against non-temporal tables except that a few temporal predicates will be added to the queries. These temporal predicates eliminate rows whose assertion time periods and/or effective time periods are not what the query is looking for.

An object that is represented by exactly one row in a non-temporal table may be represented by any number of rows in a temporal table. But for normal business use, the one current row in the temporal table, i.e. the row which corresponds to that one row in the non-temporal table, is likely to be accessed much more frequently than any of the other rows. Unless we properly combine temporal columns with non-temporal columns in the index, access to that current row may require us to scan through many past or future rows to get to it.

Of course, we are talking about both a scan of index leaf pages, as well as the more expensive scan of the table itself. When specific rows are being searched for, and when they may or may not be clustered close to one another in physical storage, we want to minimize any type of scan.

Another important consideration in determining the optimal sequence of columns in an index is that optimizers may decide not to use a column in an index unless values have been provided for all the columns to its left, those being the columns that help to more directly trace a path through the higher levels of the index tree, using the columns that match supplied predicates. So if we design an index with its temporal columns too far to the right, and with unqualified columns prior to them, a scan might still be triggered whenever the optimizer looks for the one current row for the object being queried. On the other hand, as we will see, the solution is not to simply make the temporal columns left-most in the index.

There will usually be many more non-current rows for an object, in an asserted version table, than the one current row for that object. The table may contain any number of rows representing the history of the object, and any number of rows representing anticipated future states of the object. The table may contain any number of no longer asserted rows for that object, as well as rows that we are not yet prepared to assert. So what we want the optimizer to do is to jump as directly as possible to the one currently asserted current version for an object, without having to scan though a potentially large number of non-current rows.

Let's look at an example. We will assume that it is currently September 2011. So the next time the clock ticks, according to the clock tick granularity used in this book, it will be October 2011.

In the table shown in Figure 15.1, there are nine rows representing the object whose object identifier is 55. Three of those rows are historical versions. Their effectivity periods are past. They represent past states of the object they refer to. We designate them with “pe” (past effective) in the state column of the table. ²

Another three of those rows are no longer asserted. Their assertion periods are past. They represent claims that we once made, claims that the statements which those rows made about the objects which they represented were true statements. But now we no longer make those claims. They exist in the assertion time past. We designate these rows with “pa” (past asserted) in the state column of the table.

Two of those rows are not yet asserted. They are deferred assertions. We are not yet willing to claim that the statements made by those rows are true statements. We designate these rows with “fa” (future asserted) in the state column of the table.

There is one current row representing the object whose identifier is 55. This row is currently asserted and, within current assertion time, became effective in August 2009 and will remain in effect until further notice. Note, however, that it will remain asserted only until October 2012. At that time, if nothing in the data changes, the database will cease to say that the data for object 55 is Kiwi from August 2009 until further notice. Instead, it will say that data for object 55 is Kiwi from August 2009 to December 2013, and that from December 2013 until further notice, it will be Grapes. We designate this earlier, but current, row with “cc” (currently asserted current version) in the state metadata column of the table.

The SQL to retrieve the one current row for object 55 is:

Most optimizers will use the index tree to locate the row id (rid) of the qualifying row or rows using, first of all, the columns that have direct matching predicates, such as EQUALS or IN, columns which are sometimes called match columns. These optimizers will also use the index tree for a column with a range predicate, such as BETWEEN or LESS THAN OR EQUAL TO (<=), provided that it is the first column in the index or the first column following the direct match columns.

Together, the direct match predicates and the first range predicate determine a starting position for a search of the index, that position being the first value found within the range specified on the first range predicate. And because of the match columns to the left of that first range column in the index, that first range predicate will direct us to the branch of the index tree where all the leaf node pointers point to rows in the target table which satisfy those match predicates as well that first range predicate. The most important thing to note here is that we get to this starting point in the search of the index without doing a scan. Our strategy is to get to the desired result using an index with little or no scanning.

Once we reach that starting point, all of the entries matching both the direct match predicates and also that first range predicate will be scanned. For all rows qualified by that scan, each of them will be scanned by the remaining predicates in the index. The index entries get narrowed down to a small set of pointers to all the rows in the table which match those search criteria whose columns appear on that index.

After the index scan is exhausted, it may still be necessary to scan the table itself. Although our goal is to have no scans at all, it isn't always possible to completely avoid them. Frequency of reads and updates, and other conditions, also need to be considered.

This is why the sequence of columns in an index is so important. Most important of all is to choose the correct range predicate column to place immediately after the common match predicate columns. To put the same point in other words: most important of all is to get positioned into the index for the desired row without resorting to scanning.

Suppose that the sequence of columns in the index is {oid, eff_beg_dt, asr_beg_dt}. In this case, using Figure 15.1, the optimizer will match on the 55, and then apply the less than or equal to predicate to the second indexed column, eff_beg_dt. If the current date is September 2011, there are eight rows where eff_beg_dt is less than or equal to the current date. So those eight rows will be scanned, and after that the other criteria will be applied while being scanned. Is this the best sequence of columns for this index, given that most queries will be looking for the one current row for an object, lost in a forest of non-current assertions and/or non-current versions for that same object?

In this proposed sequence of columns, the effective begin date immediately follows the match columns, and the next column is the assertion begin date. So after matching, and then filtering on effective begin date, the index will be scanned for the remaining criteria including assertion begin date. And the same eight rows will be qualified by that scan. Finally, the DBMS will use the row ids (rids) of the qualifying rows, and read the table itself. If the table is physically clustered on exactly this sequence of columns, we might get all eight rows in one I/O. On the other hand, in the worst case, it would require eight I/Os just to find the one current row. Since physical I/Os are one of the main causes of performance problems, reducing them is one of our main opportunities for optimization. And this particular sequence of index columns doesn't seem to do a good job in reducing I/O, either in the index or in the table itself.

Since there are probably more rows for object 55's past than for its future, we might consider reversing the sort order on the effective begin date index column, and make it descending instead of ascending. But even with a descending sort order, there are still the same eight rows that qualify and need further filtering. In fact, most rows in a temporal database usually have an effective begin date less than Now(). So effective begin date does not appear to be a good column to place immediately after the last match column in the index.

Another approach is to put all four temporal columns in the index. This might improve things, but it also has serious flaws. One problem is that some optimizers might ignore columns if the earlier columns do not match with EQUALS predicates (e.g. List Prefetch in earlier versions of DB2). And even if these four columns are used by the optimizer, an index scan may still be needed. Index performance for asserted version tables is most strongly affected by the one temporal column in the index that follows immediately after the match columns.

As we have now seen, effective begin date is not a good choice for that column position. Neither is assertion begin date, and for much the same reasons, as almost all rows have an assertion begin date earlier than the assertion begin date on the most frequently retrieved row, the current row for the object.

There are two remaining candidates for the column position that immediately follows the match columns: effective end date and assertion end date. In the table in Figure 15.1, there are the same number of rows with an assertion end date greater than Now() as there are rows with an effective end date greater than Now(). The ratio is determined by the number of updates to open-ended versions (ones with 12/31/9999 effective end dates) compared to the number of versions created with known effective end dates.

For example, a policy might have a known effective end date when it is created, whereas a client would normally not have one. So for a policy table, there would be fewer rows with an effective end date greater than Now(), because there would be fewer rows with a 12/31/9999 effective end date to withdraw into past assertion time. For a client table, it would be a toss-up. Since one withdrawn row is created for every temporal update, the number of rows for that object with an assertion end date greater than Now(), and the number of rows with an effective end date greater than Now() would tend to be roughly equal.

There is also an update performance issue with including the assertion end date anywhere in the index. Every time an episode is updated, a currently asserted row is withdrawn; and so its assertion end date is changed. This would require an update to the index, if the assertion end date is in that index; and it would happen every time a temporal update or a temporal delete is processed. By leaving the assertion end date out of the index, these frequent updates will not affect the index.

By a process of elimination, we have come to {oid, eff_end_dt} as the sequence of columns that will best optimize the performance of queries looking for the currently asserted current versions of objects. In this case, the optimizer will match on the 55, and then apply the GREATER THAN predicate to the second indexed column, eff_end_dt such as “eff_end_dt > Now()”. But for tables whose updates usually result in a version with a 12/31/9999 effective end date, the effective end date will not separate the currently asserted current version from the withdrawn versions for the same object. The best way to do that is to add the assertion end date as the last column in the index, giving us {oid, eff_end_dt, asr_end_dt}. Even though it will require an index scan to filter the assertions, doing so will often reduce the number of I/Os to the main table.

As we noted earlier, however, the assertion end date is updated every time a temporal update is carried out. It is updated as the then-current row is withdrawn into past assertion time, making room for the row or rows that replace it, or else replace and supercede it. So these physical updates will require a physical update to the corresponding index entry as well.

The decision of whether or not to include the assertion end date in an index designed to optimize access to the currently asserted current versions of objects, therefore, requires careful analysis of the specific situation. For policies and similar kinds of entities, where the effective end dates are usually known in advance, most withdrawn assertions will have an effective end date less than that of the currently asserted current version for the policy. This means that there is less need for the assertion end date in the index. But for clients and similar kinds of entities, where the effective end dates are usually not known in advance, many withdrawn assertions will contain an effective end date equal to that of the currently asserted current version, specifically the 12/31/9999 effective end date. This means that there is greater need for the assertion end date in the index, to push all those past assertions aside and allow us to get to the currently asserted current version more directly.

Generalizing from this specific case, our conclusion is that the sequence of columns for an asserted version table should begin with the match predicates for that table, starting with the most frequently used ones. After that, the effective end date should be the next column in the index. For tables in which most rows are created with a known (non-12/31/9999) effective end date, nothing else is needed in the index. But for tables in which most rows are created with a 12/31/9999, “until further notice”, effective end date, we recommend that the assertion end date be added to the index, right after the effective end date.

Temporal referential integrity (TRI) is enforced in two directions. On the insert or temporal expansion of a child managed object, or on a change in the parent object designated by its temporal foreign key, we must insure that the parent object is present in every clock tick in which the child object is about to be present. On the deletion or temporal contraction of a parent managed object, we must RESTRICT, CASCADE or SET NULL that transformation so that it does not leave any “temporal orphans” after the transaction is complete.

In this section, we will discuss the performance considerations involved in creating indexes that support TRI checks on both parent and child managed objects.

Even if Asserted Versioning did not support logical gap versioning, we would keep both effective end dates and assertion end dates in the Asserted Versioning bi-temporal schema. The reason is that, without them, most accesses to these tables would require finding the MAX(dt) of the designated object in assertion time, or in effective time within a specified period of assertion time. The performance problem with a MAX(dt) is that it needs to be evaluated for each row that is looked at, causing performance degradation exponential to the number of rows reviewed.

Experience with the AVF and our Asserted Versioning databases has shown us that eliminating MAX(dt) subqueries and having effective and assertion end dates on asserted version tables, dramatically improves performance.

Some readers might wonder why we do not use nulls to stand in for unknown future dates, whether effective end dates or assertion end dates. From a logical point of view, NULL, which is a marker representing the absence of information, is what we should use in these date columns whenever we do not know what those future dates will be.

But experience with the AVF and with Asserted Versioning databases has shown that using real dates rather than nulls helps the optimizer to consistently choose better, more efficient access paths, and matches on index keys more directly.

Without using NULL, the predicate to find versions that are still in effect is:

Using NULL, the semantically identical predicate is:

The OR in the second example causes the optimizer to try one path and then another. It might use index look-aside, or it might scan. Either of these is less efficient than a single GREATER THAN comparison.

Another considered approach is to coalesce NULL and the latest date recognizable by the DBMS, giving us the following predicate:

But functions normally cannot be resolved in standard indexes, and so the COALESCE function will normally cause a scan. Worse yet, some DBMSs will not resolve functions until all data is read and joined. So frequently, a lot of extra data will be assembled into a preliminary result set before this COALESCE function is ever applied.

The last of our three options is a simple range predicate (such as GREATER THAN) without an OR, and without a function. If the end date is unknown, and the value we use to represent that unknown condition is the highest date (or timestamp) which the DBMS can recognize, then this simple range predicate will return the same results as the other two predicates. And given that the highest date a DBMS can recognize is likely to be far into the future, it is unlikely that business applications will ever need to use that date to represent that far-off time. In SQL Server, for example, that highest date is 12/31/9999. So as long as our business applications do not need to designate that specific New Year's Eve nearly 8000 years from now, we are free to use it to represent the fact that a value is unknown. Using it, we can use the simple range predicate shown earlier in this section, and reap the benefits of the excellent performance of that kind of predicate.

Another technique that can help with performance and database maintenance, such as backups, recoveries and reorganizations, is partitioning. There are several basic approaches to partitioning.

One is to partition by a date, or something similar, so that the more current and active data is grouped together, and is more likely to be found in cache. This is a common partitioning strategy for on-line transaction processing systems.

Another is to partition by some known field that could keep commonly accessed smaller groups of data together, such as a low cardinality foreign key. The benefit of this approach is that it directs a search to a small well-focused collection of data located on the same or on adjacent I/O pages. This strategy improves performance by taking advantage of sequential prefetch algorithms.

A third approach is to partition by some random field to take advantage of the parallelism in data access that some DBMSs support. For these DBMSs, the partitions define parallel access paths. This is a good strategy for applications such as reporting and business intelligence (BI) where typically large scans could benefit from the parallel processing made possible by the partitioning.

Some DBMSs require that the partitioning index also be the clustering index. This limits options because it forces a trade-off between optimizing for sequential prefetch and optimizing for parallel access. Fortunately, DBMS vendors are starting to separate the implementation of these two requirements.

Another limitation of some DBMSs, but one that is gradually being addressed by their vendors, is that whenever a row is moved between partitions, those entire partitions are both locked. This forces application developers to design their processes so that they never update a partitioning key value on a row during prime time, because doing so locks the source and destination partitions until the move is complete. As we noted, more recent releases of DBMSs reduce the locking required to move a row from one partition to another.

A good partitioning strategy for an Asserted Versioning database is to partition by one of the temporal columns, such as the assertion end date, in order to keep the most frequently accessed data in cache. As we have pointed out, that will normally be currently asserted current versions of the objects of interest to the query.

For an optimizer to know which partition(s) to access, it needs to know the high order of the key. For direct access to the other search criteria, it needs direct access to the higher nodes in the key, higher than the search key. Therefore, while one of the temporal dates is good for partitioning, it reduces the effectiveness of other search criteria. To avoid this problem, we might want to define two indexes, one for partitioning, and another for searching.

The better solution for defining partitions that optimize access to currently asserted versions is to use the circa flag as the first column in the partitioning index. The best predicate would be {circa_asr_flag = ‘Y’} for current assertions. For DBMSs which support index-look-aside processing for IN predicates, the best predicate might be {circa_asr_flag IN (‘Y’, ‘N’)} when it is uncertain if the version is currently asserted. With this predicate, the index can support searches for past assertions as well as searches for current ones. Otherwise, it will require a separate index to support searches for past assertions.

Clustering and partitioning often go together, depending on the reason for partitioning and the way in which specific DBMSs support it. Whether or not partitioning is used, choosing the best clustering sequence can dramatically reduce I/O and improve performance.

The general concept behind clustering is that as the database is modified, the DBMS will attempt to keep the data on physical pages in the same order as that specified in the clustering index. But each DBMS does this a little differently. One DBMS will cluster each time an insert or update is processed. Another will make a valiant attempt to do that. A third will only cluster when the table is reorganized. But regardless of the approach, the result is to reduce physical I/O by locating data that is frequently accessed together as physically close together as possible.

Early DBMSs only allowed one clustering index, but newer releases often support multiple clustering sequences, sometimes called indexed views or multi-dimensional clustering.

It is important to determine the most frequently used access paths to the data. Often the most frequently used access paths are ones based on one or more foreign keys. For asserted version tables, currently asserted current versions are usually the most frequently queried data.

Sometimes, the right combination of foreign keys can provide good clustering for more than one access path. For example, suppose that a policy table has two low cardinality TFKs, product type and market segment, and that each TFK value has thousands of related policies. ³ We might then create this clustering index:

The circa flag would cluster most of the currently asserted rows together, keeping them physically co-located under the lower cardinality columns. Clustering would continue based on effective date, and then by the higher cardinality object identifier of the table. This will provide access via the product type oid, and will tend to cluster the data for current access for three other potential search indexes:

Materialized Query Tables (MQTs), sometimes called Indexed Views, are extremely helpful in optimizing the performance of Asserted Versioning databases. They are especially helpful when querying currently asserted current versions.

Some optimizers will automatically determine if an MQT can be used, even if we do not explicitly specify one in the SQL FROM clause. Some DBMSs will let us specifically reference an MQT. Certain implementations of MQTs do not allow volatile variables and system registers, such as Now() or CURRENT TIMESTAMP in the definition, because the MQTs would be in a constant rebuild state. For example, we could not code the following in the definition of the MQT:

However, we could code a literal such as:

This would work, but obviously the MQT would have to be recreated each time the date changed. Another option is to create a single row table with today's date in it, and join to that table. For example, consider a Today table with a column called today's date. An MQT table would be joined to this table using a predicate like {asr_end_dt > Today.todays_dt}. Then, we could periodically increment the value of todays_dt to rebuild the MQT.

However, this is another place where we recommend the circa flag. If we have it, we can just use the {circa_asr_flag = ‘Y’} predicate in the MQT definition. This will keep the overhead low, will keep maintenance to a minimum, and will segregate past assertion time data, thereby getting better cache/buffer utilization.

We can also create something similar to the circa flag for the effective end date. This would be used to include currently effective versions in an MQT. However, for the same reasons we cannot use Now() in an assertion time predicate, we cannot use {eff_end_dt > Now()} in MQT definitions because of the volatile system variable Now(). So instead, we can use an effective time flag, and code a {circa_eff_flag = ‘Y’} predicate in the MQT definition.

MQTs could also be helpful when joining multiple asserted version tables together.

With most MQT tables, we have a choice of refreshing them either periodically or immediately. Our choice depends on what the DBMS permits, and the requirements of specific applications and specific MQTs.

In addition to tuning techniques specific to Asserted Versioning databases, there are general tuning techniques that are just as applicable to temporal tables as to conventional or non-temporal ones.

Use Cache Profligately. Per-unit memory costs, like per-unit costs for other hardware components, are falling. Multi-gigabyte memory is now commonplace on personal computers, and terabyte memories are now found on mainframe computers. Try to get as many and as much of your indexes in cached buffers as you can. Reducing physical I/O is essential to good performance.

Use Parameter Markers. If we cannot use static SQL for a frequently executed large data volume query, then the next best thing is to prepare the SQL with parameter markers. Many optimizers will perform a hashed compare of the SQL to the database dynamic prepared SQL cache, then a direct compare of the SQL being prepared, looking for a match. If it finds a match, it will avoid the expensive access path determination optimization process, and will instead use the previously determined access path rather than trying to re-optimize it.

The reason for the use of parameter markers rather than literals for local predicates is that with cache matching, the optimizer is much more likely to find a match. For example, a prepared statement of does not match causing the statement to be re-optimized. But a prepared SQL statement of will find a match whether the value of the parameter marker is 44, 55, or any other number, and in most cases will not need to be re-optimized.

Use More Indexes. Index other common search columns such as business keys. Also, use composite key indexes when certain combinations of criteria are often used together.

Eliminate Sorts. Try to reduce DBMS sorting by having index keys match the ORDER BY or GROUP BY sequence after EQUALS predicates.

Explain/Show Plan. Know the estimated execution time of the SQL. Incorporate SQL tuning into the system development life cycle.

Monitor and Tune. Some monitoring tools will identify the SQL statements that use the most overall resources. But as well as the single execution overhead identified in the Explain (Show Plan), it is important to also consider the frequency of execution of the SQL statements. For example, a SQL statement that runs for 6 seconds but is called only 10 times per hour uses a lot fewer resources than another that runs only 60 milliseconds, but is called 10,000 times per hour—in this case, 1 minute vs. 10 minutes total time. The query it is most important to optimize is the 60 millisecond query.

Use Optimization Hints Cautiously. Most optimizers work well most of the time. However, once in a while, they just don't get it right. It's getting harder to force the optimizer into choosing a better access path, for example by using different logical expressions with the same truth conditions, or by fudging catalog statistics. However, most optimizers support some type of optimization hints. Use them sparingly, but when all else fails, and the optimizer is being stubborn, use them.

Use Isolation Levels. Specify the appropriate Isolation Level to minimize locks and lock waits. Isolation levels of Cursor Stability (CS) or Uncommitted Read (UR) can significantly improve the throughput compared to more restrictive levels such as Repeatable Read (RR). However, keep in mind that a temporal update usually expands into several physical inserts and updates to the objects. So make sure that less restrictive isolation levels are acceptable to the application.