Selectivity and Cost Estimation for Joins Based on Random Sampling

摘要: We compare the performance of sampling-based procedures for estimating selectivity a join. While some have been proposed in database literature, their relative has never analyzed. A main result this paper is partial ordering that compares variability estimators different after an arbitrary fixed number sampling steps. Prior to current work, it was also unknown whether these fixed-step could be extended fixed-precision are both asymptotically consistent and efficient. Our second general method such extension proof valid all under consideration. show that, plausible assumptions on costs, with respect estimator implies corresponding cost. final collection cost processing join query according plan.