1. A computer-implemented method of partition pruning, comprising: receiving a query that requests retrieval of data items from a partitioned object that is partitioned into a plurality of partitions based, at least in part, on partitioning criteria; wherein the partitioning criteria associates, for each partition of the plurality of partitions, a different set of one or more key values with said each partition; wherein the partitioning criteria establishes an order of the plurality of partitions; identifying a plurality of conditions specified in a predicate of the query, wherein: the plurality of conditions includes a first condition and a second condition that specifies a non-equality condition, the first condition and the second condition are combined using an OR operation, the first condition corresponds to a first set of one or more key values and the second condition corresponds to a second set of key values, and none of the one or more key values in the first set is in the second set of key values; based on the plurality of conditions, determining a non-contiguous set of not-pruned partitions; wherein a particular partition, of the plurality of partitions, (a) is not a member of said non-contiguous set of not-pruned partitions and (b) is between two partitions of the set of not-pruned partitions based on the order of the plurality of partitions; and during execution of the query, only accessing data items in partitions of said partitioned object that reside in partitions that are members of said non-contiguous set of not-pruned partitions; wherein the method is performed by one or more computing devices.