Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-20
2002-10-22
Rones, Charles L. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C711S129000
Reexamination Certificate
active
06470360
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.
COMPUTER PROGRAM LISTING APPENDIX
A Computer Program Listing Appendix, containing one (1) total file on compact disc, is included with this application.
BACKGROUND OF THE INVENTION
The present invention relates generally to database systems and, more particularly, to optimization of page allocation (e.g., of data pages or the like) in such systems.
The present invention relates generally to information processing environments and, more particularly, to optimization of page allocation (e.g., of data pages or the like) 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 (formerly, Sybase SQL Server™). Both Powersoft™ and Sybase Adaptive 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.
As the migration to client/server continues, 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. Accordingly, there is much interest in improving the performance of such system, particularly in terms of execution speed and reliability.
Increasingly, database servers are deployed on multi-processor computers, such as Hewlett-Packard's V-class UNIX-based machines (e.g., HP V2500 RISC-based computer) running on a 64-bit operating system (e.g., HP UNIX). In such a configuration, multiple instances of the database server software are run, one instance (e.g., UNIX process) per processor, all operating on a single shared memory (e.g., 32 GB of main memory). Expectedly, as the number of processors is increased, the contention on the single shared memory—a critical system resource—also increases. As soon as contention for the shared memory arises, each of the multiple processes will encounter wait states, such as “spinning” (e.g., consuming CPU cycles while waiting availability of a spin lock), or will stall in order to wait for its turn for access to the shared memory. As a result, overall system scalability and hence throughput suffer.
Thus today, the contention on shared memory poses a bottleneck to true scalability for database servers running on multi-processor computers. Moreover, the problem is particularly acute in environments employing database servers for online transaction processing (OLTP), such as e-commerce applications, where contention is exacerbated by a high number of concurrent transactions. What is really desired is for the database system to scale in relation (e.g., linearly) to the number of processors added, so that system throughput scales accordingly. The present invention includes optimization techniques that assist in reaching that ideal goal.
SUMMARY OF THE INVENTION
In a multiuser database environment with a large number of clients performing a large number of transactions (e.g., inserts, updates, and deletes), such as an OLTP application executing hundreds of transactions per minute for providing e-commerce support, a huge number of database page splits occur. In such a scenario, the system must frequently access the database's allocation pages in order to update the information pertaining to page-management housekeeping. Each allocation page is protected in this concurrent environment using a latch. Since the conventional approach is for the database system to traverse a chain of allocation pages and grab the first available allocation page, the net result is that the latch protecting the allocation page becomes a single point of contention in a high-volume transaction environment.
The present invention comprises a Client/Server Database System with improved page allocation methodology, particularly applicable in a multiprocessor database configuration. In an exemplary embodiment, the system includes one or more Clients (e.g., Terminals or PCs executing client database access software) 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 that modify data are typically provided using a data manipulation language (DML), such as using the DML capabilities of the well-known SQL syntax.
The present invention introduces a methodology for optimized page allocation, using the following approach. During page allocation, once an allocation page with free space has been located in the system's global allocation map or GAM (i.e., using routine page allocation steps), the page identifier for that allocation page is stored in a hint array, as part of that object's (i.e., table's) object descriptor or des. For a table undergoing a lot of splits (i.e., insert-intensive object), the system may store an array of allocation page “hints” (allocation page identifiers) in the des for that object (e.g., table). The array itse
Rones Charles L.
Smart John A.
Sybase Inc.
LandOfFree
Database system with improved methodology for page allocation 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 with improved methodology for page allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system with improved methodology for page allocation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2963181