Skip to content

Reservoir sampling is biased toward later rows #9569

Description

@Ma77Ball

What happened?

The Reservoir Sampling operator does not produce a uniform random sample. The replacement probability is off by one, so the first input tuple after the reservoir fills is always kept (probability 1.0 instead of count/(count+1)), biasing the final sample toward tuples that arrive later in the stream.

How to reproduce?

Run a workflow with a Reservoir Sampling operator (small k, e.g. 5) over an input much larger than k (100+ rows); across runs the sampled rows skew toward the end of the input. In code, ReservoirSamplingOpExec.processTuple draws rand.nextInt(n) where n is the number of tuples already seen, instead of the Algorithm R bound nextInt(n+1).

Version/Branch

main

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions