As an alternative to WT-11815, keith.smith@mongodb.com suggested implementing an algorithm using the existing WT cursor API. Assuming we are generating a deterministic random sample of size K with seed S from a collection of size N:

• Generate K random numbers between 1 and N using seed S and sort them
• Open a WT cursor on the collection and iterate over records using the standard next() API, count the number of times we iterate. This iterates over the documents in "natural" order
• Every time we hit a number we generated, save that document

I prototyped this approach here and verified that when there are no writes present in the workload, we are able to generate deterministic samples. This ticket tracks the work to productionalize this work. This will help both CBR and join ordering optimization programs with testing and debugging customer issues.

This approach has very poor performance because it is effectively doing a full collection scan as part taking the sample. On my workstation, taking a 1k sample of the trade table in TPC-E c5000 (80M rows) takes ~1 minute. This was a non-starter in the world of on-the-fly sampling, but with persistent samples and for testing, this approach may be quite useful.

This approach is an improvement of the current implementation of strided sampling which performs a collection scan and returns every 1/k documents because it provides better statistical guarantees.