On Sampling and Relational Operators.
Surajit Chaudhuri, Rajeev Motwani · 1999
A major bottleneck in implementing sampling as a primitive relational operation is the inefficiency of sampling the output of a query. We highlight the primary difficulties, summarize the results of some recent work in this area, and indicate directions for future work.