Performance-related estimation using pseudo-ranked trees

Claim 3

The method of claim 1 wherein: said tree index is a pseudo-ranked tree; said weight values are approximations of said statistics; the method further includes the steps of: reading a second set of weight values associated with branches below said node by sampling said index tree below said node; generating a correction factor based on said second set of weight values; and adjusting said first set of weight values based on said correction factor to produce a corrected set of weight values; and said step of estimating the cost of using said tree index based on said first set of weight values includes the step of estimating the cost of using said tree index based on said corrected set of weight values.

Claim 4

The method of claim 2 wherein: the method comprises the step of reading a third set of weight values associated with branches below said node by taking a second sample below said node; and the step of generating a correction factor based on said second set of weight values includes the step of generating a correction factor based on said second set of weight values and said third set of weight values.

Claim 5

The method of claim 3 wherein the step of generating a correction factor based on said second set of weight values and said third set of weight values includes the steps of: generating a first correction factor based on said second set of weight values; generating a second a correction factor based on said third set of weight values; and generating an average correction factor based on said first correction factor and said second correction factor.

Claim 6

The method of claim 2 wherein the step of reading a second set of weight values associated with branches below said node by sampling said index tree below said node includes the steps of: selecting a first branch from said node; descending said first branch to a second node; and reading weight values associated with all branches extending from said second node, wherein said second set of weight values includes said weight values associated with all branches extending from said second node.

Claim 7

The method of claim 5 wherein the step of generating a correction factor based on said second set of weight values includes the steps of: determining a ratio between the weight value of the first branch and a sum of the weight values associated with all branches extending from said second node; and generating said correction factor based on said ratio.

Claim 8

The method of claim 6 wherein: the step of reading a second set of weight values associated with branches below said node by sampling said index tree below said node includes the steps of: selecting a second branch from said second node; descending said second branch to a third node; and reading weight values associated with all branches extending below said third node; wherein the step of generating a correction factor based on said second set of weight values includes the steps of: determining a second ratio between the weight value of the second branch and a sum of the weight values associated with all branches extending below said third node; and averaging said ratio and said second ratio to generate an average ratio.

Claim 9

The method of claim 1 wherein: said first set of weight values represent how many data item identifiers are stored in said tree index below said first branch, said second branch, and any intervening branches; and the step of reading a first set of weight values associated with said first branch, said second branch, and any intervening branches that reside between said first branch and said second branch, includes the steps of reading a first weight value that represents how many data item identifiers are stored in said tree below said first branch; and reading a second weight value that represents how many data item identifiers are stored in said tree below said second branch.

Claim 10

The method of claim 1 further comprising the step of identifying an interval associated with said query by performing the steps of: inspecting branch nodes that reside at a first level of the tree; evaluating separators stored in said branch nodes based on said range limitation; if any separators evaluate to true based on said range limitation, then classifying all intervals between two separators that evaluate to true as T intervals; classifying all intervals between two separators that evaluate to false as F intervals; and classifying all intervals between a separator that evaluates to false and a separator that evaluates to true as an M interval.

Claim 11

The method of claim 9 further comprising the steps of: selecting a branch that is associated with an M interval; descending the branch to a lower branch node; and evaluating separators in said lower branch node based on said range limitation.

Claim 14

The method of claim 11 further comprising the steps of: traversing the tree index to a node that has a first set of branches, said first set of branches including a first branch associated with a first interval that bounds a first endpoint of the specified interval; a second branch associated with a second interval that bounds a second endpoint of the specified interval; and zero or more intervening branches that are associated with intervals between said first interval and said second interval; and wherein said branch is a branch within said first set of branches.

Claim 15

The method of claim 11 further comprising the step of: reading a third set of weight values, wherein said third set of weight values are weight values associated with one or more branches that reside on a second path that descends from said second node; wherein the step of adjusting said first weight value based on said second set of weight values to produce an adjusted weight value includes the steps of: generating a first correction ratio based on said first weight value and said second set of weight values; generating a second correction ratio based on said first weight value and said third set of weight values; generating an average correction ratio based on said first correction ratio and said second correction ratio; and adjusting said first weight value based on said average correction ratio.

Claim 16

The method of claim 11 wherein the step of reading a second set of weight values includes the steps of: reading weight values associated with all branches extending from said second node; generating a correction ratio based on said first weight value and a sum of the weight values associated with all branches extending from said second node; and wherein the step of adjusting said first weight value based on said second set of weight values includes the step of adjusting said first weight value based on said correction ratio.

Claim 17

The method of claim 14 wherein the step of reading a second set of weight values further includes the steps of: selecting a second branch that extends from said second node; reading a second weight value associated with said second branch; descending said second branch to a third node; reading weight values associated with all branches extending from said third node; generating a second correction ratio based on said second weight and a sum of the weight values associated with all branches extending from said third node; generating a correction factor based on said correction ratio and said second correction ratio; and wherein the step of adjusting said first weight value based on said second set of weight values includes the step of adjusting said first weight value based on said correction factor.

