Patent ID: 8290917

Claim:
A computer storage medium storing computer-executable instructions for performing a method comprising: receiving a query that identifies an input data source; partitioning the input data source into a plurality of partitions, each of the partitions including a set of data elements with an associated set of indices for indicating an ordering of the data elements; identifying a plurality of index states for the set of indices for each partition, wherein the plurality of index states for each partition include a first state indicating whether the set of indices for the partition is normalized, a second state indicating whether the set of indices for the partition is ordered, and a third state indicating whether the set of indices for the partition is contiguously partitioned; identifying a query type for a query operator in the received query; identifying a set of admissible index states for the query operator based on the identified query type; comparing the identified plurality of index states to the set of admissible index states; determining prior to execution of the query whether a reordering of data elements will be performed based on the identified query type and the comparison of the identified plurality of index states to the set of admissible index states; and reordering the data elements in at least one of the partitions prior to execution of the query when it is determined based on the identified query type and the comparison that reordering will be performed.