Support random cursor with data substrate

[liunyl]

Feature Summary
Support random cursor related interface for eloqdoc. This will be used by sampling.

Motivation

Proposed Solution

[coderabbitai]

📝 CodeRabbit Plan Mode

Generate an implementation plan and prompts that you can use with your favorite coding agent.

• Create Plan

Examples

• Example 1
• Example 2

---

🔗 Similar Issues

Related Issues

• Migrate eloqdoc to data_substrate #270
• Write design doc for new hash partition scan #98
• [Feature] Add metrics #317

👤 Suggested Assignees

• githubzilla
• liunyl
• lzxddz

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!

[liunyl]

Research on wired tiger implementation

---

date: 2025-12-25T03:20:39+00:00
researcher: Auto
git_commit: ecaa6bc
branch: main
repository: eloqdoc
topic: "How WiredTiger implements randomCursor and its next method - does it retrieve a new random value every time next is called, or does it just advance the previous random value to next key?"
tags: [research, codebase, wiredtiger, random-cursor, index]
status: complete
last_updated: 2025-12-25
last_updated_by: Auto
last_updated_note: "Added follow-up research for next_random_sample_size configuration, advance page count calculation, and MongoDB duplicate handling requirements"

Research: WiredTiger randomCursor next() Method Behavior

Date: 2025-12-25T03:20:39+00:00
Researcher: Auto
Git Commit: ecaa6bc
Branch: main
Repository: eloqdoc

Research Question

How does WiredTiger implement randomCursor and its next method? Does it retrieve a new random value every time next is called, or does it just advance the previous random value to the next key?

Summary

Answer: WiredTiger's next_random cursor retrieves a NEW pseudo-random value every time next() is called. It does not simply advance from a previous random position. Each call to next() performs a new random descent through the B-tree to select a random leaf page, then picks a random entry from that page.

WiredTiger's next_random option is implemented at the storage engine level and works by:

1. Replacing the cursor's next function pointer with __wt_curfile_next_random
2. On each next() call, performing a random descent through the B-tree structure
3. Selecting a random leaf page and then a random entry from that page

MongoDB's WiredTiger RecordStore implementation uses this feature via the next_random configuration string, but WiredTigerIndex does not currently implement newRandomCursor() (it returns an empty cursor by default).

Detailed Findings

WiredTiger next_random Implementation

The next_random option is a WiredTiger cursor configuration that enables pseudo-random record retrieval. When configured, it changes the cursor's behavior fundamentally:

