4 ms·
Sampling with SQL
- tmoertel 2y agoHey! I'm tickled to see this on HN. I'm the author. If you have any questions, just ask. I'll do my best to answer them here.
- indoordin0saur 2y agoThank you! The thing I find tricky here is choosing the weight. I think maybe one obvious way you would want to weight samples would be for recency. E.g. if I have a table of user login events then I care about seeing more of the ones that happened recently but still want to see some of the older ones. Would the algorithm still work if I converted a `created_at` timestamp to epoch time and used that? Or would I want to normalize it in some way?
- swasheck 2y agodepending on what you’re analyzing, EMA could give you a good weighting method
- tmoertel 2y agoAll of your `created_at` epoch times are going to be of similar magnitude, since they’re all about the same relative distance from the start of the epoch (usually 1970-01-01T00:00:00). So if you use them as weights directly, you’re in effect taking a uniform sample – every row has about the same chance of being chosen. Based on what I glean about your scenario, I suspect you’d be better served by some kind of exponentially decaying weight based on age (i.e., age = current_timestamp ‒ created_at). For example, if you wanted to make your rows half as likely to be selected every time they grew another hour older, you could use `POW(2.0, -age / 3600)` as your weight, where age is given in seconds. duckdb> WITH Ages AS ( SELECT age FROM UNNEST([0, 3600, 7200]) AS t(age) ) SELECT age, POW(2.0, -age / 3600) AS w FROM Ages; ┌──────┬──────┐ │ age ┆ w │ ╞══════╪══════╡ │ 0 ┆ 1.0 │ │ 3600 ┆ 0.5 │ │ 7200 ┆ 0.25 │ └──────┴──────┘
- swasheck 2y agothis is a really fascinating and interesting to me. i’ve been using sql to analyze large data sets recently since sql is my primary skillset and having new methods and algorithms is quite handy and interesting. i do have a question of clarification. this is built on weighted sampling with weights in the dataset. does this indicate some sort of preprocessing to arrive at the weights?
- tmoertel 2y agoThe weights just indicate how important each row is to whatever you’re trying to estimate. Sometimes, your datasets will have numeric columns that naturally suggest themselves as weights. Other times, you may have to create weights. For example, say you run a website like Wikipedia and want to estimate the percentage of page views that go to pages that are dangerously misleading. You have a dataset that contains all of your site’s pages, and you have logs that indicate which pages users have viewed. What you don’t have is a flag for each page that indicates whether it’s “dangerously misleading”; you’ll have to create it. And that’s likely to require a panel of expert human reviewers. Since it’s not practical to have your experts review every single page, you’ll want to review only a sample of pages. And since each page spreads misleading information only to the degree it’s viewed by users, you’ll want to weight each page by its view count. To get those counts, you’ll have to process the site logs, and count how many times each page was viewed. Then you can take a sample of pages weighted by those counts. That’s a pretty typical scenario. You think about the question you’re trying to answer. You think about the data you have and the data you’ll need. Then you figure out how to get the data you need, hopefully without too much trouble.
- swasheck 2y agoso that’s a “yes, in many cases it requires preprocessing which would occur prior to the scope of this article.” thank you!
- emmelaich 2y agoIs there something in the SQL standard that says functions are guaranteed to executed more than once? I swear that once I used something like random() and it was only executed once, making it useless for the task at hand. I had to use some trick to ensure it was executed for each row. I may have used it in the `select` part. Dialect was Oracle's, from memory. related: https://xkcd.com/221/ https://xkcd.com/221/
- hobs 2y agoIt depends on the function and the SQL implementation, you can see in this simulator that where rand() > rand() evaluates row by row in MySQL but once in SQL Server, so its easy to get this stuff messed up even if the code is "equivalent" its really not. https://onecompiler.com/mysql/42vq8s23b https://onecompiler.com/mysql/42vq8s23b https://onecompiler.com/sqlserver/42vq8tz24 https://onecompiler.com/sqlserver/42vq8tz24
- emmelaich 2y agoThanks, that's a bit upsetting :-)
- tmoertel 2y agoIndeed. On systems with unfortunate evaluation semantics for `RAND`, you can generate fresh random values for each row by creating a function for that purpose and calling it on the primary key of each row. I provide one example in the article at: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html#adding-determinism https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.... I'll include a copy here because it's short. It's for DuckDB and was created to let us generate a controllable number of fresh random values for each row: -- Returns a pseudorandom fp64 number in the range [0, 1). The number -- is determined by the given `key`, `seed` string, and integer `index`. CREATE MACRO pseudorandom_uniform(key, seed, index) AS ( (HASH(key || seed || index) >> 11) * POW(2.0, -53) );
- o11c 2y ago
- natmaka 2y agoIf you need to "extract a small, sample dataset from a larger PostgreSQL database while maintaining referential integrity" check https://github.com/mla/pg_sample https://github.com/mla/pg_sample
- rhymer 2y agoBe careful, the weight of Algorithm A by Efraimidis and Spirakis cannot be interpreted as the inclusion probability, and thus cannot be used in survey sampling to construct the Horvitz–Thompson estimator. See "Remarks on some misconceptions about unequal probability sampling without replacement" by Yves Tillé. Quoted from Tillé's conclusion: "There is a multitude of correct and fast method of sampling... there is no reason to use an incorrect method like weighted random sampling where we do not control the inclusion probabilities" It's not clear to me how easy it is to implement the "multitude of corect and fast methods" in SQL, though. Would love to see some reference implementation.
- apwheele 2y agoCare to elaborate on this? So this post does not save the resulting weight, so you don't use that in any subsequent calculations. You would just treat the result as a simple random sample. So it is unclear why this critique matters.
- tmoertel 2y agoYes, rhymer has hit on the primary tradeoff behind Algorithm A. While Algorithm A is fast, easy, and makes it possible to sample any dataset you can access with SQL, including massive distributed datasets, its draws from the population are not independent and identically distributed (because with each draw you make the population one item smaller), nor does it let you compute the inclusion probabilties that would let you use the most common reweighting methods, such as a Horvitz–Thompson estimator, to produce unbiased estimates from potentially biased samples. In practice, however, when your samples are small, your populations are large, and your populations' weights are not concentrated in a small number of members, you can use Algorithm A and just pretend that you have a sample of i.i.d. draws. In these circumstances, the potential for bias is generally not worth worrying about. But when you cannot play so fast and loose, you can produce unbiased estimates from an Algorithm A sample by using an ordered estimator, such as Des Raj's ordered estimator [1]. You could alternatively use a different sampling method, one that does produce inclusion probabilities. But these tend to be implemented only in more sophisticated statistical systems (e.g., R's "survey" package [2]) and thus not useful unless you can fit your dataset into those systems. For very large datasets, then, I end up using Algorithm A to take samples and (when it matters) Des Raj's ordered estimator to make estimates. (I was planning a follow up post to my blog on this subject.) [1] The original papers are hard to come by online, so I suggest starting with an introduction like https://home.iitk.ac.in/~shalab/sampling/chapter7-sampling-varying-probability-sampling.pdf https://home.iitk.ac.in/~shalab/sampling/chapter7-sampling-v..., starting at page 11. [2] https://cran.r-project.org/web/packages/survey/survey.pdf https://cran.r-project.org/web/packages/survey/survey.pdf
- apwheele 2y agoVery nice, another pro-tip for folks is that you can set the weights to get approximate stratified sampling. So say group A had 100,000 rows, and group B had 10,000 rows, and you wanted each in the resulting to have approximately the same proportion. You would set the weight for each A row to be 1/100,000 and for B to be 1/10,000. If you want exact counts I think you would need to do RANK and PARTITION BY.
- Horffupolde 2y agoORDERing by RANDOM on a large table requires a full scan, even with LIMIT. For tables that don’t fit in memory this is impractical and I/O shoots to 100%.
- tmoertel 2y agoActually, on most modern SQL systems, especially those that deal with large datasets, the `ORDER/LIMIT` combination is implemented as a `TOP N` operation that consumes only O(N) memory.
- swasheck 2y agoi don’t think the workspace memory is op point. if the initial set (not the intermediate or final projection) is too large, reads will come from disk which also creates cpu churn. at least in mssql, if the data page is not in memory it is read into the buffer pool and then read from the buffer bool into the workspace for processing. if there isn’t enough buffer space to fit all of the data set pages in the pool, you’re going to be reading and flushing pages. i think pg operates similarly.
- tmoertel 2y agoYes, to sample a population, you must consider every row in the population. There's no way around it. But it doesn't have to be as slow and expensive as reading the entire population table. To determine which rows are in the sample, you need to consider only two columns: the weight and (a) primary key. If your population lives in a traditional row-oriented store, then you're going to have to read every row. But if you index your weights, you only need to scan the index, not the underlying population table to identify the sample. If your population lives in a column-oriented store, identifying the sample is fast, again because you only need to read two small columns to do it. Column stores are optimized for this case.
- crazygringo 2y agoBut only when operating on fields that are indexed. If you pull the highest 5 product ID's sorting by product ID, you're right it only reads those 5 entries from disk. But when you ORDER BY RANDOM(), it's forced to do a full-table scan, because RANDOM() can't be indexed.
- nzach 2y agoIs the idea of doing statistics directly in the database a relatively new development? This seems like such a great idea, but this is just the first time I read about this. This is a great article, thanks for sharing.
- bastawhiz 2y ago> ORDER BY -LN(1.0 - RANDOM()) / weight Isn't this the same as just > ORDER BY -LN(RANDOM()) / weight
- tmoertel 2y agoYes, except that it avoids the possibility of a floating-point error. In most SQL implementations, `RANDOM()` can return zero, but the log of 0 is undefined. From the article: > One last numerical subtlety. Why do we generate random numbers with the expression `1.0 - RANDOM()` instead of just `RANDOM()`? Since most implementations of RANDOM(), such as the PCG implementation used by DuckDB, return a floating-point value in the semi-closed range [0, 1), they can theoretically return zero. And we don’t want to take the logarithm of zero. So we instead use `1.0 - RANDOM()` to generate a random number in the semi-closed range (0, 1], which excludes zero.
- bastawhiz 2y agoGot it, I'd missed that. Thank you
- indoordin0saur 2y agoFor the newbies: quick way I'll get a sample of rows (without weights) in Redshift: `SELECT * FROM sales ORDER BY RANDOM() LIMIT 10;`
- peterm4 2y agoBeen working with sqlite and Typescript, needing random rows sampled reproducibly with a seed. Found this handy little trick [0]. Not the cleanest, but it works! `SELECT * FROM sales ORDER BY substr(${seedValue} * sales.id, length(sales.id) + 2) LIMIT 10;` [0] https://stackoverflow.com/questions/24256258/order-by-random-with-seed-in-sqlite https://stackoverflow.com/questions/24256258/order-by-random...
- oli5679 2y agoOne thing that can be useful with sampling is sampling a consistent but growing sub population. This can help maintain a consistent holdout for machine learning models, help you sample analytical data and test joins without null issues etc. If you use a deterministic hash, like farm_fingerprint on your id column (e. g user_id) and keep if modulus N = 0, you will keep the same growing list of users across runs and queries to different tables.