1. A computer program product comprising a non-transitory computer useable storage medium to store a computer readable program, wherein the computer readable program, when executed on a computer, causes the computer to perform operations comprising: receiving a query for which a query execution plan (QEP) is to be computed, wherein a set comprising all possible QEPs for the query describes a search space, wherein each QEP of the set references a plurality of quantifiers; dividing the search space into a plurality of subproblems for which constituent QEPs referencing a smaller number of quantifiers are to be created; generating a skip vector array (SVA) that indicates disjoint quantifier sets between two subproblems; partitioning the plurality of subproblems into a plurality of partitions, wherein each of the subproblems within a partition references the same number of quantifiers; allocating each of the plurality of partitions to a thread of a plurality of threads within a multiple thread architecture, wherein a partition containing subproblems referencing fewer quantifiers is executed before a partition containing subproblems referencing more quantifiers; receiving from each of the plurality of threads a constituent QEP for each subproblem; and combining two constituents QEPs at the QEP optimizer server to determine a QEP referencing the combined set of quantifiers for the two constituent QEPs.