1BRC in KDB/Q

[DefconQ]

1BRC in KDB/Q

[DefconQ]

[sharpobject]

What hardware are you using and how does it read the file at nearly 200GB/s?

[tfmark]

I think the issue for KDB/Q is efficiently reading the file (or rather, how to parallelise the file read).

Just reading in the file alone, via .Q.fsn, takes 2 minutes on my machine.

\ts .Q.fsn[{};`:measurements.txt;536870912] // 512MB chunks
127813 4050501232

I had a go at figuring out the right places to split the file and read it in, but it's still awfully slow. The peach doesn't appear to be doing anything useful...

findLineFeed:{[filePath;offset;searchLength]
    offset + first where 0x0a = read1 (filePath;offset;searchLength)
  }

getChunks:{[filePath;numberOfRows]
    fileSize: hcount filePath;
    // approximately 13 chars per line on average in test data
    approxChunkLength: numberOfRows * 13;
    numberOfChunks: ceiling fileSize % approxChunkLength;
    approxOffsets: 1 _ til[numberOfChunks] * approxChunkLength;
    // max row length: 100 + count ";-99.9\n"
    offsets: 0,1 + findLineFeed[filePath;;107] peach approxOffsets;
    lengths: (1 _ deltas offsets),fileSize - last offsets;
    // returns list of (filePath;offset;length)
    :filePath,/:offsets,'lengths;
  };


f:{[rows]
    0!select Min:min Measurement, Max:max Measurement, Count:count i, Sum:sum Measurement by Station from flip`Station`Measurement!("sf";";") 0: rows
  };

filename: `:measurements.txt

\ts t:raze f peach getChunks[filename;10000000]  // approximately 1mio rows per chunk -> 267646 54368656
select min Min, max Max, sum[Sum] % sum[Count] by Station from t

Edit:
Ran on a different machine:

q)\ts t:raze f peach getChunks[filename;10000000]
189610 18400

... hopefully a Q God can swoop in and come up with a decent implementation.

[mkst]

With enough RAM the calculation can be done as 1 line, but breaking it into the load vs the aggregation:

\ts t:flip`Station`Measurement!("sf";";") 0: `:measurements.txt
304032 25769821840 // (milliseconds;bytes) i.e. ~5 minutes, 24GB RAM used

\ts select Min:min Measurement, Max:max Measurement, Mean:avg Measurement by Station from t
2847 8589992928 // ~2.8 seconds, 8GB RAM 

I haven't managed to get any improvement with the above code leveraging peach. I feel like I'm missing something...:

\ts t:raze f peach filename,/:getChunks[filename;100000000] / 11 chunk(s)
383154 331920

\ts t:raze f peach filename,/:getChunks[filename;10000000]  / 107 chunks
316436 2631952 

\ts t:raze f peach filename,/:getChunks[filename;1000000]   / 1062 chunks 
311177 21089552 

[DefconQ]

I was having a look at this https://tech.marksblogg.com/billion-nyc-taxi-kdb.html and was thinking of using named pipes but I am still trying to figure it out

[tfmark]

Testing out the new 4.1t release with multithreaded 0: shows a decent improvement. 90 seconds down from 5 minutes.

$ q -s 16
KDB+ 4.1t 2024.01.25 Copyright (C) 1993-2024 Kx Systems
l64/ 16()core 64194MB *removed*

\ts t:flip`Station`Measurement!("sf";";") 0: `:measurements.txt
94909 17179871376
\ts select Min:min Measurement, Max:max Measurement, Mean:avg Measurement by Station from t
3012 8590024672

[avec-zz]

you might find that multi-process helps a lot
on my machine (which mind you much smaller than yours) i get a 5-6x reduction

{system"q -p ", x , " </dev/null"}each string s:3000+til abs system"s"
.z.pd:`u#hopen each s

and then just running the same script up yours from above but with -s -12

(could also tune the number of chunks further to match cores better, etc.)