Methods and systems for constructing q, θ-optimal histogram buckets

1. A computer-implemented method of optimizing execution of a query that accesses data by a computer, the method comprising:

generating, by a query sever having a processor, a cardinality estimate using a q, θ-optimal histogram comprising a plurality of buckets over a data distribution where, for any cardinality estimate made using the histogram, the cardinality estimate is constrained to obey an acceptability criteria parameterized by q and θ that bounds a ratio error between the cardinality estimate and a true value of the cardinality, q being a factor by which the estimate deviates, at most, from a true value of the cardinality and θ being a threshold value which the cardinality estimate does not exceed, wherein a maximum number of possible query intervals generated in determining the acceptability of the q, θ-optimal histogram is less than quadratic in the number of values for the maximum number of possible query intervals;

using the cardinality estimation generated based on the q, θ-optimal histogram that obeys the acceptability criteria parameterized by q and θ to determine, by the processor of the query server, an optimal query plan for executing the query; and

producing an output of the optimal query plan, wherein a bucket in the plurality of buckets is constructed by incrementally extending a smaller q, θ-acceptable bucket without need to test the new bucket for q, θ-violations whose intervals are wholly contained within the smaller bucket.

2. The method of claim 1 , wherein each of the plurality of buckets is to store at least one of a number of distinct values contained in that bucket and a cumulated frequency of the number of distinct values stored therein.

3. The method of claim 1 , wherein if a bucket in the plurality of buckets contains a q, θ-violation, then that bucket also contains a q, θ′-violation for all θ′ less than θ.

4. The method of claim 1 , wherein for an interval [v l ,v r ) within the plurality of buckets that is a minimal q,θ-violation, if [v r−1 ,v r ) is q-acceptable, then [v l ,v r−1 ) is a q-violation but not a q,θ-violation.

5. The method of claim 1 , further comprising constructing individual bucklets within the plurality of buckets of the q, θ-optimal histogram, including allocating compressed storage for: a cumulative frequency for the plurality of buckets, a cumulative frequency of the individual bucklets, and boundaries of the individual bucklets that are interior to an overall histogram bucket interval of the q, θ-optimal histogram.

6. The method of claim 1 , further comprising:

generating, using the q, θ-optimal histogram, cardinality estimates for at least one query execution plan for executing a query;

using the cardinality estimates to determine an optimal query plan for executing the query; and

producing an output of the optimal query plan.

7. A non-transitory medium having program instructions embodied thereon, the medium comprising:

instructions to generate a cardinality estimate using a q, θ-optimal histogram comprising a plurality of buckets over a data distribution where, for any cardinality estimate made using the histogram, the cardinality estimate is constrained to obey an acceptability criteria parameterized by q and θ that bounds a ratio error between the cardinality estimate and a true value of the cardinality, q being a factor by which the estimate deviates, at most, from a true value of the cardinality and θ being a threshold value which the cardinality estimate does not exceed, wherein a maximum number of possible query intervals generated in determining the acceptability of the q, θ-optimal histogram is less than quadratic in the number of values for the maximum number of possible query intervals;

instructions to use the cardinality estimation generated based on the q, θ-optimal histogram that obeys the acceptability criteria parameterized by q and θ to determine an optimal query plan for executing the query; and

instructions to produce an output of the optimal query plan, wherein a bucket in the plurality of buckets is constructed by incrementally extending a smaller q, θ-acceptable bucket without need to test the new bucket for q,θ-violations whose intervals are wholly contained within the smaller bucket.

8. The medium of claim 7 , wherein each of the plurality of buckets is to store at least one of a number of distinct values contained in that bucket and a cumulated frequency of the number of distinct values stored therein.

9. The medium of claim 7 , wherein if a bucket in the plurality of buckets contains a q, θ-violation, then that bucket also contains a q, θ′-violation for all θ′ less than θ.

10. The medium of claim 7 , wherein for an interval [v l ,v r ) within the plurality of buckets that is a minimal q,θ-violation, if [v r−1 ,v r ) is q-acceptable, then [v l ,v r−1 ) is a q-violation but not a q,θ-violation.

11. The medium of claim 7 , further comprising instructions to construct individual bucklets within the plurality of buckets of the q, θ-optimal histogram, including allocating compressed storage for: a cumulative frequency for the plurality of buckets, a cumulative frequency of the individual bucklets, and boundaries of the individual bucklets that are interior to an overall histogram bucket interval of the q, θ-optimal histogram.

12. The medium of claim 7 , further comprising:

instructions to generate, using the q, θ-optimal histogram, cardinality estimates for at least one query execution plan for executing a query;

instructions to use the cardinality estimates to determine an optimal query plan for executing the query; and

instructions to produce an output of the optimal query plan.

13. A system comprising:

a computing device comprising:

a memory storing processor-executable program code; and

a processor to execute the processor-executable program code in order to cause the computing device to:

generate, by a query sever having a processor, a cardinality estimate using a q, θ-optimal histogram comprising a plurality of buckets over a data distribution where, for any cardinality estimate made using the histogram, the cardinality estimate is constrained to obey an acceptability criteria parameterized by q and θ that bounds a ratio error between the cardinality estimate and a true value of the cardinality, q being a factor by which the estimate deviates, at most, from a true value of the cardinality and θ being a threshold value which the cardinality estimate does not exceed, wherein a maximum number of possible query intervals generated in determining the acceptability of the q, θ-optimal histogram is less than quadratic in the number of values for the maximum number of possible query intervals;

use the cardinality estimation generated based on the q, θ-optimal histogram that obeys the acceptability criteria parameterized by q and θ to determine an optimal query plan for executing the query; and

produce an output of the optimal query plan, wherein a bucket in the plurality of buckets is constructed by incrementally extending a smaller q,θ-acceptable bucket without need to test the new bucket for q,θ-violations whose intervals are wholly contained within the smaller bucket.

14. The system of claim 13 , wherein each of the plurality of buckets is to store at least one of a number of distinct values contained in that bucket and a cumulated frequency of the number of distinct values stored therein, or, in some cases, only a cumulated frequency of the number of distinct values stored therein.

15. The system of claim 13 , wherein a maximum size query interval needed to conclude a guaranteed acceptability is bound by a predetermined formula.

16. The system of claim 13 , wherein for an interval [v l ,v r ) within the plurality of buckets that is a minimal q,θ-violation, if [v r−1 ,v r ) is q-acceptable, then [v l ,v r−1 ) is a q-violation but not a q,θ-violation.

17. The system of claim 13 , wherein the processor further executes the processor-executable program code in order to cause the computing device to construct individual bucklets within the plurality of buckets of the q, θ-optimal histogram, including allocating compressed storage for: a cumulative frequency for the plurality of buckets, a cumulative frequency of the individual bucklets, and boundaries of the individual bucklets that are interior to an overall histogram bucket interval of the q, θ-optimal histogram.

18. The system of claim 13 , wherein the processor further executes the processor-executable program code in order to cause the computing device to:

generate, using the q, θ-optimal histogram, cardinality estimates for at least one query execution plan for executing a query;

use the cardinality estimates to determine an optimal query plan for executing the query; and

produce an output of the optimal query plan.