Claim 18

A computer-readable medium having stored thereon sequences of instructions for estimating a cost of using a tree index to process a query that includes at least one interval restriction, the sequences of instructions including instructions for performing the steps of: traversing the tree index to a node that has a first branch associated with a first interval into which a first endpoint of the interval restriction falls, and a second branch associated with a second interval into which a second endpoint of the interval restriction falls; reading a first set of weight values associated with said first branch, said second branch, and any intervening branches that reside between said first branch and said second branch, wherein said first set of weight values represent statistics about information stored in said tree index below said first branch, said second branch, and any intervening branches; and estimating the cost of using said tree index based on said first set of weight values.

Claim 19

A computer-readable medium having stored thereon sequences of instructions for estimating a cost of using a tree index to process a query that includes at least one interval restriction, the sequences of instructions including instructions for performing the steps of: traversing the tree index to a node that has a first branch associated with a first interval into which a first endpoint of the interval restriction falls, and a second branch associated with a second interval into which a second endpoint of the interval restriction falls; reading a first set of weight values associated with said first branch, said second branch, and any intervening branches that reside between said first branch and said second branch, wherein said first set of weight values represent statistics about information stored in said tree index below said first branch, said second branch, and any intervening branches; and estimating the cost of using said tree index based on said first set of weight values.

Claim 20

The computer-readable medium of claim 16 wherein: said tree index is a pseudo-ranked tree; said weight values are approximations of said statistics; the sequences of instructions further include instructions for performing the steps of: reading a second set of weight values associated with branches below said node by sampling said index tree below said node; generating a correction factor based on said second set of weight values; and adjusting said first set of weight values based on said correction factor to produce a corrected set of weight values; and said step of estimating the cost of using said tree index based on said first set of weight values includes the step of estimating the cost of using said tree index based on said corrected set of weight values.

Claim 21

The computer-readable medium of claim 17 wherein: the sequences of instructions further comprise instructions for performing the step of reading a third set of weight values associated with branches below said node by taking a second sample below said node; and the step of generating a correction factor based on said second set of weight values includes the step of generating a correction factor based on said second set of weight values and said third set of weight values.

Claim 22

The computer-readable medium of claim 18 wherein the step of generating a correction factor based on said second set of weight values and said third set of weight values includes the steps of: generating a first correction factor based on said second set of weight values; generating a second a correction factor based on said third set of weight values; and generating an average correction factor based on said first correction factor and said second correction factor.

Claim 23

The method of claim 17 wherein the step of reading a second set of weight values associated with branches below said node by sampling said index tree below said node includes the steps of: selecting a first branch from said node; descending said first branch to a second node; and reading weight values associated with all branches extending from said second node, wherein said second set of weight values includes said weight values associated with all branches extending from said second node.

Claim 24

The computer-readable medium of claim 20 wherein the step of generating a correction factor based on said second set of weight values includes the steps of: determining a ratio between the weight value of the first branch and a sum of the weight values associated with all branches extending from said second node; and generating said correction factor based on said ratio.

Claim 25

The computer-readable medium of claim 21 wherein: the step of reading a second set of weight values associated with branches below said node by sampling said index tree below said node includes the steps of: selecting a second branch from said second node; descending said second branch to a third node; and reading weight values associated with all branches extending below said third node; wherein the step of generating a correction factor based on said second set of weight values includes the steps of: determining a second ratio between the weight value of the second branch and a sum of the weight values associated with all branches extending below said third node; and averaging said ratio and said second ratio to generate an average ratio.

Claim 26

The computer-readable medium of claim 16 wherein: said first set of weight values represent how many data item identifiers are stored in said tree index below said first branch, said second branch, and any intervening branches; and the step of reading a first set of weight values associated with said first branch, said second branch, and any intervening branches that reside between said first branch and said second branch, includes the steps of reading a first weight value that represents how many data item identifiers are stored in said tree below said first branch; and reading a second weight value that represents how many data item identifiers are stored in said tree below said second branch.

Claim 27

The computer-readable medium of claim 16 further comprising sequences of instructions for performing the step of identifying an interval associated with said query by performing the steps of: inspecting branch nodes that reside at a first level of the tree; evaluating separators stored in said branch nodes based on said range limitation; if any separators evaluate to true based on said range limitation, then classifying all intervals between two separators that evaluate to true as T intervals; classifying all intervals between two separators that evaluate to false as F intervals; and classifying all intervals between a separator that evaluates to false and a separator that evaluates to true as an M interval.

Claim 28

The computer-readable medium of claim 24 further comprising sequences of instructions for performing the steps of: selecting a branch that is associated with an M interval; descending the branch to a lower branch node; and evaluating separators in said lower branch node based on said range limitation.

Claim 29

