lgK must be between 4 and 21 inclusive: ThetaSketch.Builder setLgK validation error

Answer to the question

The lgK value you pass to ThetaSketch.Builder.setLgK() is the only knob that controls the sketch’s memory usage, relative error, and the stability of page boundaries. The library enforces that lgK be between 4 and 21 inclusive; values outside this range throw an IllegalArgumentException with the message "lgK must be between 4 and 21 inclusive".

Trade‑offs of a global fixed lgK

• Memory: The sketch allocates k = 2^lgK slots regardless of the actual cardinality. A fixed lgK of 20 uses 1,048,576 slots, which is about 8 MiB for 64‑bit longs.
• Accuracy: The relative error is roughly 1/√k. With lgK = 20 the error is about 0.3 %; with lgK = 10 it is about 3 %.
• Pagination stability: Because every query uses the same sketch configuration, the estimated distinct count for a given set of rows is reproducible. Page boundaries shift only when the underlying data changes, not when the sketch is re‑instantiated.

Trade‑offs of adapting lgK per query

• Memory: For small result sets you can choose a low lgK (e.g. 4 or 5) and keep memory usage tiny (4–32 slots).
• Accuracy: The relative error grows as you reduce lgK. A low lgK can produce estimates that differ by 20–25 % from the true count, which can move page boundaries between runs.
• Pagination consistency: Because the sketch’s error changes, the same query may return a different number of estimated distinct elements on successive runs, causing the page number for a given item to shift.

Effect on theoretical error bound

The error bound for a ThetaSketch is approximately 1/√k. Changing lgK from 4 to 21 reduces the bound from about 25 % to 2 %. The page‑count estimate is directly proportional to the sketch estimate, so tighter error bounds translate into more stable page totals.

Recommended approach

1. Determine the worst‑case cardinality you expect across all queries. This value will guide the choice of a fixed lgK that keeps error below your tolerance.
2. Pick a single lgK that satisfies the worst‑case cardinality and your memory budget. For example, if you can afford 4 MiB and need <1 % error, lgK = 15 (k = 32,768) gives an error of ~0.5 %.
3. Instantiate one sketch per query using that lgK. Reuse the same sketch instance for repeated executions of the same query to avoid re‑instantiation overhead.
4. Cache the estimate if you need to serve multiple pages from the same query result set; this keeps the page count stable across page loads.
5. Do not merge sketches with different lgK values; if you need to combine results from multiple partitions, ensure each partition uses the same lgK or rebuild a new sketch with the target lgK.

Missing diagnostic detail

To give a more concrete lgK recommendation, could you share the maximum expected distinct count for the largest query you plan to paginate? Knowing that number will let us compute the exact lgK that satisfies a target error bound while staying within your memory limits.