Query optimizers often produce sub-optimal query plans due to inaccurate cardinality estimates. The goal of exact cardinality query optimization (ECQO) is to produce optimal plans based on guaranteed exact cardinality values, obtained via probe executions. We propose a novel algorithm for ECQO. It improves over prior work by limiting the overheads of probe executions. Instead of fully generating each relation in the optimizer's plan space, it calculates cardinality bounds based on partially generated relations. Thereby, it is often able to prune relations early if they are too large to participate in any optimal plan. Our algorithm exploits dependencies between relations to propagate exclusions, it selects probing targets for maximum information gain, and it caps probing overheads by conservative bounds on execution cost. Those bounds are iteratively increased once lower bounds on optimal query execution cost have been established. The algorithm is non-intrusive and can be used on top of any database management system supporting SQL limit clauses. We formally prove that probing costs are bounded as a function of the optimal execution cost and evaluate our algorithm experimentally. Our algorithm is in average six times and up to 69 times faster than a state-of-the-art baseline for ECQO on the recently proposed join order benchmark.