3 ms·

I didn't find the solutions to be all that helpful; it was essentially "pipeline your processing." If all I'm doing is a programmatic "cat | grep | cut", that's

I didn't find the solutions to be all that helpful; it was essentially "pipeline your processing." If all I'm doing is a programmatic "cat | grep | cut", that's fine. It gets messy when I want to sort the data or join it with another medium-large dataset, and this is why people load into memory in the first place. Is there a sane path where I'm not immediately jumping to Hadoop or Presto? Maybe I can offload the join to SQLite?

civilized 5y ago
Yes! If your data is too big to comfortably manipulate in memory with R/Python/your language of choice, and the data is (or can be made to be) tabular, the next best place for it is a relational database. If you don't have an existing server that's well-suited, use SQLite or DuckDB, the "SQLite of analytics". Definitely use a columnar database if you're going to be doing complex queries and joins. This is battle-worn experience and I will absolutely die on this hill. Relational databases JUST WORK. The only exception is when you need to do complex ML on big data, in which case, take your pick from Apache Spark, Dask, or some similar framework. Hopefully these will be increasingly supplemented by in-database ML going forward, so that there is no reason to ever leave the database.
dredmorbius 5y ago
The best thing to do when it comes to sorting data is to not do that. Sorts frequently are used in merges or to find some top-n / bottom-n instance rate. If you've got to sort (or writing an alternative is too time-consuming), do it after eliminating as much data (variables, records) as possible. Hash tables (or other comparable tools such as btrees or Bloom filters) can be used for dataset comparisons or key-value lookups. Arrays can be used to keep a runnning count of top-n records (this may need to be sorted on insert, though comparing largest/smallest entry can mitigate this). Random sampling is very often as good as complete processing, especially where the goal is to find the general characteristics of a dataset rather than an exhaustive view or precise tabulation. Even in accounting and financial operations, sampling methods may be acceptable (see for example, mechanical copyright royalties on performance of recorded music broadcasts, or advertising and circulation rates in publishing). It's fairly staggering how clearly a small sample (as few as 30 records, often only a few hundred or thousand) can describe an immense dataset (millions or billions of entries) with reasonable accuracy, so long as it is randomly selected. And if the first sample seems off, try pulling a few others and seeing how they compare. (Effectively: Monte Carlo method.) The place where sampling methods break down most is in iterative-calculation forecasts (e.g., weather modeling), where larger aggregations (typically measured as datapoints over both area and time) greatly reduce accuracy. Though even with very precise reporting density, today's weather forecasts tend to be limited to 7--10 days. Sometimes randomness simply wins.
- kragen 5y ago
  > Arrays can be used to keep a runnning count of top-n records (this may need to be sorted on insert, though comparing largest/smallest entry can mitigate this). Honored and wise Morbius, I humbly beg to differ; top-N record arrays never need to be sorted on insert, because a binary heap is 25 lines of code. Then all you need for top-N is: for record in input_file: if record <= aMinheap.minimum: continue aMinheap.extract_minimum() aMinheap.add(record) I think that, to produce the top 100, this takes about 8 comparisons per record added to the candidate set, rather than the 1000 or so required by your suggested method. The difference won't matter for a big enough unordered dataset, though, since almost all the time will be taken by discarding records in the initial comparison. I was thinking quickselect was even faster when your data does fit in RAM, but I can't see how that could be true, even though it's linear time: if you have a million records, then the first partitioning step of quickselect will examine all of them (doing one comparison for each), the second partitioning step will examine on average half of them, and the third partitioning step will examine on average somewhat more than a quarter of them (because the expected size for the result of the second partitioning step is more than 250,000 records), and so we end up doing something like e comparisons per record on average rather than 1. But, with the running-candidate-set approach you suggested, if the million records are in random order, after we're past the first 1000 records, we do only a single comparison for at least 90% of the remaining records (because they're less than the top 100 from the first 1000), and after we're past the first 10,000 records, for at least 99%. So if we did 8000 comparisons in the first 1000, then inserted 900 of the next 9000 records for another 7200 comparisons (plus 9000 comparisons to reject the other 8100), and then another 900 of the next 90,000 records (plus 90,000 initial comparisons), we're at 121,400 comparisons for the first 100,000 records, 1.214 comparisons per record. So, for a small top-N query, quickselect loses the race before it's finished with its second partitioning step. Or am I overlooking something?
  - dredmorbius 5y ago
    I'd hand-coded a "top-n" utility in awk some time back. I think my first iteration used bubble sort. That was still faster than a sort | head script, by a lot. (I think I later improved on that, possibly by retaining min/max records.) Even in awk, and even when choosing large values for n (e.g., thousand or tens of thousands of records), this easily beat the sort utility in cpu time, wall-clock time, and memory usage, for many millions of input records. (Most of my coding tends to be hackish and brutish. Algorithms are not my strong suit.)

civilized 5y ago

Yes! If your data is too big to comfortably manipulate in memory with R/Python/your language of choice, and the data is (or can be made to be) tabular, the next best place for it is a relational database. If you don't have an existing server that's well-suited, use SQLite or DuckDB, the "SQLite of analytics". Definitely use a columnar database if you're going to be doing complex queries and joins. This is battle-worn experience and I will absolutely die on this hill. Relational databases JUST WORK. The only exception is when you need to do complex ML on big data, in which case, take your pick from Apache Spark, Dask, or some similar framework. Hopefully these will be increasingly supplemented by in-database ML going forward, so that there is no reason to ever leave the database.

dredmorbius 5y ago

The best thing to do when it comes to sorting data is to not do that. Sorts frequently are used in merges or to find some top-n / bottom-n instance rate. If you've got to sort (or writing an alternative is too time-consuming), do it after eliminating as much data (variables, records) as possible. Hash tables (or other comparable tools such as btrees or Bloom filters) can be used for dataset comparisons or key-value lookups. Arrays can be used to keep a runnning count of top-n records (this may need to be sorted on insert, though comparing largest/smallest entry can mitigate this). Random sampling is very often as good as complete processing, especially where the goal is to find the general characteristics of a dataset rather than an exhaustive view or precise tabulation. Even in accounting and financial operations, sampling methods may be acceptable (see for example, mechanical copyright royalties on performance of recorded music broadcasts, or advertising and circulation rates in publishing). It's fairly staggering how clearly a small sample (as few as 30 records, often only a few hundred or thousand) can describe an immense dataset (millions or billions of entries) with reasonable accuracy, so long as it is randomly selected. And if the first sample seems off, try pulling a few others and seeing how they compare. (Effectively: Monte Carlo method.) The place where sampling methods break down most is in iterative-calculation forecasts (e.g., weather modeling), where larger aggregations (typically measured as datapoints over both area and time) greatly reduce accuracy. Though even with very precise reporting density, today's weather forecasts tend to be limited to 7--10 days. Sometimes randomness simply wins.

kragen 5y ago
> Arrays can be used to keep a runnning count of top-n records (this may need to be sorted on insert, though comparing largest/smallest entry can mitigate this). Honored and wise Morbius, I humbly beg to differ; top-N record arrays never need to be sorted on insert, because a binary heap is 25 lines of code. Then all you need for top-N is: for record in input_file: if record <= aMinheap.minimum: continue aMinheap.extract_minimum() aMinheap.add(record) I think that, to produce the top 100, this takes about 8 comparisons per record added to the candidate set, rather than the 1000 or so required by your suggested method. The difference won't matter for a big enough unordered dataset, though, since almost all the time will be taken by discarding records in the initial comparison. I was thinking quickselect was even faster when your data does fit in RAM, but I can't see how that could be true, even though it's linear time: if you have a million records, then the first partitioning step of quickselect will examine all of them (doing one comparison for each), the second partitioning step will examine on average half of them, and the third partitioning step will examine on average somewhat more than a quarter of them (because the expected size for the result of the second partitioning step is more than 250,000 records), and so we end up doing something like e comparisons per record on average rather than 1. But, with the running-candidate-set approach you suggested, if the million records are in random order, after we're past the first 1000 records, we do only a single comparison for at least 90% of the remaining records (because they're less than the top 100 from the first 1000), and after we're past the first 10,000 records, for at least 99%. So if we did 8000 comparisons in the first 1000, then inserted 900 of the next 9000 records for another 7200 comparisons (plus 9000 comparisons to reject the other 8100), and then another 900 of the next 90,000 records (plus 90,000 initial comparisons), we're at 121,400 comparisons for the first 100,000 records, 1.214 comparisons per record. So, for a small top-N query, quickselect loses the race before it's finished with its second partitioning step. Or am I overlooking something?
- dredmorbius 5y ago
  I'd hand-coded a "top-n" utility in awk some time back. I think my first iteration used bubble sort. That was still faster than a sort | head script, by a lot. (I think I later improved on that, possibly by retaining min/max records.) Even in awk, and even when choosing large values for n (e.g., thousand or tens of thousands of records), this easily beat the sort utility in cpu time, wall-clock time, and memory usage, for many millions of input records. (Most of my coding tends to be hackish and brutish. Algorithms are not my strong suit.)