A system for cardinality estimation for database query planning is provided. In some implementations, the system performs operations comprising selecting a subset of data from a set of data on which a database query is to be executed, the set of data including a first quantity of tuples and the subset of data including a second quantity of tuples. The operations can further comprise determining, based on evaluating one or more predicates on the subset, a third quantity of tuples in the subset which satisfy the one or more predicates. The operations can further comprise determining, based on the first quantity, the second quantity, and the third quantity, a range within the subset that comprises estimated cardinalities of the one or more predicates within a predetermined error threshold range. Related systems, methods, and articles of manufacture are also described.