ACM Transactions on Database Systems · 2009 · 169 citations · 37 references
ComputingComputer ScienceInformation SystemsData ManagementDatabasesPredictive AnalyticsDatabase ManagementQuery ManagementQuery ProcessingRelational AlgebraRelational Data ModelRelational DatabasesExecution Time AnalysisExecution Time EstimationJoin AlgorithmsJoin ProcessingOperatorsQuery ExecutionQuery Performance MonitoringRelational Query Processing
Query monitoring observes and predicts execution parameters, serving users, administrators, and adaptive query processing. The article introduces a query monitoring system built from scratch, aiming to provide new techniques and an accessible interface for observed and predicted information. The system implements lightweight online cardinality estimation for joins and grouping operators, using efficient algorithms evaluated in an open‑source database. Evaluation of the prototype demonstrates the feasibility and practical utility of the proposed approach.
Query monitoring refers to the problem of observing and predicting various parameters related to the execution of a query in a database system. In addition to being a useful tool for database users and administrators, it can also serve as an information collection service for resource allocation and adaptive query processing techniques. In this article, we present a query monitoring system from the ground up, describing various new techniques for query monitoring, their implementation inside a real database system, and a novel interface that presents the observed and predicted information in an accessible manner. To enable this system, we introduce several lightweight online techniques for progressively estimating and refining the cardinality of different relational operators using information collected at query execution time. These include binary and multiway joins as well as typical grouping operations and combinations thereof. We describe the various algorithms used to efficiently implement estimators and present the results of an evaluation of a prototype implementation of our framework in an open-source data management system. Our results demonstrate the feasibility and practical utility of the approach presented herein.
37
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Random sampling with a reservoir
Jeffrey Scott Vitter · ACM Transactions on Mathematical Software · 1985 · 1.8K citations · Full text
Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang · 1997 · 928 citations · Full text