Efficient Random Sampling from Very Large Databases

One of the major research questions in large databases is how to efficiently sample a random subset of records. This sample can then be used to estimate query results and optimize query execution plans and other tasks. In order to have quick access to the data, the common practice is to create an index, which is often implemented by using B+Trees. Existing state-of-the-art algorithms for random sampling over B+Trees result in a significant performance overhead. This paper proposes novel approaches for efficient random sampling over B+Trees in very large databases. We analyze the algorithms’ correctness and use extensive simulation study, which showcases their superior performance compared to previous works while not affecting the quality of the random sample.