Earlier quoted context omitted.
1:05 in PostgreSQL 16 but it was harder than I thought to saturate the CPUs and not be disk-bound. Also, I ran on GCP not Hetzner, so maybe different hardware. SQL in theory makes this trivial, handles many of the big optimizations and looking at the repo, cuts 1000+ LOC down to a handful. Modern SQL engines handle everything for you, which is the whole damned point of SQL. Any decent engine will handle parallelism,…
> top(1) is showing that we're burying the CPU: I think it actually shows that you're IO bound (the 'D' in the 'S' column). On my workstation the query takes ~10.9s after restarting postgres and dropping the os caches. And this is a four year old CPU that wasn't top of the line at the time either. > postgres=# explain select city, min(array_min(array_agg)), avg(array_avg(array_agg)), max(array_max(array_agg)) from te…
The One Billion Row Challenge
341–350 of 366 posts
Re: The One Billion Row Challenge
#342852 ms on an M1 Max
Re: The One Billion Row Challenge
#343Isn't this simply bound by the speed of the disk? Surely none of the suggested optimizations (SIMD, multi-threading) are relevant. It would also depend of how many different stations there are and what they are for the hash lookup, but seriously I doubt this will be anything measurable compared to I/O.
Yes, this is an extremely trivial problem. Anybody who knows how to program in more than one language is going to find this silly. awk or perl would finish it before jit compilation gets started.
I have tried 2 naive awk implementations and both took 10x the basic java implementation btw (I'm sure it too can be optimized).
Re: The One Billion Row Challenge
#344Earlier quoted context omitted.
> Streaming calculation of the exact median with no storage at all is non-trivial at best in the general case It's not "non-trivial" it's impossible . I'm not sure why people think median can be approximated at all. You need to look at every data point and store a counter for the lesser of: (a) all possible values, or (b) all elements. Just consider a data set with 1 million ones and 999,999 zeroes. Throwing away (or…
It certainly is possible to approximate the median: https://aakinshin.net/posts/p2-quantile-estimator/ A quick search shows that Boost.Accumulators have several median estimation implementations available to choose from: https://www.boost.org/doc/libs/1_84_0/doc/html/accumulators/... > Median estimation based on the P^2 quantile estimator, the density estimator, or the P^2 cumulative distribution estimator.
But it brings up an important point: real data that you actually encounter is not a random sampling from "the general case". It is often possible to do a pretty good job approximating the median from real-world data, if you have some understanding of the distribution of that data. You just have to accept the fact that you might be totally wrong, if the data behaves in ways you don't expect. But of course, the more you have to know about your data before running the algorithm, the less useful the algorithm itself is.
The difference is whether you can make guarantees or not. Most algorithm design is concerned about such guarantees: on all possible inputs, this algorithm has at worst such-and-such performance. Hence the reliance on Big-O. You cannot ever make such guarantees on a "median approximator" without specifying some sort of precondition on the inputs.
What guarantees do we want to make? With "an estimator", it'd be nice to say something like: we'd like our approximation to get better given more values. That is: the more values we see, the less the next single value should be able to change our approximation. If you've looked at a billion values, all between [min, max], it'd be nice if you knew that looking at the next one or two values could only have an effect of at most 1 / f(1 billion) for some monotonically increasing f. Median does not have that property: looking at just two more values (even still within the range of [min, max]) could move your final answer all the way from max to min. If you stopped 2 data points earlier, your answer would be as wrong as possible. This remains true, for some inputs, even if you've looked at 10^10^10^10^300 values. The next 2 might change your answer by 100%.
Re: The One Billion Row Challenge
#3451 Billion Row Challenge with Apache Pinot https://hubertdulay.substack.com/p/1-billion-row-challenge-i... 852 ms on an M1 Max
Re: The One Billion Row Challenge
#346Earlier quoted context omitted.
I'd like to see it speed tested against an instance of Postgres using the file Foreign Data Wrapper https://www.postgresql.org/docs/current/file-fdw.html CREATE EXTENSION file_fdw; CREATE SERVER stations FOREIGN DATA WRAPPER file_fdw; CREATE FOREIGN TABLE records ( station_name text, temperature float ) SERVER stations OPTIONS (filename 'path/to/file.csv', format 'csv', delimiter ';'); SELECT station_name, MIN(temper…
Just modified the original post to add the file_fdw. Again, none of the instances (PG or ClickHouse) were optimised for the workload https://ftisiot.net/posts/1brows/
\copy TEST(CITY, TEMPERATURE) FROM 'measurements.txt' DELIMITER ';' CSV;Re: The One Billion Row Challenge
#347Earlier quoted context omitted.
the whole premise is silly though. why would anyone use plain java to compute this when databases were built for this or at least are the most finely tuned for it
It's only silly if you miss the point of the challenge :) Which is to learn something new and have fun along the way.
Also will I get pilloried if I just make it a big StreamOf thing? ;-)
Re: The One Billion Row Challenge
#348Earlier quoted context omitted.
1:05 in PostgreSQL 16 but it was harder than I thought to saturate the CPUs and not be disk-bound. Also, I ran on GCP not Hetzner, so maybe different hardware. SQL in theory makes this trivial, handles many of the big optimizations and looking at the repo, cuts 1000+ LOC down to a handful. Modern SQL engines handle everything for you, which is the whole damned point of SQL. Any decent engine will handle parallelism,…
FWIW, you can make the data loading a decent bit faster: 1) use the integer version of generate_series, the 1e9 leads to the floating point version being chosen 2) move the generate_series() to the select list of a subselect - for boring reasons, that we should fix, the FROM version materializes the result first 3) using COPY is much faster, however a bit awkward to write psql -Xq -c 'COPY (SELECT (1000 random())::in…
1/10th scale tests:
psql -c 'create table temps_int2_copy as select * from temps_int2_copy where 1=0;'
psql -Xq -c 'COPY (SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp FROM (SELECT generate_series(1,1e8::int8))) TO STDOUT WITH BINARY' | psql -Xq -c 'COPY temps_int2_copy FROM STDIN WITH BINARY'
==> 32sec psql -c 'create table temps_int2_copy2 as select * from temps_int2_copy where 1=0;'
psql -c 'INSERT INTO temps_int2_copy2 (city, temp) SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp from generate_series(1,1e8::int)i;'
==> 90sec psql -c 'create UNLOGGED table temps_int2_copy3 as select * from temps_int2_copy where 1=0;'
psql -c 'INSERT INTO temps_int2_copy3 (city, temp) SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp from generate_series(1,1e8::int)i;'; date
==> 45sec (still not faster!)Of course, if we really want to "go fast" then we want parallel loading, which means firing up N postgresql backends and each generate and write the data concurrently to different tables, then each compute a partial summary in N summary tables, and finally merge them together.
echo "COPY temps_int2_copy_p1 from '/var/lib/postgresql/output100m.txt' with csv;" | /usr/lib/postgresql/16/bin/postgres --single -D /etc/postgresql/16/main/ postgres
==> 32sec (saturates one core)The ultimate would be to hack into postgres and skip everything and just write the actual filesystem files in-place using knowledge of the file formats, then "wire in" these files to the database system tables. This normally gets hairy (e.g. TOAST) but with a simple table like this, it might be possible. This is a project I've always wanted to try.
Re: The One Billion Row Challenge
#349Earlier quoted context omitted.
FWIW, you can make the data loading a decent bit faster: 1) use the integer version of generate_series, the 1e9 leads to the floating point version being chosen 2) move the generate_series() to the select list of a subselect - for boring reasons, that we should fix, the FROM version materializes the result first 3) using COPY is much faster, however a bit awkward to write psql -Xq -c 'COPY (SELECT (1000 random())::in…
wow! awesome tips. I knew COPY rocks but didn't realize it would win vs INSERT INTO SELECT FROM ! https://pganalyze.com/blog/5mins-postgres-optimizing-bulk-lo... 1/10th scale tests: psql -c 'create table temps_int2_copy as select * from temps_int2_copy where 1=0;' psql -Xq -c 'COPY (SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp FROM (SELECT generate_series(1,1e8::int8))) TO STDOUT WITH BIN…
We (postgres) should fix that at some point... The difference basically is that there's a dedicated path to insert many tuples at once that's often used by COPY that isn't used by INSERT INTO ... SELECT. The logic for determining when that optimization is correct (consider e.g. after-insert per-row triggers, the trigger invocation for row N may not yet see row N+1) is specific to COPY right now. We need to generalize it to be usable in more places.
To be fair, part of the reason the COPY approach is faster is that the generate_series() query actually uses a fair bit of CPU on its own, and the piped psql's lead to the data generation and data loading being run separately. Of course, partially paying for that by needing to serialize/deserialize the data and handling all the data in four processes.
When doing the COPYs separately to/from a file, it actually takes longer to generate the data than loading the data into an unlogged table.
# COPY (SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp FROM (SELECT generate_series(1,1e8::int8))) TO '/tmp/data.pgcopy' WITH BINARY;
COPY 100000000
Time: 21560.956 ms (00:21.561)
# BEGIN;DROP TABLE IF EXISTS temps_int2; CREATE UNLOGGED TABLE temps_int2 (city int2 NOT NULL, temp int2 NOT NULL); COPY temps_int2 FROM '/tmp/data.pgcopy' WITH BINARY;COMMIT;
BEGIN
Time: 0.128 ms
DROP TABLE
Time: 0.752 ms
CREATE TABLE
Time: 0.609 ms
COPY 100000000
Time: 18874.010 ms (00:18.874)
COMMIT
Time: 229.650 ms
Loading into a logged table is a bit slower, at 20250.835 ms.> Of course, if we really want to "go fast" then we want parallel loading, which means firing up N postgresql backends and each generate and write the data concurrently to different tables, then each compute a partial summary in N summary tables, and finally merge them together.
With PG >= 16, you need a fair bit of concurrency to hit bottlenecks due to multiple backends loading data into the same table with COPY. On my ~4 year old workstation I reach over 3GB/s, with a bit more work we can get higher. Before that the limit was a lot lower.
If I use large enough shared buffers so that IO does not become a bottleneck, I can load the 1e9 rows fairly quickly in parallel, using pgbench:
c=20; psql -Xq -c "COPY (SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp FROM (SELECT generate_series(1,1e6::int8))) TO '/tmp/data-1e6.pgcopy' WITH BINARY;" -c 'DROP TABLE IF EXISTS temps_int2; CREATE UNLOGGED TABLE temps_int2 (city int2 NOT NULL, temp int2 NOT NULL); ' && time pgbench -c$c -j$c -n -f
That's just 1.2GB/s, because the bottleneck is the per-row and per-field processing, due to their narrowness.> The ultimate would be to hack into postgres and skip everything and just write the actual filesystem files in-place using knowledge of the file formats, then "wire in" these files to the database system tables. This normally gets hairy (e.g. TOAST) but with a simple table like this, it might be possible. This is a project I've always wanted to try.
I doubt that will ever be a good idea. For one, the row metadata contain transactional information, that'd be hard to create correctly outside of postgres. It'd also be too easy to cause issues with corrupted data.
However, there's a lot we could do to speed up data loading performance further. The parsing that COPY does, uhm, show signs of iterative development over decades. Absurdly enough, that's where the bottleneck most commonly is right now. I'm reasonably confident that there's at least 3-4x possible without going to particularly extreme lengths. I think there's also at least a not-too-hard 2x for the portion of loading loading data into the table.
Re: The One Billion Row Challenge
#350Earlier quoted context omitted.
> top(1) is showing that we're burying the CPU: I think it actually shows that you're IO bound (the 'D' in the 'S' column). On my workstation the query takes ~10.9s after restarting postgres and dropping the os caches. And this is a four year old CPU that wasn't top of the line at the time either. > postgres=# explain select city, min(array_min(array_agg)), avg(array_avg(array_agg)), max(array_max(array_agg)) from te…
Exactly. The issue is that postgresql takes 37 bytes per row normally, which then causes it to spill out of RAM on the limited VM specified for this challenge, causing the query to be I/O bound, hence the array representation and unnesting to fit it back into RAM. I'm guessing your machine has more RAM ?
It does, but I restarted postgres and cleared the OS cache.
Btw, the primary bottleneck for the array-ified query is the unnest() handling in the functions. The minimal thing would be to make the functions faster, e.g. via:
CREATE OR REPLACE FUNCTION array_avg(_data anyarray) RETURNS numeric IMMUTABLE PARALLEL SAFE LANGUAGE sql AS $$ select avg(a) from (SELECT unnest(_data) as a) $$;
But that way the unnest is still done 3x. Something like
SELECT a_min, a_max, a_avg FROM temps_by_city, LATERAL (SELECT min(u) a_min, max(u) a_max, avg(u) a_avg FROM (SELECT unnest(array_agg) u)) limit 5;
should be faster.