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>