chronon icon indicating copy to clipboard operation
chronon copied to clipboard

[Aggregation] Implement DABA Lite Algo and Perf testing

Open cenhao opened this issue 1 year ago • 0 comments

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:

  1. implementing the DABA lite algorithm mentioned in this paper
  2. Performance testing on different conditions (number of events, number of queries, types of aggregation, types of algorithm)
  3. Small lints for code in #452
  4. Incorporated the BufferedIterator suggested by @andrewlee-stripe here

Performance Test Result (measured in millisecond): image

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

cenhao avatar Apr 17 '23 04:04 cenhao