Histogram collection has been augmented in 10.4 with the ability to collect a percentage of rows. This was implemented via Bernoulli sampling. The drawback is that one has to perform a full table scan to perform sampling. This technique has reduced the bottleneck of Histograms collection substantially, however it can still be improved.

Storage engine API should be extended to allow the server to make use (if available) storage engine sampling capabilities.

This feature can be additionally used to support fast approximation functions such as a version of fast count-distinct with an estimator attached. (ex: Smoothed Jackknife Estimator) Additionally, with native sampling support, one could afford to perform various optimizations in the background (such as statistics collection), as the performance impact would be much smaller. Another use case for native sampling is SELECT FROM <table-sample>

https://www.2ndquadrant.com/en/blog/tablesample-in-postgresql-9-5-2/

The implementation will be done for 2 different storage engines (Aria & Innodb). The algorithm will make use of a weighted index-dive (to counteract if index pages are unbalanced).