Query optimizer with join cardinality estimation which mitigates the effects of skew

1. A computer-implemented method to estimate a cardinality of a database query, the method comprising:

determining single table cardinalities after application of selection predicates;

estimating pair-wise join selectivities without assuming independence between selection and join predicates by dividing a pair-wise join cardinality by a product of the single table cardinalities; and

multiplying said pair-wise join selectivities with said single table cardinalities after application of the selection predicates.

2. The method of claim 1 , wherein the database query comprises the selection predicates and join conditions.

3. The method of claim 1 , further comprising:

generating a representation of an incidence graph for the query.

4. The method of claim 3 , wherein the incidence graph comprises nodes representing tables and arrows representing pair-wise join operations.

5. The method of claim 1 , wherein estimating the pair-wise join selectivities includes determining resultant tables after application of the selection predicates, and computing the pair-wise join cardinality comprising a size of a further resultant table after joining two said resultant tables.

6. A computer apparatus comprising:

a processor configured to execute computer-readable instructions;

memory configured to store the computer-readable instructions and other data;

a network interface configured to receive a database query;

an interconnection network for communications between said processor, said memory, and said network interface;

a query optimizer in said memory; and

a cardinality estimator in said memory,

wherein said cardinality estimator includes computer-readable instructions configured to (a) determine single table cardinalities after application of selection predicates from the database query, (b) estimate pair-wise join selectivities without assuming independence between the selection predicates and join predicates of the database query by dividing a pair-wise join cardinality by a product of the single table cardinalities, and (c) multiply said pair-wise join selectivities with said single table cardinalities after application of the selection predicates.

7. The apparatus of claim 6 , further comprising:

computer-readable instructions in said memory which are configured to generate a representation of an incidence graph for the query.

8. The apparatus of claim 7 , wherein the incidence graph comprises nodes representing tables and arrows representing pair-wise join operations.

9. The apparatus of claim 6 , wherein the computer-readable instructions configured to estimate the pair-wise join selectivities includes computer-readable instructions configured to determine resultant tables after application of the selection predicates and to compute a pair-wise join cardinality comprising a size of a further resultant table after joining two said resultant tables.

10. A non-transitory, computer-readable medium for storing computer-readable code, the medium comprising:

computer-readable code configured to determine single table cardinalities after application of selection predicates from a database query;

computer-readable code configured to estimate pair-wise join selectivities without assuming independence between the selection predicates and join predicates of the database query by dividing a pair-wise join cardinality by a product of the single table cardinalities; and

computer-readable code configured to multiply said pair-wise join selectivities with said single table cardinalities after application of the selection predicates.