4 ms·

My first instinct would be to spin up a local Postgres and keep station data there. A lot of the solutions assume we have enough ram to keep the stats per stati

My first instinct would be to spin up a local Postgres and keep station data there. A lot of the solutions assume we have enough ram to keep the stats per station, however that's a bad assumption when dealing with a lot of data.

masklinn 3y ago
This is not a general solution, it’s a specific problem with a specific data shape, and processes specifically 1 billion rows on a 32GB machine.
- pletnes 3y ago
  And this is why file io is not the bottleneck - all the data is in RAM/disk cache.
Alifatisk 3y ago
> A lot of the solutions assume we have enough ram to keep the stats per station I’ll give this example in Ruby but you’ll get the point, what you are mentioning is an issue if you chose to use File.read(), because it opens the file and reads its content into the ram. But this can be solved if you use File.readlines() because it streams each row instead which uses much less ram.
- afiodorov 3y ago
  What I am saying is that the solutions presented assume we have N stations which are way less than 1_000_000_000. Worst case scenario for RAM would be if each line contained a unique station. In this case we'd have to allocate 1_000_000_000 * sizeof(stats) in RAM to contain the result of the computation. So most of the solutions assume sufficient RAM ahead of reading the file. In the first solution: type stats struct { min, max, sum float64 count int64 } would take up 32GB for the stats alone for all 1E9 stations, and that's ignoring space needed for each station's name!
  - blackoil 3y ago
    You are optimizing for a hypothetical edge case. If there are few hundred thousand weather stations in world or 50,000 airports or 2 million hotels. Building system assuming they'll change to billions is impractical. Also, even for this, original problem statement sets maximum to 10,000 different station names.
    - afiodorov 3y ago
      I thought this was an illustrative example of how to process big datasets. We could easily have a statistic per e.g. bitcoin transaction in a different problem, see https://github.com/afiodorov/bitcoin_ancestries https://github.com/afiodorov/bitcoin_ancestries . I struggle a lot with this toy problem. Without constraints too trivial to pay attention to; then no one seems to agree on potential real-world constraints (stdlib only? no mmaps?). If we have to solve just this problem as is, shouldn't we be timing simple solutions using various frameworks (polars, pandas, spark, bigquery[^1], go, awk) to compare various frameworks? Once you have the answer, why would you try to get the same answer again but in 4 seconds the second time round? Comparing frameworks would at least indicate if a data practitioner should upskill and pick up yet another data framework. [^1]: https://medium.com/@shuvro_25220/the-one-billion-rows-challenge-with-bigquery-404538c5e3e6 https://medium.com/@shuvro_25220/the-one-billion-rows-challe...

masklinn 3y ago

This is not a general solution, it’s a specific problem with a specific data shape, and processes specifically 1 billion rows on a 32GB machine.

pletnes 3y ago
And this is why file io is not the bottleneck - all the data is in RAM/disk cache.

Alifatisk 3y ago

> A lot of the solutions assume we have enough ram to keep the stats per station I’ll give this example in Ruby but you’ll get the point, what you are mentioning is an issue if you chose to use File.read(), because it opens the file and reads its content into the ram. But this can be solved if you use File.readlines() because it streams each row instead which uses much less ram.

afiodorov 3y ago
What I am saying is that the solutions presented assume we have N stations which are way less than 1_000_000_000. Worst case scenario for RAM would be if each line contained a unique station. In this case we'd have to allocate 1_000_000_000 * sizeof(stats) in RAM to contain the result of the computation. So most of the solutions assume sufficient RAM ahead of reading the file. In the first solution: type stats struct { min, max, sum float64 count int64 } would take up 32GB for the stats alone for all 1E9 stations, and that's ignoring space needed for each station's name!
- blackoil 3y ago
  You are optimizing for a hypothetical edge case. If there are few hundred thousand weather stations in world or 50,000 airports or 2 million hotels. Building system assuming they'll change to billions is impractical. Also, even for this, original problem statement sets maximum to 10,000 different station names.
  - afiodorov 3y ago
    I thought this was an illustrative example of how to process big datasets. We could easily have a statistic per e.g. bitcoin transaction in a different problem, see https://github.com/afiodorov/bitcoin_ancestries https://github.com/afiodorov/bitcoin_ancestries . I struggle a lot with this toy problem. Without constraints too trivial to pay attention to; then no one seems to agree on potential real-world constraints (stdlib only? no mmaps?). If we have to solve just this problem as is, shouldn't we be timing simple solutions using various frameworks (polars, pandas, spark, bigquery[^1], go, awk) to compare various frameworks? Once you have the answer, why would you try to get the same answer again but in 4 seconds the second time round? Comparing frameworks would at least indicate if a data practitioner should upskill and pick up yet another data framework. [^1]: https://medium.com/@shuvro_25220/the-one-billion-rows-challenge-with-bigquery-404538c5e3e6 https://medium.com/@shuvro_25220/the-one-billion-rows-challe...