Compressing database workloads

Details Compressing database workloads Compressing database workloads

2005-06-28

2005-06-28

Rones, Charles (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C706S917000, C709S224000, C703S021000

Reexamination Certificate

active

06912547

ABSTRACT:
Relational database applications such as index selection, histogram tuning, approximate query processing, and statistics selection have recognized the importance of leveraging workloads. Often these applications are presented with large workloads, i.e., a set of SQL DML statements, as input. A key factor affecting the scalability of such applications is the size of the workload. The invention concerns workload compression which helps improve the scalability of such applications. The exemplary embodiment is broadly applicable to a variety of workload-driven applications, while allowing for incorporation of application specific knowledge. The process is described in detail in the context of two workload-driven applications: index selection and approximate query processing.

REFERENCES:
patent: 5761438 (1998-06-01), Sasaki
patent: 5974457 (1999-10-01), Waclawsky et al.
patent: 2002/0161566 (2002-10-01), Uysal et al.
“Equivalences Among Relational Expressions”, A.V. Aho, Y. Sagiv and J.D. Ullman, pp. 218-246, 1979 Society for Industrial and Applied Mathematics, vol. 8, No. 1, May 1979.
“Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries”, Stefano Ceri and Georg Gottlob, pp. 324-345, IEEE Transactions on Software Engineering, vol. SE-11, No. 4, Apr. 1985.
S. Acharya, P.B. Gibbons and V. Poosala, “Congressional Samples for Approximate Answering of Group-By-Queries”, Proceedings of the ACM SIGMOD, 2000, pp. 487-498.
A. Aboulnaga, S. Chaudhuri, “Self-Tuning Histograms: Building Histograms Without Looking at Data”, Proceedings of the ACM SIGMOD, 1999, pp. 181-192.
S. Chaudhuri, V. Narasayya, “An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server”, Proceedings of the 23rdInternational Conference on Very Large Databases, 1997, pp. 146-155.
S. Chaudhuri, G. Das, M. Datar, R. Motwani, V. Narasayya, “Overcoming Limitations of Sampling for Aggregation Queries”, Proceedings of the 17thInternational Conference on Data Engineering, 2001, pp. 534-542.
D. Donjerkovic, Y. Ioannidis, R. Ramakrishnan, “Dynamic Histograms: Capturing Evolving Data Sets”, Proceedings of the 16thInternational Conference on Data Engineering, 2000.
V. Ganti, M.L. Lee, R. Ramakrishnan, “ICICLES: Self-Tuning Samples for Approximate Query Answering”, Proceedings of the 26thInternational Conference on Very Large Databases, 2000, pp. 176-187.
P.B. Gibbons, Y. Matias, V. Poosala, “Fast Incremental Maintenance of Approximate Histograms”, Proceedings of the 17thInternational Conference on Very Large Databases, 1997, pp. 466-475.
P.J. Haas, J.F. Naughton, S. Seshadri, L. Stokes, “Sampling-Based Estimation of the Number of Distinct Values of an Attribute”, Proceedings of the 21stInternational Conference on Very Large Databases, 1995, pp. 311-322.
N. Bruno, S. Chaudhuri and L. Gravano, “STHoles: A Multidimensional Workload-Aware Histogram”, Proceedings of the ACM SIGMOD, 2001.
M. Stillger, G. Lohman, V. Markl, M. Kandil, “LEO—DB2's LEarning Optimizer”, Proceedings of the 27thInternational Conference on Very Large Databases, 2001.
M. Charikar, S. Guha, E. Tardos, D.B. Shmoys, “A Constant-Factor Approximation Algorithm for the k-median problem”, Proceedings of the 31stAnnual Symposium on Theory of Computing, 1999.
S. Chaudhuri, V. Narasayya, “Automating Statistics Management for Query Optimizers”, Proceedings of the 16thInternational Conference on Data Engineering, 2000.
J.-H. Lin and J.S. Vitter, “ε-Approximations with Minimum Packing Constraint Violation”, Proceedings of the 24thAnnuäl Symposium on Theory of Computing, 1992.
G. Lohman, A. Skelley, G. Valentin, M. Zuliani, D.C. Zilio, “DB2 Advisor: An Optimizer Smart Enough to Recommend its Own Indexes”, Proceedings of the 16thInternational Conference on Data Engineering, 2000.
S. Arora, P. Raghavan, S. Rao, “Approximation Schemes for Euclidean k-medians and Related Problems”, Proceedings of the 30thAnnual Symposium on Theory of Computing, 1998.

Affiliated with

Also associated with

Rating

Compressing database workloads does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Compressing database workloads, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressing database workloads will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3509138