Probabilistic methods in query processing
Sangeetha Seshadri · 1992
In this thesis, we apply probabilistic techniques to analyze problems related to query optimization and query processing in database management systems. We consider three such problem areas: sampling based query size estimation, sampling based percentile estimation, and analytically deriving sizes of answers to recursive datalog queries. Sampling based query size estimation deals with the problem of estimating the number of tuples in the sizes of answers to relational queries. We compare the theoretical performance of five sampling methods and prove that the accuracy of these schemes as a function of the number of I/O's forms a partial order. We show that the most basic definition of a random sample, called simple random sampling, could lead to excessive load imbalance in a parallel database system. We overcome this problem by showing that stratified random sampling guarantees perfect load balancing without sacrificing the quality of the estimate. Sampling based percentile estimation is useful to partition the work in a parallel system. This partitioning can in turn be used to extract parallelism. Parallel sorting, nou-equi join computation and parallel joins in the presence of data skew are some examples of where estimates of percentiles can be used to partition the work. In each case, the efficiency of the resulting algorithm depends on the quality of the estimates of the percentiles. We derive a new bound on the probability that the estimates differ from the actual value by more than a certain amount for a given number of samples. Finally, we derive analytically the sizes of the fixpoints of recursively defined relations in datalog programs and the rewritten programs generated by the Magic Sets and Factoring rewriting algorithms in response to selection queries. Our results show that the recursively defined relations are within a small constant factor of their worst-case size bounds, and that the Magic Sets rewriting algorithm on the average produces relations within a small constant factor of the corresponding bounds for the recursion without rewriting. The expected size of relations produced by the Factoring algorithm, when it applies, is significantly smaller than the expected size of relations produced by Magic Sets.