SELVA: A Reliable and Fast Selectivity Estimation Method for Query Plan Optimization in Video Analytics

Video Database Management Systems (VDMS) face a critical challenge in optimizing query plans: accurate selectivity estimation, which predicts the proportion of data satisfying a predicate. Existing methods rely on fixed sampling rates (e.g., 10% of video data) to approximate selectivity, but this incurs substantial computational overhead for video data transformation (26–37% of query time) and lacks statistical guarantees for estimation reliability. The reliance on manual, static sampling further limits efficiency, as it fails to adapt to varying query complexities. We propose a dynamic sampling framework that reframes selectivity estimation under the statistical framework. Our approach introduces two key innovations. First, we design confidence sequences using an adaptive strategy, which dynamically adjusts sample sizes to meet user-defined error bounds and confidence levels, eliminating the need for fixed sampling rates. Second, we integrate an optimized betting algorithm with geometric checkpoint scheduling to minimize sample size while preserving statistical guarantees. Additionally, we leverage control variates, a variance reduction technique, to exploit correlations between transformation algorithms, further reducing sampling requirements. Experiments demonstrate that our framework reduces selectivity estimation overhead by 31% compared to conventional fixed sampling, while achieving equivalent accuracy (95% confidence, ±5% error margin). By replacing heuristic sampling with rigorous statistical guarantees, our method enhances the efficiency and scalability of VDMS query optimization, particularly for large-scale video analytics applications.