Location: src/third_party/wiredtiger/src/cursor/cur_file.c:678-686

	WT_ERR(__wt_config_gets_def(session, cfg, "next_random", 0, &cval));
	if (cval.val != 0) {
		if (btree->type != BTREE_ROW)
			WT_ERR_MSG(session, ENOTSUP,
			    "next_random configuration not supported for "
			    "column-store objects");
		cursor->next = __wt_curfile_next_random;

When next_random=true is specified, the cursor's next function pointer is set to __wt_curfile_next_random, which calls __wt_btcur_next_random.

Core Implementation: src/third_party/wiredtiger/src/btree/bt_random.c:287-442

The key function __wt_btcur_next_random implements two algorithms:

1. Default behavior (no sampling): When next_random_sample_size == 0:
   • Performs a random descent through the B-tree on each call
   • Selects a random leaf page
   • Returns a random entry from that page

	if (cbt->ref == NULL || cbt->next_random_sample_size == 0) {
		WT_ERR(__cursor_func_init(cbt, true));
		WT_WITH_PAGE_INDEX(session,
		    ret = __wt_random_descent(session, &cbt->ref, read_flags));
		if (ret == 0)
			goto random_page_entry;

2. Sampling behavior: When next_random_sample_size > 0:
   • Divides the object into segments
   • Sequentially advances through leaf pages by a calculated skip value
   • Returns a random entry from the current leaf page

	for (skip = cbt->next_random_leaf_skip; cbt->ref == NULL || skip > 0;) {
		n = skip;
		WT_ERR(__wt_tree_walk_skip(session, &cbt->ref, &skip));
		if (n == skip) {
			if (skip == 0)
				break;
			--skip;
		}
	}

Random Descent Algorithm: src/third_party/wiredtiger/src/btree/bt_random.c:168-284

The __wt_random_descent function performs a random walk down the B-tree:

• Starts at the root page
• At each internal page, randomly selects a child page
• Continues until reaching a leaf page
• This ensures uniform distribution across the entire tree structure

	/* Search the internal pages of the tree. */
	current = &btree->root;
	for (;;) {
		page = current->page;
		if (!WT_PAGE_IS_INTERNAL(page))
			break;

		WT_INTL_INDEX_GET(session, page, pindex);
		entries = pindex->entries;

		/* Eviction just wants any random child. */
		if (eviction) {
			descent = pindex->index[
			    __wt_random(&session->rnd) % entries];
			goto descend;
		}

		/*
		 * There may be empty pages in the tree, and they're useless to
		 * us. If we don't find a non-empty page in "entries" random
		 * guesses, take the first non-empty page in the tree. If the
		 * search page contains nothing other than empty pages, restart
		 * from the root some number of times before giving up.
		 *
		 * Random sampling is looking for a key/value pair on a random
		 * leaf page, and so will accept any page that contains a valid
		 * key/value pair, so on-disk is fine, but deleted is not.
		 */
		descent = NULL;
		for (i = 0; i < entries; ++i) {
			descent =
			    pindex->index[__wt_random(&session->rnd) % entries];
			if (descent->state == WT_REF_DISK ||
			    descent->state == WT_REF_LIMBO ||
			    descent->state == WT_REF_LOOKASIDE ||
			    descent->state == WT_REF_MEM)
				break;
		}

Random Leaf Entry Selection: src/third_party/wiredtiger/src/btree/bt_random.c:15-165

Once a leaf page is selected, __wt_row_random_leaf picks a random entry from that page:

	/* If the page has disk-based entries, select from them. */
	if (page->entries != 0) {
		cbt->compare = 0;
		cbt->slot = __wt_random(&session->rnd) % page->entries;

		/*
		 * The real row-store search function builds the key, so we
		 * have to as well.
		 */
		return (__wt_row_leaf_key(session,
		    page, page->pg_row + cbt->slot, cbt->tmp, false));
	}

MongoDB's Usage of WiredTiger Random Cursors

RecordStore Implementation

MongoDB's WiredTiger RecordStore implements getRandomCursor() using WiredTiger's next_random feature:

Location: src/mongo/db/storage/wiredtiger/wiredtiger_record_store.cpp:477-548

class WiredTigerRecordStore::RandomCursor final : public RecordCursor {
public:
    RandomCursor(OperationContext* opCtx, const WiredTigerRecordStore& rs, StringData config)
        : _cursor(nullptr), _rs(&rs), _opCtx(opCtx), _config(config.toString() + ",next_random") {
        restore();
    }

    ~RandomCursor() {
        if (_cursor)
            detachFromOperationContext();
    }

    boost::optional<Record> next() final {
        int advanceRet =
            wiredTigerPrepareConflictRetry(_opCtx, [&] { return _cursor->next(_cursor); });
        if (advanceRet == WT_NOTFOUND)
            return {};
        invariantWTOK(advanceRet);

        int64_t key;
        invariantWTOK(_cursor->get_key(_cursor, &key));
        const RecordId id = RecordId(key);

        WT_ITEM value;
        invariantWTOK(_cursor->get_value(_cursor, &value));

        return {{id, {static_cast<const char*>(value.data), static_cast<int>(value.size)}}};
    }

The key observation is that the next() method simply calls _cursor->next(_cursor), which invokes WiredTiger's __wt_curfile_next_random function (due to the next_random configuration). Each call performs a new random descent.

Index Implementation

WiredTigerIndex does not implement newRandomCursor(). The base class SortedDataInterface provides a default implementation that returns an empty cursor:

Location: src/mongo/db/storage/sorted_data_interface.h:390-392

    virtual std::unique_ptr<Cursor> newRandomCursor(OperationContext* opCtx) const {
        return {};
    }

Location: src/mongo/db/index/index_access_method.cpp:205-208

std::unique_ptr<SortedDataInterface::Cursor> IndexAccessMethod::newRandomCursor(
    OperationContext* opCtx) const {
    return _newInterface->newRandomCursor(opCtx);
}

Since WiredTigerIndex doesn't override this method, it returns an empty cursor, meaning random cursor functionality is not available for indexes in the current implementation.

WiredTiger Documentation

According to WiredTiger's official documentation (src/third_party/wiredtiger/src/docs/cursor-random.dox):

"By default, each returned record is pseudo-randomly selected from the underlying object as a whole."

This confirms that each next() call performs a new random selection, not a sequential advance from a previous position.

Code References

• src/third_party/wiredtiger/src/cursor/cur_file.c:108-127 - Entry point for next_random cursor operations
• src/third_party/wiredtiger/src/btree/bt_random.c:287-442 - Core __wt_btcur_next_random implementation
• src/third_party/wiredtiger/src/btree/bt_random.c:168-284 - Random descent algorithm
• src/third_party/wiredtiger/src/btree/bt_random.c:15-165 - Random leaf entry selection
• src/mongo/db/storage/wiredtiger/wiredtiger_record_store.cpp:477-548 - MongoDB RecordStore RandomCursor wrapper
• src/mongo/db/storage/sorted_data_interface.h:390-392 - Default empty random cursor implementation
• src/mongo/db/index/index_access_method.cpp:205-208 - IndexAccessMethod delegation

Architecture Documentation

How next_random Works

1. Configuration: When opening a cursor with next_random=true, WiredTiger sets the cursor's next function pointer to __wt_curfile_next_random.

2. Each next() Call:

   • If next_random_sample_size == 0 (default): Performs a complete random descent from root to a random leaf page, then selects a random entry from that page.
   • If next_random_sample_size > 0: Uses a sampling approach that divides the object into segments and sequentially samples from each segment.

3. Random Descent Process:

   • Starts at the root page
   • At each internal page, randomly selects a child page
   • Continues until reaching a leaf page
   • Selects a random entry from the leaf page

4. No State Between Calls: Each next() call is independent. The cursor does not maintain a "current random position" that it advances from. Instead, it performs a fresh random selection each time.

MongoDB Integration

• RecordStore: Fully implements random cursors using WiredTiger's next_random feature
• Index (SortedDataInterface): Does not implement random cursors - returns empty cursor by default
• The MongoDB layer simply wraps WiredTiger's cursor and calls next(), relying on WiredTiger's implementation for the random behavior

Historical Context (from thoughts/)

No relevant historical context found in the thoughts directory for this topic.

Related Research

No related research documents found in .cursor/thoughts/shared/research/.

Follow-up Research [2025-12-25T03:30:39+00:00]: next_random_sample_size and Duplicate Handling

When is next_random_sample_size Set?

In WiredTiger: The next_random_sample_size is set when opening a cursor with the configuration string:

Location: src/third_party/wiredtiger/src/cursor/cur_file.c:689-692

		WT_ERR(__wt_config_gets_def(
		    session, cfg, "next_random_sample_size", 0, &cval));
		if (cval.val != 0)
			cbt->next_random_sample_size = (u_int)cval.val;

In MongoDB: MongoDB sets next_random_sample_size when creating random cursors for specific use cases. The primary example is in the oplog stones calculation:

Location: src/mongo/db/storage/wiredtiger/wiredtiger_record_store.cpp:401-403

    // Inform the random cursor of the number of samples we intend to take. This allows it to
    // account for skew in the tree shape.
    const std::string extraConfig = str::stream() << "next_random_sample_size=" << numSamples;

The numSamples value is calculated based on the number of records and estimated records per stone:

    int64_t wholeStones = _rs->numRecords(opCtx) / estRecordsPerStone;
    int64_t numSamples = kRandomSamplesPerStone * _rs->numRecords(opCtx) / estRecordsPerStone;

Default Behavior: If next_random_sample_size is not explicitly set (or set to 0), WiredTiger defaults to 100 when using the sampling algorithm:

Location: src/third_party/wiredtiger/src/btree/bt_random.c:365-366

	if (cbt->next_random_sample_size == 0)
		cbt->next_random_sample_size = 100;

How Does It Calculate the Advance Page Count?

When next_random_sample_size > 0, WiredTiger uses a sampling approach that advances through leaf pages sequentially rather than performing a full random descent each time. The number of pages to skip between samples is calculated as follows:

Location: src/third_party/wiredtiger/src/btree/bt_random.c:383-388

	if (cbt->next_random_leaf_skip == 0) {
		WT_ERR(btree->bm->size(btree->bm, session, &size));
		cbt->next_random_leaf_skip = (uint64_t)
		    ((size / btree->allocsize) /
		    cbt->next_random_sample_size) + 1;
	}

Calculation Formula:

next_random_leaf_skip = (file_size / allocation_size) / next_random_sample_size + 1

Explanation:

1. Estimate leaf pages: file_size / allocation_size provides an estimate of the number of leaf pages in the file
2. Divide by sample size: This divides the estimated leaf pages by the number of samples to determine how many pages should be in each segment
3. Add 1: Ensures tiny files don't result in a skip value of 0

Important Notes:

• This is an estimate - the comment in the code acknowledges: "this can be entirely wrong, as it depends on how many pages are in this particular checkpoint, how large the leaf and internal pages really are, and other factors"
• The code comment suggests "Ideally, the number would be prime to avoid restart issues"
• The sampling approach is designed to compensate for unbalanced trees by ensuring more uniform distribution across the object

Usage: Once calculated, the skip value is used to advance through leaf pages:

	for (skip = cbt->next_random_leaf_skip; cbt->ref == NULL || skip > 0;) {
		n = skip;
		WT_ERR(__wt_tree_walk_skip(session, &cbt->ref, &skip));
		if (n == skip) {
			if (skip == 0)
				break;
			--skip;
		}
	}

Does MongoDB Require Non-Duplicate Values?

Answer: Yes, MongoDB explicitly filters out duplicates, even though WiredTiger's random cursor is allowed to return duplicates.

MongoDB's Duplicate Handling: MongoDB's DocumentSourceSampleFromRandomCursor stage explicitly handles duplicates:

Location: src/mongo/db/pipeline/document_source_sample_from_random_cursor.h:80-81

    // Keeps track of the documents that have been returned, since a random cursor is allowed to
    // return duplicates.
    ValueUnorderedSet _seenDocs;

Implementation: The getNextNonDuplicateDocument() method keeps retrying until it gets a non-duplicate:

Location: src/mongo/db/pipeline/document_source_sample_from_random_cursor.cpp:103-144

DocumentSource::GetNextResult DocumentSourceSampleFromRandomCursor::getNextNonDuplicateDocument() {
    // We may get duplicate documents back from the random cursor, and should not return duplicate
    // documents, so keep trying until we get a new one.
    const int kMaxAttempts = 100;
    for (int i = 0; i < kMaxAttempts; ++i) {
        auto nextInput = pSource->getNext();
        switch (nextInput.getStatus()) {
            case GetNextResult::ReturnStatus::kAdvanced: {
                auto idField = nextInput.getDocument()[_idField];
                uassert(28793,
                        str::stream()
                            << "The optimized $sample stage requires all documents have a "
                            << _idField
                            << " field in order to de-duplicate results, but encountered a "
                               "document without a "
                            << _idField
                            << " field: "
                            << nextInput.getDocument().toString(),
                        !idField.missing());

                if (_seenDocs.insert(std::move(idField)).second) {
                    return nextInput;
                }
                LOG(1) << "$sample encountered duplicate document: "
                       << nextInput.getDocument().toString();
                break;  // Try again with the next document.
            }

Key Points:

1. MongoDB expects duplicates: The code explicitly acknowledges that "a random cursor is allowed to return duplicates"
2. Deduplication is required: MongoDB uses a ValueUnorderedSet _seenDocs to track seen document IDs and filters out duplicates
3. ID field requirement: All documents must have an _id field (or ts for oplog) for deduplication to work
4. Retry limit: The code will retry up to 100 times to find a non-duplicate document before erroring
5. Error handling: If 100 consecutive duplicates are encountered, MongoDB throws an error: "could not find a non-duplicate document after 100 attempts"

Why This Matters: This design allows WiredTiger to return duplicates (which is more efficient for the storage engine), while MongoDB's application layer ensures the final result set contains no duplicates. This separation of concerns is efficient because:

• WiredTiger doesn't need to maintain state about previously returned values
• MongoDB can handle deduplication at a higher level where it has more context (document IDs)
• The retry mechanism handles the rare case of many consecutive duplicates

Open Questions

None - the research question and follow-up questions have been fully answered.