Hi Murtadha, You're right about the theta sketch, I went and looked. It's getBloomFilterKeyFields(), so the PK, and the only thing reading it is LSMIndexSampleCursor diffing the insert and delete heaps to decide how many samples to pull per component. So it's really a row count estimator, not NDV.
The anti-matter bit is what made HLL click for me. KMV subtracts, HLL can't. So it's less "HLL++ over LSM is hard" and more "HLL is the wrong sketch once you have tombstones." At runtime there are no tombstones, so HLL++ is fine there. One thing I found while poking at this that I think belongs in the proposal. SQL_COUNT_DISTINCT_HASH from ASTERIXDB-3783 is registered with addAgg only, no local/intermediate/global and no serial variant, so the combiner rule can't split it and it can't go through ExternalGroupByPOperator. That's not really fixable, exact distinct has no mergeable state. Which means the sketch version isn't just a faster count distinct, it's the only one that can produce a partial aggregate. So I'm planning on the local/intermediate/global and serial variants from the start rather than bolting them on later. Plumbing-wise it looks like LOCAL_SAMPLING and RANGE_MAP already do exactly this, local agg emits ABinary, global agg merges. On quantiles: agreed, and we're worse off there than on distinct. We have median and that's it, no percentile_cont or percentile_disc. And median sorts to run files per partition then ships them over the network with FileNetworkInputChannel. Meanwhile RANGE_MAP is already picking split points from samples for range partitioning, just not exposed. KLL or t-digest covers both. I'm going to write up runtime approx_count_distinct first, with quantiles sketched as a follow-on in the same proposal so the local/global sketch plumbing gets designed once. Will send it around when it's in shape. On Sat, 12 Sept 2026 at 02:24, Mike Carey <[email protected]> wrote: > +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 > > > >
