chronon
chronon copied to clipboard
[Aggregation] Implement DABA Lite Algo and Perf testing
Summary
This PR is built on top of @nikhilsimha's ongoing PR: #452, since that PR is not merged yet, and this change depends on a lot of the work included there. Supposedly, we can merge this PR to include the work there.
Changes of this PR:
- implementing the DABA lite algorithm mentioned in this paper
- Performance testing on different conditions (number of events, number of queries, types of aggregation, types of algorithm)
- Small lints for code in #452
- Incorporated the
BufferedIterator
suggested by @andrewlee-stripe here
Performance Test Result (measured in millisecond):
Why / Goal
The DABA lite algo promises to provide great performance for in-order sliding window aggregation, especially for streaming scenarios.
(Note: sorting is measured separately, even though both DABA & two stack require data to be in order. This is to present the true cost of these two.)
Test Plan
- [x] Added Unit Tests
- [x] Covered by existing CI
- [ ] Integration tested
Reviewers
@nikhilsimha @hzding621 @andrewlee-stripe