Replace unordered_set NDV with memory-bounded HyperLogLog estimator #77

Context

PR #75 implemented ANALYZE TABLE using std::unordered_set<std::string> to collect Number of Distinct Values (NDV) per column. Text columns use a 64-char prefix truncation to limit memory.

Problem

For high-cardinality columns (e.g., UUIDs, email addresses, long URLs), the NDV set can grow unbounded. Even with 64-char truncation, distinct strings sharing a prefix will collide and be counted as one, but more importantly the memory usage scales with actual cardinality — potentially many MBs for large tables with high uniqueness.

The current implementation documents this limitation with a comment: "distinct strings with the same 64-char prefix will be counted as one NDV. Use HyperLogLog for production accuracy."

Proposed Solution

Replace the per-column ndv_sets (std::vector<std::unordered_set<std::string>>) with a memory-bounded NDV estimator per column:

Option A: HyperLogLog (recommended)

• Use a fixed-memory HyperLogLog implementation (e.g., ~12KB per column regardless of cardinality)
• Feed each value (or its 64-char prefix for text) into the HLL as a bytes hash
• Use ndv = hll.cardinality() at the end of the scan

Option B: Reservoir sampling with cap

• Keep a random sample of up to N values (e.g., 10k) per column
• Once the cap is reached, switch to approximate counting mode using the sample fraction
• Simpler to implement but less accurate

Implementation Notes

• The change replaces ndv_sets[col_idx].insert(...) with ndv_estimators[col_idx].insert(value_or_prefix)
• At scan end: col_stats[col_idx].ndv = ndv_estimators[col_idx].cardinality()
• execute_analyze() in query_executor.cpp is the primary caller
• No changes needed to catalog.hpp or other components — ndv field type remains std::optional<uint64_t>

Files Affected

• src/executor/query_executor.cpp — execute_analyze() loop (lines ~962-986)

References

• PR Query Optimizer Phase 1: ANALYZE TABLE + Volcano/Vectorized Chooser #75: Query Optimizer Phase 1
• execute_analyze() — current ndv_sets usage (search for ndv_sets)
• include/optimizer/row_estimator.hpp — NDV field in ColumnInfo