You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "daescha (via GitHub)" <gi...@apache.org> on 2026/10/17 06:57:09 UTC
[PR] fix(hll): union sketches with different lgK [datasketches-go]
daescha opened a new pull request, #198:
URL: https://github.com/apache/datasketches-go/pull/198
## Summary
- **`fix(hll)`: union sketches with different lgK**
- `unionImpl` sets `bit3 = 8` when `srcLgK < gadgetLgK`, as Java and C++ do. Before this, cases 8, 10, 12 and 14 were never selected, so a smaller-lgK source merged as if both had the same lgK.
- Ports `downsample` from Java `HllUnion` and uses it in cases 12, 16/18 and 22. These returned `not implemented`.
- `mergeHlltoHLLmode` handles `srcLgK > tgtLgK` for HLL_8 (case 4) and HLL_4/HLL_6 (cases 12/13), by masking the target slot as Java does.
- `checkBasicUnion` builds `h2` with `lgK2` and expects the control lgK instead of a hard-coded 7.
- **`fix(hll)`: add `nextValid` to the HLL_4 pair iterator.** Downsampling an HLL_4 sketch iterates its valid pairs, and the base method panicked with `override me`. A slot lookup error makes `nextValid` return true, so `getPair` returns the error. The panicking base stub on `hllPairIterator` is removed.
## Why
Combining HLL sketches built with different lgK is a normal union in Java and C++. In Go it either errors or returns a wrong estimate:
| Union | Java / C++ | `main` |
|---|---|---|
| source lgK > `lgMaxK` (cases 16/18/22) | downsample to `lgMaxK` | `not implemented` |
| source lgK < gadget lgK, gadget in HLL mode (case 12) | downsample the gadget | merged as equal lgK: wrong estimate and bounds |
| HLL_4/6 source, lgK > gadget lgK | fold registers with a slot mask | `not implemented` |
## Validation
- `go test ./hll/` with the TCK snapshots from `make download-snapshots`.
- `golangci-lint run ./...`
- New `TestUnionMixedLgK` covers lgK pairs (10,12), (12,10), (12,12) and (4,21), `lgMaxK` 8 to 14, n = 100, 3000 and 50000, and every pair of source types.
- Each union is compared with the same values built directly at the smallest lgK. It checks the result lgK and the composite estimate.
- On `main`, 198 of 432 subtests fail.
- Cross-checked against datasketches-cpp through the datasketches-postgresql extension: 55 sketches, 79 union groups, lgK 4 to 21, HLL_4/6/8, LIST, SET and HLL modes.
- Every mixed-lgK union matches the C++ result byte for byte.
- On `main`, 10 groups fail and 2 return wrong values.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(hll): union sketches with different lgK [datasketches-go]
Posted by "proost (via GitHub)" <gi...@apache.org>.
proost commented on code in PR #198:
URL: https://github.com/apache/datasketches-go/pull/198#discussion_r4302104086
##########
hll/union_test.go:
##########
@@ -46,6 +46,53 @@ func TestUnions(t *testing.T) {
checkBasicUnion(t, n1, n2, lgK1, lgK2, lgMaxK, t1, t2, rt)
}
+func TestUnionMixedLgK(t *testing.T) {
+ for _, tc := range []struct{ lgK1, lgK2 int }{{10, 12}, {12, 10}, {12, 12}, {4, 21}} {
+ for _, lgMaxK := range []int{8, 11, 12, 14} {
+ for _, n := range []int{100, 3000, 50000} {
+ for t1 := 0; t1 < 3; t1++ {
+ for t2 := 0; t2 < 3; t2++ {
+ name := fmt.Sprintf("lgK%d_%d/max%d/n%d/t%d_%d", tc.lgK1, tc.lgK2, lgMaxK, n, t1, t2)
+ t.Run(name, func(t *testing.T) {
+ checkUnionMatchesControl(t, n, tc.lgK1, tc.lgK2, lgMaxK, TgtHllType(t1), TgtHllType(t2))
+ })
+ }
+ }
+ }
+ }
+ }
+}
+
+// checkUnionMatchesControl compares registers of a union against the same values built at the smallest lgK.
+func checkUnionMatchesControl(t *testing.T, n, lgK1, lgK2, lgMaxK int, type1, type2 TgtHllType) {
Review Comment:
You commented that registers comparions, but actually not. can you added too?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(hll): union sketches with different lgK [datasketches-go]
Posted by "proost (via GitHub)" <gi...@apache.org>.
proost merged PR #198:
URL: https://github.com/apache/datasketches-go/pull/198
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(hll): union sketches with different lgK [datasketches-go]
Posted by "daescha (via GitHub)" <gi...@apache.org>.
daescha commented on code in PR #198:
URL: https://github.com/apache/datasketches-go/pull/198#discussion_r4306053725
##########
hll/union_test.go:
##########
@@ -46,6 +46,53 @@ func TestUnions(t *testing.T) {
checkBasicUnion(t, n1, n2, lgK1, lgK2, lgMaxK, t1, t2, rt)
}
+func TestUnionMixedLgK(t *testing.T) {
+ for _, tc := range []struct{ lgK1, lgK2 int }{{10, 12}, {12, 10}, {12, 12}, {4, 21}} {
+ for _, lgMaxK := range []int{8, 11, 12, 14} {
+ for _, n := range []int{100, 3000, 50000} {
+ for t1 := 0; t1 < 3; t1++ {
+ for t2 := 0; t2 < 3; t2++ {
+ name := fmt.Sprintf("lgK%d_%d/max%d/n%d/t%d_%d", tc.lgK1, tc.lgK2, lgMaxK, n, t1, t2)
+ t.Run(name, func(t *testing.T) {
+ checkUnionMatchesControl(t, n, tc.lgK1, tc.lgK2, lgMaxK, TgtHllType(t1), TgtHllType(t2))
+ })
+ }
+ }
+ }
+ }
+ }
+}
+
+// checkUnionMatchesControl compares registers of a union against the same values built at the smallest lgK.
+func checkUnionMatchesControl(t *testing.T, n, lgK1, lgK2, lgMaxK int, type1, type2 TgtHllType) {
Review Comment:
done
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org