Skip to content

Reservoir Sampling is biased, and k = 1 hangs on the default two workers #9503

Description

@Matthew-DWM

What happened?

Reservoir Sampling uses Algorithm R, but it draws the replacement slot from n positions where it needs n + 1: n counts the rows before the current one, so the draw should be rand.nextInt(n + 1) (ReservoirSamplingOpExec.scala:52). The script that Export to Python generates repeats the same bound (ReservoirSamplingOpDesc.scala:86).

Before:  k = 1, rows [10, 20]  ->  row 20 draws nextInt(1), always 0  ->  always keeps 20
After:   k = 1, rows [10, 20]  ->  row 20 draws nextInt(2)            ->  keeps either row, half the time each

Before:  k = 1 on 2 workers  ->  worker 1's share is 0  ->  its first row calls nextInt(0), which throws  ->  run stays Running
After:   same split          ->  worker 1 keeps nothing  ->  run completes with 1 row
  1. The sample is biased. Later rows are kept too often. With k = 1 the first row is never kept: over 4 rows the chances are 0, ⅓, ⅓, ⅓ instead of ¼ each.
  2. A worker with no share of k throws, and the run never finishes. k is split across the operator's workers (ReservoirSamplingOpExec.scala:34), and Reservoir Sampling runs on two by default (application.conf:23). The failing worker reports IllegalArgumentException: bound must be positive to the console and pauses itself (DataProcessor.scala:338-346), so the run neither completes nor fails. Any k below the worker count does the same.

A run (CSV File Scan of 1,000 rows → Reservoir Sampling, default two workers):

k Result
1 "bound must be positive" in the console after 1 s; Reservoir Sampling still Running after 45 s
0 (typed in; the property starts empty) the same, from both workers
2 completes with 2 rows

Expected:

  • Within each worker, every row is equally likely to be kept: a row at position n ≥ k enters the reservoir with probability k / (n + 1).
  • A worker with no share keeps nothing, so k = 1 completes.
  • The exported script keeps the same rows as the engine.
  • A sample size below 1 stays refused by both, as the review of feat(workflow-operator): export the join and set operators as Python #8506 settled, but with a message that says why.
  • Loop-variable binding of k is unchanged.
  • Seeded runs will return different rows than before; that is the correction, not a regression.

How to reproduce?

  1. CSV File Scan over any CSV with a few hundred rows, then Reservoir Sampling with k = 1. Leave the default worker count.
  2. Run. Reservoir Sampling's console shows java.lang.IllegalArgumentException: bound must be positive, and the operator stays Running until the run is killed.
  3. For the bias: with one worker per operator (CONSTANTS_NUM_WORKER_PER_OPERATOR=1), k = 1 over a two-row file always keeps the second row.
  4. Without a deployment:
    • Serialize a ReservoirSamplingOpDesc with k = 1 using JSONUtils.objectMapper, and build ReservoirSamplingOpExec(descString, idx = 0, workerCount = 1). Call open(), pass rows 10 and 20 through processTuple, then drain onFinish(0): it always returns 20.
    • Build another executor with idx = 1, workerCount = 2. Its first processTuple throws IllegalArgumentException: bound must be positive.

Version/Branch

1.4.0-incubating-SNAPSHOT (main)

Commit Hash (Optional)

No response

What browsers are you seeing the problem on?

No response

Relevant log output

java.lang.IllegalArgumentException: bound must be positive

Activity

  1. added theissue type on Nov 16, 2026
  2. Matthew-DWM commented on Nov 16, 2026

    @Matthew-DWM
    Author

    /take

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