Fast Entropy Maximization for Selectivity Estimation of Conjunctive Predicates on CPUs and GPUs
Diego Havenstein, Peter Lysakovski, Norman May, Guido Moerkotte, Gabriele Steidl · MADOC (University of Mannheim) · 2020
Entropy maximization is the only principled approach to combine several (partial) selectivity estimates to an estimate for a full conjunction.However, this approach has no appearance in database management systems.We conjecture that the main reason is a lack of implementations with good performance.Indeed, the originally proposed iterative scaling algorithm has a slow convergence rate and high complexity in each iteration.As an alternative, we propose to use a method based on Newton's algorithm to solve the entropy maximization problem.Further, we show how this general approach can be implemented very efficiently for both CPUs and GPUs.Our experiments show that our CPU and GPU implementation is more than 4 orders of magnitude faster than the state-of-the-art method for the most complex problem it could handle.For even more complex problems our new GPU implementation outperforms our CPU implementation by more than 43x.In a few milliseconds it is now possible to compute all partial selectivities for complex conjunctive predicates with 20 or more predicates.We strongly believe that the proposed implementation is ready for production-grade database management systems.