System and method for identifying and constructing star joins for execution by bitmap ANDing

Patent 6105020 Issued on August 15, 2000. Estimated Expiration Date:

October 11, 2019. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Method and apparatus for automatic table selection and generation of structured query language instructions
Patent #: 5519859
Issued on: 05/21/1996
Inventor: Grace

Query optimizer system that detects and prevents mutating table violations of database integrity in a query before execution plan generation
Patent #: 5546576
Issued on: 08/13/1996
Inventor: Cochrane, et al.

Program storage device and computer program product for outer join operations using responsibility regions assigned to inner tables in a relational database
Patent #: 5551031
Issued on: 08/27/1996
Inventor: M. Cheng, et al.

Outer join operations using responsibility regions assigned to inner tables in a relational database
Patent #: 5557791
Issued on: 09/17/1996
Inventor: Cheng, et al.

Database system with subquery optimizer
Patent #: 5668987
Issued on: 09/16/1997
Inventor: Schneider

Global optimization of correlated subqueries and exists predicates
Patent #: 5761657
Issued on: 06/02/1998
Inventor: Hoang

Remote highlighting of objects in a conferencing system by logically anding a highlight bitmap and a foreground bitmap
Patent #: 5790818
Issued on: 08/04/1998
Inventor: Martin

Bitmap comparison apparatus and method using an outline mask and differently weighted bits
Patent #: 5835634
Issued on: 11/10/1998
Inventor: Abrams

Database link system
Patent #: 5845276
Issued on: 12/01/1998
Inventor: Emerson, et al.

Method for executing star queries
Patent #: 5848408
Issued on: 12/08/1998
Inventor: Jakobsson, et al.

More ...

Inventors

Application

No. 415799 filed on 10/11/1999

US Classes:

707/2, Access augmentation or optimizing707/3Query processing (i.e., searching)

Examiners

Primary: Black, Thomas G.
Assistant: Coby, Frantz

Attorney, Agent or Firm

Rogitz; John L.

International Class

G06F 017/30

Abstract

A system and method for a relational database system for identifying star joins in a query and for breaking the query down for bitmap ANDing. The fact table of the star join is located, and cycles between and within dimension tables are broken. Then, the minimal set of tables necessary to execute the star join is identified, and the dimension tables that should appear in the bitmap ANDing plan are also identified. A bitmap ANDing plan is then generated, or, if the query does not qualify for bitmap ANDing, a conventional execution plan is generated.