Star/join query optimization

Details Star/join query optimization Star/join query optimization

1997-08-28

1999-09-28

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

707 2, 707 3, G06F 1730

Patent

active

059604280

ABSTRACT:
Unwieldy star/join queries are performed more efficiently using a filtered fact table. Suitable queries include star/join queries with a large fact table joined with multiple subsidiary dimension tables, where indices exist over fact table join columns. The query is analyzed to prepare a query plan for the dimension table accesses. This plan is supplemented by adding nested loop join operations, where the inner table is a dimension table plan and the outer table is an index scan performed over a fact table index of the join column with the dimension table. The plan is also supplemented by filtering records resulting from the nested loop joins using a sequence of dynamic bit vectors, ultimately yielding a list of probable fact table records. The plan is further supplemented by fetching these records to construct a distilled fact which is used, instead of the large original table, to execute the query in considerably less time. If desired, the supplemented query plan and other competing approaches may studied to provide cost estimates, with the least costly approach being actually implemented.

REFERENCES:
patent: 5091852 (1992-02-01), Tsuchida et al.
patent: 5297280 (1994-03-01), Potts, Sr. et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5530939 (1996-06-01), Mansfield, Jr. et al.
patent: 5671403 (1997-09-01), Shekita et al.
patent: 5694591 (1997-12-01), Du et al.
patent: 5797000 (1998-08-01), Bhattacharya et al.
patent: 5799309 (1998-08-01), Srinivasan
patent: 5806059 (1998-09-01), Tsuchida et al.
patent: 5822749 (1998-10-01), Agrawal
patent: 5848408 (1998-12-01), Jakobson et al.
patent: 5864842 (1999-01-01), Pederson et al.
DeWitt et al, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering. vol. 2. No. 1, pp. 44-62, Mar. 1990.
O'Neil et al., Multi-Table Joins Through Bitmapped Join Incides, SIGMOD Record, vol. 24, No. 3, Sep. 1995, pp. 8-11.
Sellenger et al., "Access Path Selection in a Relational Database Management System", Proceedings of the ACM SIGMOD Conference, Jun. 1979.
B. H. Bloom, "Space/Time Trade-Offs in Hash Coding with Allowable Errors", Comm. ACM 13, 7 (Jul. 1970), pp. 422-426.
J. L. Carter et al., "Universal Classes of Hash Functions", Journal of Computer and System Sciences, vol. 18, No. 2, (Apr. 1979), pp. 143-154.

Affiliated with

Also associated with

Rating

Star/join query optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Star/join query optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Star/join query optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-716081