Repository navigation
Overlapping label-column domains alias into one Hydra cell, and the comparator scores it as sketch error #74
Description
Context
Hydra::update writes a record into every non-empty subset of its labels.
The key for a subset is the selected columns joined with ;, in column order.
For a depth-1 subset that key is the bare label string, carrying nothing that identifies which column it came from.
So a value appearing in column 0 and a value appearing in column 1 produce the same subset key whenever the two strings are equal, and both populations land in the same grid cell.
SubpopFrequencyGT builds its ground truth from column label_column alone, so the counts contributed by every other column's depth-1 subset are scored as the sketch's own error.
What is wrong
The shipped example, configs/datagen/hydra_columns.yaml, gives all three columns the default alphabet.
The keys shape renders a rank through a fixed positional encoding, so rank i is always the same string.
Column 1 draws cardinality 50 and column 0 draws cardinality 200, which makes column 1's label set exactly the first 50 strings of column 0's.
The overlap is total and deterministic, not a collision that happens sometimes.
Measured on the invocation the config file itself documents, at rows=3 cols=1024 cell_rows=3 cell_cols=1024:
| label alphabets | are_all |
|---|---|
| shared (as shipped) | 0.742 |
| disjoint per column | 0.159 |
About 79% of the reported error is produced by the workload spec.
The config file's own header comment describes this hazard and the file ships with it anyway.
Every Hydra accuracy number published from this config is dominated by an effect that is not the sketch's.
What needs deciding
Three directions, and they are not the same claim.
-
Give each label column its own
string.alphabetin the config.
Cheapest, and the next person writing a column list steps on it again. -
Make
LabeledWorkload::generaterefuse label columns whose domains overlap.
This says the aliasing is a defect in the workload. -
Model the aliasing in the comparator, so the reported error is the library's real behaviour on overlapping domains.
This says the aliasing is a property of the sketch and belongs in the measurement.
The second and third are opposite stances and only one should be taken.
Worth settling first: whether Manousis et al., VLDB 2022 assumes disjoint column domains.
If the paper assumes it, the workload is wrong and the second direction is right.
If the paper does not, the library has a real limitation and the third direction is measuring it.
Estimate
Config edit: 15 minutes.
Generator validation: 1 to 2 hours.
Comparator modelling: half a day.
Activity
hydra: exact baselines, one per cell type
GordonYuanyc commentedon Jul 30, 2026
The exact baselines added in 435c505 turn this into a measured quantity.
hydra-cms/polarsreproduces Hydra's key space, bare depth-1 label included, and computes the answer exactly. So its error against the comparator's ground truth is entirely aliasing, with no approximation in it.At
rows=3 cols=1024onconfigs/datagen/hydra_columns.yaml:hydra-cms/libhydra-cms/polars(exact)That is 78% of the reported error, which independently confirms the 79% this issue estimated by varying the alphabets. Two different methods, same answer.
The other two:
hydra-hll/polarsreportsare_all = 0.250,hydra-kll/polarsreportsmean_rank_err = 0.00076.With disjoint
string.alphabetper label column all three score exactly zero, which is also the check that the three comparators have no off-by-one.None of this picks the direction. The three options in the issue body still stand, and the shipped config still has the overlap. What changed is that the cost of leaving it is now readable off a row instead of argued about.
GordonYuanyc commentedon Aug 4, 2026
This is resolvable against a rule that already exists, so it needs no new design decision.
docs/aqpbm-core.md§2.6 fixes what the statistic means:A depth-1 Hydra key is the bare label string with no column identity, so the population the sketch answers over is "records where any column holds this value".
SubpopFrequencyGTbuilds ground truth over "records where columnlabel_columnholds this value". Those are two different populations, so the number reported as sketch error is measuring a disagreement about the question, not error in the answer.Two ways out, and either satisfies the rule.
SubpopFrequencyOpswith that meaning.Worth noting what is not the problem: nothing here argues for restricting which label subsets can be asked. A structure that answers for any non-empty subset is doing what the capability describes, and constraining that would design away a capability rather than fix a defect.
The shipped
configs/datagen/hydra_columns.yamlmaking the overlap total and deterministic is a good reproducer to keep.GordonYuanyc commentedon Aug 5, 2026
Citation fix: the statistic definitions are
docs/aqpbm-core.md§2.5, not §2.6. The sections were renumbered.The line this issue turns on is unchanged:
The rest of my earlier comment stands.
fix: give the label columns disjoint alphabets, so the exact baseline…
refactor(bench): one measure helper; HydraKLL on disjoint label alpha…
feat(bench): exact-delta-set row and HydraKLL in the rqe-optimizer co…
docs(hydra): consolidate the Hydra notes already on main
docs: Hydra admission design (accuracy, cost, candidates, sketch-benc…
polars: tag Hydra baseline subset keys by column (#74)
polars: tag Hydra baseline subset keys by column (#74) (#195)
study: --phase hydra on the eval's datasets; Hydra cost rows (#202)
eval: AutoSketch vs. ASAP with Hydra candidates and a roll-up ablatio…