+1 to start with a runtime-based version first. It would also be interesting to look at scalable approximate quantiles, perhaps?
On 9/9/26 5:28 AM, Murtadha Hubail wrote:
Hi Vivek, It would be great to add support for appropriate aggregate functions, starting with approx_count_distinct. Most OLAP systems rely on HyperLogLog++ and/or Theta Sketches to handle this efficiently. Note that our current Theta Sketch implementation in the LSM layer only covers the primary key, rather than every field. Maintaining pre-computed HLL++ sketches over LSM-based storage introduces significant challenges (especially with updates and deletes). I suggest starting with a proposal for a runtime-based approx_count_distinct function first. This gives us quick dynamic aggregations before we evaluate pre-aggregated storage options. -Murtadha ________________________________ From: Vivek Gangavarapu <[email protected]> Sent: Monday, 07 September 2026 07:52:17 To: [email protected] <[email protected]> Subject: [DISCUSS] Approximate aggregates Hi all, I want to discuss about the approximate aggregates. We have no approximate aggregates at all - no approx_count_distinct, no approximate percentiles, nothing. Spark, Trino, BigQuery, Snowflake, DuckDB and ClickHouse all ship these. The interesting part is that we already built the hard bit. ASTERIXDB-3702 added theta sketches to the LSM layer - ThetaSampler and ThetaEstimator in hyracks-storage-am-lsm-common. They're mergeable, they're tested, and they're already written into disk component metadata. But nothing above storage can see them. The query layer has no access, and the CBO doesn't use them either - it still estimates distinct counts by running a sampling query. Three things that could come out of that, roughly in order of effort: - approx_count_distinct() as a SQL++ aggregate. A sketch has fixed-size state, which is exactly what our aggregate framework wants, so unlike exact COUNT(DISTINCT) it would get hash group-by and two-step aggregation without any special casing. - Sketches as values you can store - init, merge, estimate - so a rollup table can keep partial sketches and combine them later. That's what makes this useful for time-partitioned data rather than just a faster count. - Let the CBO read the sketches we already keep instead of sampling for it. Ian, this looks adjacent to your distinct cardinality WIP (21097) - curious whether you'd been thinking along the same lines. What does everyone think? Thanks, Vivek
