1. A computer-implemented method for generating a cardinality estimate, comprising: identifying a predicate in a query, wherein the predicate is split into a plurality of equivalence classes; generating a plurality of equivalence graphs from the plurality of equivalence classes; identifying spanning trees from the plurality of equivalence graphs; and generating a cardinality estimate based on the spanning trees.