Patent ID: 8396862

Claim:
A method of searching a multilevel partitioned database, the method comprising: receiving a query for data from the multilevel partitioned database, wherein the multilevel partitioned database includes multiple rows of partitioned data that are partitioned into plurality of levels, wherein each level is partitioned based on a different column; statically including partitions from one or more first levels of the plurality of levels of the multilevel partitioned database for execution of the query; determining an estimate of partitions from at least a second level in the one or more first level partitions to be dynamically included; dynamically including at least some of the estimated partitions; joining at least two tables of the multilevel partitioned database based on a cost of joining the tables, the cost calculated as a function of the statically included partitions and the estimate of the partitions to be dynamically included; executing the query over the statically included partitions and the dynamically included partitions by; accessing at least one data storage facility; performing the joining of the at least two tables; scanning sorted rows of the at least some of the statically included partitions and dynamically included partitions; and stopping execution of the query when a row from a dynamically included partition indicates a partition that no longer matches a query value, wherein dynamically including partitions occurs while scanning rows of the statically included partitions during execution of the query.