Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-02
2002-01-22
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06341281
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 optimizing the process of retrieving information stored 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,
Volumes 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™ (formerly, Sybase SQL Server™) database servers. Both Powersoft™ and Sybase Adaptive Server™ are available from Sybase, Inc. of Emeryville, Calif.
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 SQL Server™. As a result, increasingly higher demands are being placed on server-based SQL database systems to provide enterprise-wide decision support—providing timely on-line access to critical business information (e.g., through “queries”). Accordingly, there is much interest in improving the performance of such systems, particularly database queries, for enhancing decision support.
SUMMARY OF THE INVENTION
The present invention comprises a Client/Server Database System with improved methods for performing database queries. 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®, available from Novell, Inc. of Provo, Utah) includes a Database Server System, such as Sybase SQL 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 particular records of a one or more tables. For enhancing the speed in which the Database Server performs queries, a new invariant technique is introduced to evaluate correlated queries (i.e., queries containing one or more correlated subqueries) efficiently.
Correlated queries are very common and important in decision support systems. Traditional nested iteration evaluation methods for such queries can be very time consuming. When they apply, query rewriting techniques have been shown to be much more efficient, but query rewriting is not always possible. When query rewriting does not apply, something better can be done than the traditional nested iteration methods.
The basic approach of the present invention, therefore, is to recognize the part(s) of the subquery that is not related to the outer references and cache the result(s) of that part(s) after its first execution. Later, the result can be reused and combined with the result of the rest of the subquery that is changing for each iteration. This technique is applicable to arbitrary correlated subqueries.
Methods are introduced to recognize the invariant part of a data flow tree, and to restructure the evaluation plan to reuse the stored intermediate result. An efficient method is proposed to teach an existing join optimizer to understand the invariant feature and thus allow it to be able to generate better join plans in the new context. Some other related optimization techniques are also introduced. The proposed techniques were implemented using an existing real commercial database system.
An experimental evaluation of the proposed technique indicates that, when query rewriting is not possible, the invariant technique is significantly better than the traditional nested iteration method. Even when query rewriting applies, the invariant technique is sometimes better than the query rewriting technique. Thus, the invariant technique is advantageous as an alternative in evaluating correlated queries since it fills the gap left by rewriting techniques.
REFERENCES:
patent: 4527253 (1985-07-01), Sato et al.
patent: 4947319 (1990-08-01), Bozman
patent: 5062055 (1991-10-01), Chinnaswamy et al.
patent: 5210870 (1993-05-01), Baum et al.
patent: 5237681 (1993-08-01), Kagan et al.
patent: 5317727 (1994-05-01), Tsuchida et al.
patent: 5317742 (1994-05-01), Bapat
patent: 5367656 (1994-11-01), Ryan
patent: 5367675 (1994-11-01), Cheng et al.
patent: 5379419 (1995-01-01), Heffernan et al.
patent: 5394531 (1995-02-01), Smith
patent: 5412804 (1995-05-01), Krishna
patent: 5450561 (1995-09-01), Ryan
patent: 5465342 (1995-11-01), Walsh
patent: 5465352 (1995-11-01), Nakazawa et al.
patent: 5495591 (1996-02-01), Ryan
patent: 5526511 (1996-06-01), Swenson et al.
patent: 5537635 (1996-07-01), Douglas
patent: 5548755 (1996-08-01), Leung et al.
patent: 5668987 (1997-09-01), Schneider
patent: 5812996 (1998-09-01), Rubin et al.
patent: 5822749 (1998-10-01), Agarwal
patent: 5822750 (1998-10-01), Jou et al.
patent: 5832475 (1998-11-01), Agrawal et al.
patent: 5852821 (1998-12-01), Chen et al.
patent: 6032144 (2000-02-01), Srivastava et al.
patent: 6134546 (2000-10-01), Bestgen et al.
patent: 6182060 (2001-01-01), Hedgcock et al.
Bello Randall George
Kirk Steven A.
MacNicol Roger Dermot
Rao Jun
Yang Katherine Tsouya
Alam Hosain T.
Ly Anh
Smart John A.
Sybase Inc.
LandOfFree
Database system with methods for optimizing performance of... 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 methods for optimizing performance of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system with methods for optimizing performance of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2820592