Patent ID: 7895189

Claim:
A computer-implemented method comprising: receiving a query of a database, said query having an expression, said expression comprising a plurality of filters, said expression comprising at least one AND operator and at least one OR operator connecting said plurality of filters; providing a tree representing said expression, said tree comprising a plurality of nodes, said at least one AND operator being associated with at least one AND node of said plurality of nodes, respectively; said at least one OR operator being associated with at least one OR node of said plurality of nodes, respectively; matching at least one index to at least a portion of said expression, wherein said matching identifies at least one eligible index to satisfy a particular filter of said plurality of filters; creating a partition set comprising a plurality of partitions, each partition of said plurality of partitions comprising at least one filter of said plurality of filters; merging one partition of said partition set with another partition of said partition set based on a determination that a filter of said one partition and a filter of said another partition have a least common ancestor that is an AND node of said plurality of nodes, wherein said merging reduces a number of said plurality of partitions of said partition set; and generating an index plan based on, at least in part, said at least one eligible index and a particular partition of said partition set, said particular partition comprising said particular filter.