Method of building multidimensional workload-aware histograms

Details Method of building multidimensional workload-aware histograms Method of building multidimensional workload-aware histograms

2006-02-28

2006-02-28

Ali, Mohammad (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07007039

ABSTRACT:
In a database system, a method of maintaining a self-tuning histogram having a plurality of existing rectangular shaped buckets arranged in a hierarchical manner and defined by at least two bucket boundaries, a bucket volume, and a bucket frequency. At least one new bucket is created in response to a query on the database. Each new bucket is contained within at least one existing bucket and the new bucket becomes a child bucket and the existing bucket containing it becomes a parent bucket. The boundaries of each new bucket correspond to a region of the database accessed by the query and the frequency of the new bucket is a number of data records returned by the query. Buckets may be merged based on a merge criterion such as similar bucket density when the total number of buckets exceeds the predetermined budget.

REFERENCES:
patent: 5870752 (1999-02-01), Gibbons et al.
patent: 5920870 (1999-07-01), Briscoe et al.
patent: 5991764 (1999-11-01), Sundaresan
patent: 6353832 (2002-03-01), Acharya et al.
patent: 6507840 (2003-01-01), Ioannidis et al.
patent: 6772142 (2004-08-01), Kelling et al.
patent: 2001/0010091 (2001-07-01), Noy
A. Aboulnaga and S. Chaudhuri. Self-Tuning Histograms: Building Histograms Without Looking at Data. In Proceedings of the 1999 ACM International Conference on Management of Data (SIGMOD'99), Jun. 1999.
S. Chaudhuri. An Overview of Query Optimization in Relational Systems. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Jun. 1-3, 1998, Seattle, Washington 1998.
C.M. Chen and N. Rousopoulos. Adaptive Selectivity Estimation Using Query Feedback. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, 1994.
D. Donjerkovic, Y. Ioannidis and R. Ramakrishnan. Dynamic Histograms: Capturing Evolving Data Sets. In Proceedings of the 16th International Conference on Data Engineering, 2000.
P.B. Gibbons, Y. Matias and V. Poosala. Fast Incremental Maintenance of Approximate Histograms. In VLDB '97, Proceedings of 23rd International Conference on Very Large Data Bases, 1997.
D. Gunopulos, G. Kollios, V.J. Tsotras and C. Domeniconi. Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes. In Proceedings of the 2000 ACM International Conference on Management of Data (SIGMOD'00), 2000.
H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K.C. Sevik and T. Suel. Optimal Histograms with Quality Guarantees. In Proceedings of the Twenty-fourth International Conference on Very Large Databases (VLDB'98), 1998.
M. Muralikrishna and D.J. DeWitt. Equi-Depth Histograms for Estimating Selectivity Factors for Multidimensional Queries. In Proceedings of the 1988 ACM International Conference on Management of Data (SIGMOD'88), Jun. 1988.
M. Muthukrishnan, V. Poosala and T. Suel. On Rectangular Partitioning in Two Dimensions: Algorithms, Complexity and Applications. In Database Theory-ICDT'99, 7th International Conference, 1999.
J. Nievergelt, H. Hinterberger and K.C. Sevcik. The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Transactions on Database Systems, 9(1):38-71, Mar. 1984.
V. Poosala and Y. Ioannidis. Selectivity Estimation Without the Attribute Value Independence Assumption. In Proceedings of the Twenty-Third International Conference on Very Large Databases (VLDB '97), 1997.
V. Poosala, Y.Ioannidis, P.J. Haas and E.J. Shekita. Improved Histograms for Selectivity Estimation of Range Predicates. In Proceedings of the 1996 ACM International Conference on Management of Data (SIGMOD '96), Jun. 1996.

Affiliated with

Also associated with

Rating

Method of building multidimensional workload-aware histograms does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of building multidimensional workload-aware histograms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of building multidimensional workload-aware histograms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3632964