A computer system comprising: one or more memory devices; a tree index stored in said one or more memory devices; a processor coupled to said one or more memory devices; a sequence of instructions stored in said one or more memory devices for estimating a cost of using a tree index to process a query that includes at least one interval restriction, the sequences of instructions including instructions which, when executed by said processor, cause said processor to perform the steps of: traversing the tree index to a node that has a first branch associated with a first interval into which a first endpoint of the interval restriction falls, and a second branch associated with a second interval into which a second endpoint of the interval restriction falls; reading a first set of weight values associated with said first branch, said second branch, and any intervening branches that reside between said first branch and said second branch, wherein said first set of weight values represent statistics about information stored in said tree index below said first branch, said second branch, and any intervening branches; and estimating the cost of using said tree index based on said first set of weight values.

Claim 30

A computer system comprising: one or more memory devices; a tree index stored in said one or more memory devices; a processor coupled to said one or more memory devices; a sequence of instructions stored in said one or more memory devices for estimating a cost of using a tree index to process a query that includes at least one interval restriction, the sequences of instructions including instructions which, when executed by said processor, cause said processor to perform the steps of: traversing the tree index to a node that has a first branch associated with a first interval into which a first endpoint of the interval restriction falls, and a second branch associated with a second interval into which a second endpoint of the interval restriction falls; reading a first set of weight values associated with said first branch, said second branch, and any intervening branches that reside between said first branch and said second branch, wherein said first set of weight values represent statistics about information stored in said tree index below said first branch, said second branch, and any intervening branches; and estimating the cost of using said tree index based on said first set of weight values.

Claim 31

The computer system of claim 26 wherein: said tree index is a pseudo-ranked tree; said weight values are approximations of said statistics; the sequences of instructions further include instructions for performing the steps of: reading a second set of weight values associated with branches below said node by sampling said index tree below said node; generating a correction factor based on said second set of weight values; and adjusting said first set of weight values based on said correction factor to produce a corrected set of weight values; and said step of estimating the cost of using said tree index based on said first set of weight values includes the step of estimating the cost of using said tree index based on said corrected set of weight values.

Claim 32

The computer system of claim 27 wherein: the sequences of instructions further comprise instructions for performing the step of reading a third set of weight values associated with branches below said node by taking a second sample below said node; and the step of generating a correction factor based on said second set of weight values includes the step of generating a correction factor based on said second set of weight values and said third set of weight values.

Claim 33

The computer system of claim 28 wherein the step of generating a correction factor based on said second set of weight values and said third set of weight values includes the steps of: generating a first correction factor based on said second set of weight values; generating a second a correction factor based on said third set of weight values; and generating an average correction factor based on said first correction factor and said second correction factor.

Claim 34

A computer system comprising: one or more memory devices; a tree index stored in said one or more memory devices; a processor coupled to said one or more memory devices, said processor being configured to generate an estimate of how many data item identifiers stored in said tree index fall within a specified interval by executing the steps of: establishing weights for branches within said tree, wherein the weight value associated with each branch is an estimate of how many data item identifiers are stored in leaf nodes that reside below the branch; reading a first weight value associated with a branch that corresponds to an interval that has at least one endpoint which falls within said specified interval; following said branch to a second node; reading a second set of weight values, wherein said second set of weight values are weight values associated with one or more branches that reside on a path that descends from said second node; adjusting said first weight value based on said second set of weight values to produce an adjusted weight value; and generating said estimate based on said adjusted weight value.

Claim 35

A computer system comprising: one or more memory devices; a tree index stored in said one or more memory devices; a processor coupled to said one or more memory devices, said processor being configured to generate an estimate of how many data item identifiers stored in said tree index fall within a specified interval by executing the steps of: establishing weights for branches within said tree, wherein the weight value associated with each branch is an estimate of how many data item identifiers are stored in leaf nodes that reside below the branch; reading a first weight value associated with a branch that corresponds to an interval that has at least one endpoint which falls within said specified interval; following said branch to a second node; reading a second set of weight values, wherein said second set of weight values are weight values associated with one or more branches that reside on a path that descends from said second node; adjusting said first weight value based on said second set of weight values to produce an adjusted weight value; and generating said estimate based on said adjusted weight value.

Claim 36

The computer system of claim 30 wherein the processor is further configured to execute the steps of: traversing the tree index to a node that has a first set of branches, said first set of branches including a first branch associated with a first interval that bounds a first endpoint of the specified interval; a second branch associated with a second interval that bounds a second endpoint of the specified interval; and zero or more intervening branches that are associated with intervals between said first interval and said second interval; and wherein said branch is a branch within said first set of branches.

Claim 37

The computer system of claim 30 wherein the processor is further configured to execute the step of: reading a third set of weight values, wherein said third set of weight values are weight values associated with one or more branches that reside on a second path that descends from said second node; wherein the step of adjusting said first weight value based on said second set of weight values to produce an adjusted weight value includes the steps of: generating a first correction ratio based on said first weight value and said second set of weight values; generating a second correction ratio based on said first weight value and said third set of weight values; generating an average correction ratio based on said first correction ratio and said second correction ratio; and adjusting said first weight value based on said average correction ratio.