You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@asterixdb.apache.org by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu> on 2026/08/06 14:36:39 UTC
[M] Change in asterixdb[master]: [NO ISSUE][STO] Scale sample give-up cap by target, not tuple population
From Ritik Raj <ri...@couchbase.com>:
Ritik Raj has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21499?usp=email )
Change subject: [NO ISSUE][STO] Scale sample give-up cap by target, not tuple population
......................................................................
[NO ISSUE][STO] Scale sample give-up cap by target, not tuple population
The random sample cursors bound Phase-1 collection with a give-up
threshold. It was scaled to the component tuple-population ceiling
(leafPages * maxLeafTupleCount ~= total tuples), so a near-exhaustive or
over-estimated component whose target is unreachable ground ~32 * total
tuples attempts before giving up, regardless of how small the target
was.
That attempt count is the same for row and column, but a column attempt
re-inits the PK definition-level decoders and walks the PK column, far
heavier than a row slot lookup. So after a mutation pass (deletes +
upserts shadow old-component tuples), a column component that cannot
fill its target ground for minutes-to-hours, making random-mode ANALYZE
on column datasets 10-30x slower than full scan; row was unaffected.
Fix: scale the give-up threshold by the sample target instead:
cap = MULTIPLIER * max(leafPages, componentSampleCardinality)
The coupon-collector tail for the last few tuples grows with the target,
not the population, so this keeps enough headroom to reach a reachable
target while bounding the exhausted case to O(target) draws. The
leafPages floor lets a tiny target still probe every page. Applied to
both ColumnBtreeSampleCursor and DiskBTreeSampleCursor. Debug lines now
log target, attempts, and the cap so a future grind is visible.
Ext-ref: MB-73172
Co-Authored-By: Claude Opus 4.8 <no...@anthropic.com>
Change-Id: I957d74dd87156d9545f52e05b9e2819566469c27
---
M hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeSampleCursor.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/btree/ColumnBtreeSampleCursor.java
2 files changed, 66 insertions(+), 55 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/99/21499/1
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeSampleCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeSampleCursor.java
index ab7c344..00b940d 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeSampleCursor.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeSampleCursor.java
@@ -67,21 +67,17 @@
// u64: (pageId << 32) | tupleIndex
private final LongSet seenTupleIndexes;
// Sampling related fields
- // Multiplier applied to the component tuple-population ceiling to derive the
- // effective consecutive-miss give-up threshold (see doOpen). Empirically the
- // reservoir stalls at roughly threshold/3 when the threshold is too tight, so a
- // multiple well above 3 is needed to reliably reach near-exhaustive targets.
- @AiProvenance(agent = AiProvenance.Agent.CLAUDE_OPUS_4_8, tool = AiProvenance.Tool.CLAUDE_CODE_UI, contributionKind = AiProvenance.ContributionKind.GENERATED, notes = "Population-scaled give-up threshold to stop near-exhaustive samples truncating at ~500 attempts")
- private static final long POPULATION_ATTEMPT_MULTIPLIER = 32L;
+ // Multiplier applied to the sample target (see doOpen) to derive the effective give-up threshold.
+ // Empirically the reservoir stalls at roughly threshold/3 when the threshold is too tight, so a multiple
+ // well above 3 is needed to reliably reach near-exhaustive targets.
+ private static final long SAMPLE_ATTEMPT_MULTIPLIER = 32L;
private final int maxLeafFindingAttempts;
- // Effective consecutive-miss give-up threshold, scaled to the component's tuple
- // population in doOpen(). maxLeafFindingAttempts alone is a fixed floor that
- // silently truncates near-exhaustive samples (target close to the component's
- // live-tuple count): as the reservoir fills, random draws increasingly hit
- // already-seen tuples, so the consecutive-miss streak needed to find the last
- // few tuples grows with the population. Scaling the cap to the population keeps
- // collection from stopping short while still bounding the genuinely-exhausted
- // case (target >= population) to O(population) draws.
+ // Effective consecutive-miss give-up threshold, scaled to the sample target in doOpen().
+ // maxLeafFindingAttempts alone is a fixed floor that silently truncates near-exhaustive samples (target
+ // close to the component's live-tuple count): as the reservoir fills, random draws increasingly hit
+ // already-seen tuples, so the consecutive-miss streak needed to find the last few tuples grows with the
+ // target. Scaling the cap to the target keeps collection from stopping short while still bounding the
+ // genuinely-exhausted case to O(target) draws.
private int effectiveMaxLeafFindingAttempts;
private final long componentSampleCardinality;
private final Random randomNumGen;
@@ -184,27 +180,28 @@
// number of interior pages (~0.4 % of total pages for typical fan-out).
// The resulting array gives perfectly uniform random access to any leaf.
leafPageIds = bTree.enumerateLeafPageIdsCompact(rootPageId, bTreeOpCtx, bufferCacheOpCtx);
- // Scale the give-up threshold to a multiple of the component's tuple-population
- // ceiling (leaf pages x max tuples/leaf). The per-component sample target never
- // exceeds the population (the caller caps it at the component's live-tuple
- // estimate), so a target is always reachable; the loop must not give up before
- // reaching it. Random draws with a growing already-seen set miss increasingly
- // often as the reservoir fills, so the consecutive-miss streak needed to find
- // the last few tuples grows super-linearly in the population - a give-up
- // threshold equal to the population alone stops far short (observed collected
- // ~= threshold/3). POPULATION_ATTEMPT_MULTIPLIER buys enough headroom to reach
- // the target, while still bounding the genuinely-exhausted case (target >
- // available, e.g. a "high" sample of a tiny dataset) to O(multiplier x
- // population) draws. Computed as long, then clamped to int: for huge components
- // the product overflows int, but there the target is far below the population so
- // the loop exits on reaching it; clamping to Integer.MAX_VALUE just avoids a
- // negative (overflowed) threshold that would itself cause truncation.
- long populationCeiling = (long) leafPageIds.size() * leafTupleCapacity;
- effectiveMaxLeafFindingAttempts = (int) Math.min(Integer.MAX_VALUE,
- Math.max(maxLeafFindingAttempts, POPULATION_ATTEMPT_MULTIPLIER * populationCeiling));
+ // Scale the give-up threshold to the sample TARGET, not the tuple-population ceiling:
+ //
+ // attempts cap = MULTIPLIER * max(leafPages, componentSampleCardinality)
+ //
+ // The caller caps the per-component target at the component's live-tuple estimate, so it never exceeds
+ // the reachable set; the loop must not give up before reaching it. Random draws with a growing
+ // already-seen set miss increasingly often as the reservoir fills, so the consecutive-miss streak
+ // needed for the last few tuples grows with the TARGET (a threshold equal to the target alone stops
+ // short, observed collected ~= threshold/3) - hence the multiplier. It must NOT scale with the raw
+ // tuple population (leafPages x maxLeafTupleCount ~= total tuples): a near-exhaustive / over-estimated
+ // component (target unreachable) would then grind ~MULTIPLIER x total-tuples attempts regardless of how
+ // small the target is. On this row cursor each attempt is a cheap slot lookup so that grind stays
+ // tolerable, but the column cursor pays a PK-decode per attempt and the same ~32 x total-tuples grind
+ // runs for minutes-to-hours (see ColumnBtreeSampleCursor); target-scaling fixes both. The leafPages
+ // floor lets a tiny target still probe every page. Clamp to int (a huge product would overflow
+ // negative and itself cause truncation).
+ long attemptCeiling = SAMPLE_ATTEMPT_MULTIPLIER * Math.max(leafPageIds.size(), componentSampleCardinality);
+ effectiveMaxLeafFindingAttempts =
+ (int) Math.min(Integer.MAX_VALUE, Math.max(maxLeafFindingAttempts, attemptCeiling));
if (LOGGER.isDebugEnabled()) {
- LOGGER.debug("DiskBTreeSampleCursor: {} leaf pages enumerated, target {} samples", leafPageIds.size(),
- componentSampleCardinality);
+ LOGGER.debug("DiskBTreeSampleCursor: {} leaf pages enumerated, target {} samples, attempts cap {}",
+ leafPageIds.size(), componentSampleCardinality, effectiveMaxLeafFindingAttempts);
}
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/btree/ColumnBtreeSampleCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/btree/ColumnBtreeSampleCursor.java
index a123882..86c9280 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/btree/ColumnBtreeSampleCursor.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/btree/ColumnBtreeSampleCursor.java
@@ -81,19 +81,15 @@
// u64: (pageId << 32) | tupleIndex
private final LongSet seenTupleIndexes;
- // Multiplier applied to the component tuple-population ceiling to derive the
- // effective consecutive-miss give-up threshold (see doOpen). Mirrors
- // DiskBTreeSampleCursor: the reservoir stalls well short of the target when the
- // threshold only equals the population, so a multiple well above that is needed.
- @AiProvenance(agent = AiProvenance.Agent.CLAUDE_OPUS_4_8, tool = AiProvenance.Tool.CLAUDE_CODE_UI, contributionKind = AiProvenance.ContributionKind.GENERATED, notes = "Population-scaled give-up threshold to stop near-exhaustive samples truncating at ~500 attempts")
- private static final long POPULATION_ATTEMPT_MULTIPLIER = 32L;
+ // Multiplier applied to the sample target (see doOpen) to derive the effective give-up threshold.
+ // Mirrors DiskBTreeSampleCursor: a fixed threshold stalls short of the target because random draws
+ // increasingly hit already-collected tuples near the end, so headroom must scale with the target.
+ private static final long SAMPLE_ATTEMPT_MULTIPLIER = 32L;
private final int maxLeafFindingAttempts;
- // Effective consecutive-miss give-up threshold, scaled to the component's tuple
- // population in doOpen(). A fixed maxLeafFindingAttempts silently truncates
- // near-exhaustive samples (target close to the component's live-tuple count) as
- // random draws increasingly hit already-collected pages/tuples; scaling to the
- // population keeps collection from stopping short while bounding the
- // genuinely-exhausted case to O(population) draws. Mirrors DiskBTreeSampleCursor.
+ // Effective give-up threshold, scaled to the sample target in doOpen(). A fixed maxLeafFindingAttempts
+ // silently truncates near-exhaustive samples (target close to the component's live-tuple count) as random
+ // draws increasingly hit already-collected tuples; scaling to the target keeps collection from stopping
+ // short while bounding the genuinely-exhausted case to O(target) draws. Mirrors DiskBTreeSampleCursor.
private int effectiveMaxLeafFindingAttempts;
private final int samplesPerPage;
// Max number of random probes per page (oversampled vs samplesPerPage to absorb
@@ -213,13 +209,26 @@
rootPageId = ((BTreeCursorInitialState) initialState).getPageId();
leafPageIds = bTree.enumerateLeafPageIds(rootPageId, opCtx, context);
- // Scale the give-up threshold to the component's tuple-population ceiling
- // (leaf pages x max tuples/leaf), clamped to int to avoid an overflowed
- // negative cap on huge components (where the target is far below the
- // population and the loop exits on reaching the target regardless).
- long populationCeiling = (long) leafPageIds.length * leafTupleCapacity;
- effectiveMaxLeafFindingAttempts = (int) Math.min(Integer.MAX_VALUE,
- Math.max(maxLeafFindingAttempts, POPULATION_ATTEMPT_MULTIPLIER * populationCeiling));
+ // Scale the give-up threshold to the sample TARGET, not the tuple-population ceiling.
+ //
+ // attempts cap = MULTIPLIER * max(leafPages, componentSampleCardinality)
+ //
+ // The loop collects componentSampleCardinality distinct live tuples; the caller already caps that
+ // target at the component's globally-live (shadowing-aware) count, so it never exceeds the reachable
+ // set. The coupon-collector tail for the last few tuples grows with the TARGET, so headroom must scale
+ // with the target. The old bound (MULTIPLIER * leafPages * maxLeafTupleCount) scaled with the raw tuple
+ // population instead: leafPages * maxLeafTupleCount ~= total tuples, so a near-exhaustive / over-
+ // estimated component (target unreachable) ground ~MULTIPLIER * total-tuples attempts before giving up,
+ // regardless of how small the target was. That attempt count is identical for row and column (both ~=
+ // 32 * total tuples); the reason it was invisible on row but catastrophic on column is the COST PER
+ // ATTEMPT, not the count: a column attempt re-inits the PK definition-level decoders and walks the PK
+ // column (collectFromPage), far heavier than a row slot lookup, so the same ~32 * total-tuples grind is
+ // milliseconds on row but minutes-to-hours on column. Target-scaling cuts the count to O(target) and
+ // fixes both. The leafPages floor lets a tiny target still probe every page. Clamp to int (a huge
+ // product would overflow negative).
+ long attemptCeiling = SAMPLE_ATTEMPT_MULTIPLIER * Math.max(leafPageIds.length, componentSampleCardinality);
+ effectiveMaxLeafFindingAttempts =
+ (int) Math.min(Integer.MAX_VALUE, Math.max(maxLeafFindingAttempts, attemptCeiling));
collectedSamples = new long[(int) componentSampleCardinality];
collectedCount = 0;
@@ -272,8 +281,13 @@
Arrays.sort(collectedSamples, 0, collectedCount);
if (LOGGER.isDebugEnabled()) {
- LOGGER.debug("ColumnBtreeSampleCursor Phase 1: collected {} samples from {} leaf pages", collectedCount,
- leafPageIds.length);
+ // endedPreemptively with attempts==cap flags a component that ground to the give-up threshold
+ // (near-exhaustive/over-estimated target). attempts far below cap means the target was reached.
+ LOGGER.debug(
+ "ColumnBtreeSampleCursor Phase 1: collected {}/{} samples from {} leaf pages, "
+ + "attempts {}/{}, endedPreemptively {}",
+ collectedCount, componentSampleCardinality, leafPageIds.length, hasNextAttemptCount,
+ effectiveMaxLeafFindingAttempts, endedPreemptively);
}
}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21499?usp=email
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email
Gerrit-MessageType: newchange
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I957d74dd87156d9545f52e05b9e2819566469c27
Gerrit-Change-Number: 21499
Gerrit-PatchSet: 1
Gerrit-Owner: Ritik Raj <ri...@couchbase.com>