Dual filter histogram optimization
A plurality of histograms are maintained with respect to a dataset. The dataset includes a plurality of data segments. In response to a query that includes a plurality of conditions ordered in an initial sequence, a plurality of corresponding rejection rates is determined for the plurality of conditions based at least in part on the plurality of histograms. The plurality of conditions are re-ordered according to the plurality of corresponding rejection rates associated with the plurality of conditions to form a reordered sequence for the plurality of conditions. The query is executed according to the reordered sequence of the plurality of conditions.
1. A method, comprising:
determining a first hash value and a first shift value for a first query condition of a query;
determining a second hash value and a second shift value for a second query condition of the query;
determining a corresponding rejection rate for the first query condition and for the second query condition based on their corresponding hash values and the shift values;
ordering the first query condition and the second query condition based on rejection rates associated therewith; and
executing the query according to the ordering.
2. The method of claim 1 , further comprising receiving the query comprising the first and the second query conditions.
3. The method of claim 1 , wherein the first and the second hash values are determined based on a corresponding hash function.
4. The method of claim 3 , wherein the corresponding hash function is computed for a query condition comprised of a single value.
5. The method of claim 3 , wherein the corresponding hash function is computed for a query condition comprised of a range of values.
6. The method of claim 3 , wherein the corresponding hash function is a modulo hash function.
7. The method of claim 1 , wherein the first and the second shift values are determined based on a corresponding shift function.
8. The method of claim 7 , wherein the corresponding shift function is computed for a query condition comprised of a single value.
9. The method of claim 7 , wherein the corresponding shift function is computed for a query condition comprised of a range of values.
10. The method of claim 7 , wherein the corresponding shift function for a query condition is based on a range of stored values associated with the query condition.
11. The method of claim 10 , wherein the corresponding shift function is associated with a corresponding shift histogram, wherein the corresponding shift histogram is associated with a plurality of buckets, wherein the corresponding shift function is configured to modify a corresponding range associated with each of the plurality of buckets.
12. The method of claim 11 , wherein the corresponding range associated with each of the plurality of buckets is based on the range of stored values associated with the query condition.
13. The method of claim 1 , wherein the ordering is from a highest rejection rate to a lowest rejection rate.
14. The method of claim 1 , wherein executing the query according to the ordering includes: determining that a hash bit mask associated with a condition of the ordering matches a corresponding hash bit mask of a data segment; and comparing a hash bit mask associated with a next condition of the ordering with a corresponding hash bit mask of the data segment.
15. The method of claim 1 , wherein executing the query according to the ordering includes: determining that a hash bit mask associated with a condition of the ordering mismatch a corresponding hash bit mask of a data segment; and skipping the data segment.
16. The method of claim 1 , wherein executing the query according to the ordering includes inspecting one or more data segments for one or more rows that match the query conditions of the ordered sequence.
17. A system, comprising:
a processor configured to:
determine a first hash value and a first shift value for a first query condition of a query;
determine a second hash value and a second shift value for a second query condition of the query;
determine a corresponding rejection rate for the first query condition and for the second query condition based on their corresponding hash values and the shift values;
order the first query condition and the second query condition based on rejection rates associated therewith; and
execute the query according to the order; and
a memory coupled to the processor and configured to provide the processor with instructions.
18. The system of claim 17 , wherein the processor is further configured to receive the query comprising a plurality of query conditions.
19. The system of claim 18 , wherein the first query condition is a query condition having a highest rejection rate among the plurality of query conditions.
20. A computer program product, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:
determining a first hash value and a first shift value for a first query condition of a query;
determining a second hash value and a second shift value for a second query condition of the query;
determining a corresponding rejection rate for the first query condition and for the second query condition based on their corresponding hash values and the shift values;
ordering the first query condition and the second query condition based on rejection rates associated therewith; and
executing the query according to the ordering.