Search

After a system crash, databases recover to the last committed transaction, but applications usually either crash or cannot continue. The Phoenix purpose is to enable application state to persist across system crashes, transparent to the application program. This simplifies application programming, reduces operational costs, masks failures from users, and increases application availability, which is critical in many scenarios, e.g., e-commerce. Within the Phoenix project, we have explored how to provide application recovery efficiently and transparently via redo logging. This paper describes the conceptual framework for the Phoenix project, and the software infrastructure that we are building.

An under-appreciated facet of index search structures is the importance of high performance search within B-tree internal nodes. Much attention has been focused on improving node fanout, and hence minimizing the tree height [BU77, LL86]. [GG97, Lo98] have discussed the importance of B-tree page size. A recent article [GL2001] discusses internal node architecture, but the subject is buried in a single section of the paper.In this short note, I want to describe the long evolution of good internal node architecture and techniques, including an understanding of what problem was being solved during each of the incremental steps that have led to much improved node organizations.

Media recovery protects a database from failures of the stable medium by maintaining an extra copy of the database, called the backup, and a media recovery log. When a failure occurs, the database is “restored” from the backup, and the media recovery log is used to roll forward the database to the desired time, usually the current time. Backup must be both fast and “on-line”, i.e. concurrent with on-going update activity. Conventional online backup sequentially copies from the stable database, almost independent of the database cache manager, but requires page-oriented log operations. But results of logical operations must be flushed to a stable database (a backup is a stable database) in a constrained order to guarantee recovery. This order is not naturally achieved for the backup by a cache manager concerned only with crash recovery. We describe a “full speed” backup, only loosely coupled to the cache manager, and hence similar to current online backups, but effective for general logical log operations. This requires additional logging of cached objects to guarantee media recoverability. We then show how logging can be greatly reduced when log operations have a constrained form which nonetheless provides very useful additional logging efficiency for database systems.

Recovery can be extended to new domains at reduced logging cost by exploiting “logical” log operations. During recovery, a logical log operation may read data values from any recoverable object, not solely from values on the log or from the updated object. Hence, we needn't log these values, a substantial saving. In [8], we developed a redo recovery theory that deals with general log operations and proved that the stable database remains recoverable when it is explained in terms of an installation graph. This graph was used to derived a write graph that determines a flush order for cached objects that ensures that the database remains recoverable. In this paper, we introduce a refined write graph that permits more flexible cache management that flushes smaller sets of objects. Using this write graph, we show how: (i) the cache manager can inject its own operations to break up atomic flush sets; and (ii) the recovery process can avoid redoing operations whose effects aren't needed by exploiting generalized recovery LSNs. These advances permit more cost-effective recovery for, e.g., files and applications.

The recent article by Gray and Graefe in the Sigmod Record [1] included a study of B-tree page size and the trade-off between page size and the cost of accessing B-tree data. Its goal was to find the page size that would result in the lowest access cost per record. This insightful analysis showed how increasing page size permitted the B-tree to be traversed faster while increasing the amount of data that needed to be read to perform the traversal. Their analysis captures the trade-off between the cost (in time) of each access and how many accesses are needed to traverse the tree.

Most database systems provide database designers with single attribute indexing capability via some form of B+tree. Multi-attribute search structures are rare, and are mostly found in systems specialized to some more narrow application area, e.g. geographic databases. The reason is that no multi-attirbute search structure has been demonstrated, with high confidence. Multi-attribute search is an active area of research. This paper reviews the state of this field and some of the difficult problems, and reviews some recent notable papers.

To achieve high concurrency in a database system has meant building a system that copes well with important special cases. Recent work on multi-level systems suggest a systematic path to high concurrency. A multi-level system using locks permits restrictive low level locks of a subtransaction to be replaced with less restrictive high level locks when sub-transactions commit, enhancing concurrency. This is possible because sub-transactions can be undone via high level compensation actions rather than by restoring a prior lower level state. We describe a recovery scheme, called Multi-Level Recovery (MLR) that logs this high level undo operation with the commit record for the subtransaction that it compensates, posting log records to only a single log. A variant of the method copes with nested transactions, and both nested and multi-level transactions can be treated in a unified fashion.

In the discussion of research issues in spatial databases (SIGMOD Record vol. 19, no. 4, Dec 1990) we stated the need for a robust framework for analytical comparison of a broad range of spatial access methods. The utility of such a comparison, even of very closely related access methods, was shown in [FALO87]. A necessary precondition for a meaningful analytical comparison is the existence of strong analytical results for individual access methods. In the following paper, Salzberg and Lomet take the worst case analytical results on fan-out and average storage utilization they obtained for their hB-tree [LOME89,LOME90] and extend the analysis to another robust method, Z-order encoding [OREN84]. We think this paper is a start on the comparative assessment of access methods based on analytical results. We hope to see future work extend the framework beyond worst case analysis, and to other access methods as well.

We present an access method designed to provide a single integrated index structure for a versioned timestamped database with a non-deletion policy. Historical data (superceded versions) is stored separately from current data. Our access method is called the Time-Split B-tree . It is an index structure based on Malcolm Easton's Write Once B-tree. The Write Once B-tree was developed for data stored entirely on a Write-Once Read-Many or WORM optical disk. The Time-Split B-tree differs from the Write Once B-tree in the following ways: Current data must be stored on an erasable random-access device. Historical data may be stored on any random-access device, including WORMs, erasable optical disks, and magnetic disks. The point is to use a faster and more expensive device for the current data and a slower cheaper device for the historical data. The splitting policies have been changed to reduce redundancy in the structure—the option of pure key splits as in B + -trees and a choice of split times for time-based splits enable this performance enhancement. When data is migrated from the current to the historical database, it is consolidated and appended to the end of the historical database, allowing for high space utilization in WORM disk sectors.