dlyubimov/HBase-Lattice — Issue #4: complement optimization
Author: dlyubimov
Created: 2011-12-22 19:08:57+00:00
State: open

some aggregate functions are allowing complement scan optimizations esp. w.r.t. to hierarchies it might be useful.

E.g. a slice along time hierarchy for a month with a timezone GMT-8 can be decomposed with 3 short scans:

-- one month key scan (only one month key. If a proper cuboid is available, that would be exactly one hbase key scan);
-- a set-merge scan for keys corresponding to 8 more hours after the month end (in UTC) becasue we celebrate Christmas 8 hours after London here on Pacific coast;
-- a set-complement scan for keys corresponding to 8 hours after the month start (in UTC) because hour month here stars 8 hours later than it does in London.

The essense of optimization is that merge-only scan would need to scan ~30x24 hour keys, there's no other route to do it; but complement scan would scan 1+8+8 keys and it would do it in parallel. We had exactly that scheme in prototype but it is not really implemented in HBL optimizer (yet)