cockroachdb / cockroachdb/cockroach

opt: improve histogram intersection logic for non-numeric types

Open
#159,433 2 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer C-bug O-support P-3 T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

When a filter on a non-numeric type (string, bytes, uuid, inet) intersects a histogram bucket, it is desirable to estimate a number of rows less than the total number in the bucket. Currently, the logic that handles this assumes a uniform distribution of data values across the first 8 bytes (ignoring any common prefix): https://github.com/cockroachdb/cockroach/blob/3209e33b9528c21be13110c1cb99471ebd85c5a8/pkg/sql/sem/tree/datumrange/range.go#L180-L182

This likely works well for UUID columns, but can cause catastrophic underestimates for STRING columns, which are often clustered around certain values. A common example is when the STRING column represents a path. We should consider relaxing the uniformity assumption for non-UUID types.

Jira issue: CRDB-57841

Contributor guide

Open the contributing guide

Research direction

Start in pkg/sql/sem/tree/datumrange/range.go at the histogram intersection logic around lines 180-182, and trace how non-numeric types are estimated. Compare the current treatment of string, bytes, UUID, and inet values, then define and validate an approach that avoids catastrophic underestimates for clustered string data while preserving suitable UUID estimates.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.