Home // DBKDA 2014, The Sixth International Conference on Advances in Databases, Knowledge, and Data Applications // View article

Sample Trace: Deriving Fast Approximation for Repetitive Queries

Authors:
Feng Yu
Wen-Chi Hou
Cheng Luo

Keywords: query optimization, query re-optimization, trace, sampling method, sample trace

Abstract:
epetitive queries refer to those queries that are likely to be executed repeatedly in the future. Queries such as those used to generate periodic reports, perform routine summarization and data analysis belong to this category. Repetitive queries can constitute a large portion of the daily activities of a database system, and thus deserve extra optimization efforts. In this paper, we propose to record information about how tuples are joined in a repetitive query, called the query trace. We prove that the query trace is sufficient to compute the exact selectivities of joins for all plans of a given query. To reduce the space and time overheads in generating the query trace, we propose to construct only a sample of the query trace, called a sample trace, which can be much smaller than a (complete) query trace. A special operation, called a sample outer join, is designed to accomplish this feat. Accurate estimations of join selectivities, with associated confidence intervals, can be derived easily using the sample trace. Extensive experiments show that the sample trace can be constructed efficiently and be a controllable trade-off between accuracy and efficiency in estimations of join selectivities for repetitive queries.

Pages: 59 to 65

Copyright: Copyright (c) IARIA, 2014

Publication date: April 20, 2014

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-334-6

Location: Chamonix, France

Dates: from April 20, 2014 to April 24, 2014