Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-07-31
2002-03-26
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06363387
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The present invention relates generally to information processing environments and, more particularly, to computer-implemented methodologies for enhancing concurrent access in a data processing system, such as a Database Management System (DBMS).
Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as “records” having “fields” of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.
Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is typically provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information retrieved from or updated in such files, and so forth, all without user knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of a database management system is known in the art. See e.g., Date, C.,
An Introduction to Database Systems,
Volume I and II, Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.
DBMS systems have long since moved from a centralized mainframe environment to a de-centralized or distributed environment. One or more PC “client” systems, for instance, may be connected via a network to one or more server-based database systems (SQL database server). Commercial examples of these “client/server” systems include Powersoft™ clients connected to one or more Sybase Adaptive Server™ database servers. Both Powersoft™ and Sybase Adaptive Server™ (formerly Sybase SQL Server™) are available from Sybase, Inc. of Emeryville, Calif.
To support multiple clients concurrently accessing data, a database system must employ some sort of concurrency control. Concurrency control is the way that a database synchronizes clients' or users' access to data to ensure that they do not destroy each other's work. Locking is the way that most databases handle concurrency control. While one user has a lock on a subset of the database, that data is “blocked” or protected from other users' attempts to make changes to it. One user's changes have to be “committed” before another user can see or further change the same data.
One of the characteristics of a locking scheme is the level of the locks. Some products default to physical storage page-level locks, while others default to logical row-level locks. Some products allow the user to specify which level of locking (page, row, or table) will be used for an individual table. Another of the characteristics of a locking scheme is the lock type, whether dynamic or static. A static locking scheme sets up one level of locking for each table in the database, often at table creation time or via database defaults. Dynamic locking attempts to optimize the granularity of locks depending on the particular change being made. A dynamic locking scheme will automatically increase the granularity of locks from row to page to table level when a certain threshold is met in the more fine-grained locks. The goal is to use the least amount of system overhead per lock while getting as many users safely into the database as possible. The usual approach is to start with a higher level lock, then reduce its granularity only when there is contention from another transaction that wants to lock the same page or table for an UPDATE, DELETE, INSERT, or SELECT operation. This minimizes the total number of locks.
The approach of initially using a lower granularity and escalating it when a threshold level is reached has problems. For example, escalation from row-level to page-level locks can cause deadlocks when two transactions attempt to acquire page-level locks on the same page at the same time. Page-level locking is particularly problematic for highly-concurrent data structures whose structures must be maintained, such as B-tree data structures. Conventionally, when two different transactions are attempting to insert into the same B-tree page, for instance, the underlying system employs transaction durational page-level locks, so that the two competing inserts would be serialized. If enough room does not exist for the inserts, the page is split. A split in one part of the tree does not occur in isolation but propagates to its parent. Often, the split is done as a separate action—a “nested top” action—within the transaction. After the split is completed, the system continues with the current transaction. If two transactions are trying to perform splits at different locations in the B-tree in a conventional system, the transactions are serialized, as a conventional system only allows one top action at a time. The process of serializing page splits leads to much contention among the multiple transactions concurrently executing within the system.
Each day more and more businesses are run from mission-critical systems which store information on server-based SQL database systems, such as Sybase Adaptive Server™. As a result, increasingly higher demands are being placed on server-based SQL database systems to provide enterprise-wide decision support. Since reducing the time required for processing queries substantially impacts system performance, it is highly desirable to optimize query processing. Without further optimization, processing of a query in real-time can be particularly burdensome, especially since a relatively high number of computations and possibly disk or network input/output operations must be performed in order to evaluate each row of the table or tables under examination. Accordingly, there is much interest in improving the performance of such tasks, particularly in terms of execution speed and reliability.
SUMMARY OF THE INVENTION
The present invention comprises a Client/Server Database System with improved methods for enhancing concurrency using a “row update” bit and deferred locking. In an exemplary embodiment, the system includes one or more Clients (e.g., Terminals or PCs) connected via a Network to a Server. The Server, operating under a server operating system (e.g., UNIX), includes a Database Server System, such as Sybase Adaptive Server™. In general operation, Clients store data in and retrieve data from one or more database tables resident on the Server by submitting SQL commands, some of which specify “queries”—criteria for selecting records of a table for a particular operation (e.g., updating). Queries are typically provided using a data manipulation language (DML), such as using the well-known SQL syntax.
The present invention introduces a methodology for using a “row update” (ROW_UPDATE) bit and deferred locking techniques that reduce locking overhead and increase concurrency, during database operations requiring access (e.g., query processing). Each data row employs ROW_DELETE and ROW_UPDATE status bits (flags or indicators). When a transaction updates a row, it sets the ROW_UPDATE bit. When a transaction inserts a row, neither the ROW_UPDATE nor the ROW_DELETE status bits
Martin Jameison B.
Ponnekanti Nagavamsi
Alam Hosain T.
Nguyen Tam V
Smart John A.
Sybase Inc.
LandOfFree
Database system providing methodology for enhancing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database system providing methodology for enhancing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system providing methodology for enhancing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2881257