Safe Haskell	None
Language	Haskell2010

DataFrame.Operations.JoinPar

Description

Parallel chunked-probe join kernels. The build side is indexed once into a shared, read-only CompactIndex (open-addressing, from DataFrame.Operations.Join); the probe side is split into caps contiguous row ranges and probed in parallel by forkIO workers (no sparks). Each worker makes two passes over its range — a count pass to size its slice, then a fill pass — and writes into the single shared output buffers at a precomputed prefix-sum offset. Because ranges are contiguous and laid out in range order, the produced (probeIxs, buildIxs) vectors are bit-for-bit identical to the sequential hashInnerKernel / hashLeftKernel: probe rows appear in original order and, within a probe row, build matches in ciSortedIndices order.

This is the parallel==sequential correctness gate (see testsOperationsParallelJoin.hs). A sequential fallback is used when there is a single capability or the probe side is below parJoinThreshold; the caller (innerJoin / leftJoin) decides via shouldParallelizeJoin.

Synopsis

parInnerProbe :: Vector Int -> (Int -> (Int, Int)) -> Vector Int -> IO (Vector Int, Vector Int)
parLeftProbe :: Vector Int -> (Int -> (Int, Int)) -> Vector Int -> IO (Vector Int, Vector Int)
shouldParallelizeJoin :: Int -> Int -> Bool
shouldParallelizeSmallBuildProbe :: Int -> Bool
parJoinThreshold :: Int
parBuildThreshold :: Int
parProbeThreshold :: Int

Documentation

parInnerProbe :: Vector Int -> (Int -> (Int, Int)) -> Vector Int -> IO (Vector Int, Vector Int) Source #

Parallel inner-join probe. parInnerProbe sortedIdxs lookup probeHashes returns (probeIxs, buildIxs) identical to a sequential probe of the same index. The build index must already be constructed from the build side.

parLeftProbe :: Vector Int -> (Int -> (Int, Int)) -> Vector Int -> IO (Vector Int, Vector Int) Source #

Parallel left-join probe. Like parInnerProbe but every probe row emits at least one output row; unmatched rows carry a -1 sentinel in the build column.

shouldParallelizeJoin :: Int -> Int -> Bool Source #

Whether a join should take the parallel probe path: more than one capability, a probe side of at least parJoinThreshold rows, and a build side of at least parBuildThreshold rows (a small/hot index is faster probed sequentially).

shouldParallelizeSmallBuildProbe :: Int -> Bool Source #

Whether a small-build join (build below parBuildThreshold, so radix partitioning / sort-merge is not used) should take the parallel probe path: a very large probe side (at least parProbeThreshold) and more than one capability. The shared build index is read-only across threads, so probing it in parallel needs no synchronization. Independent of build size on purpose: the build is already tiny; the cost is the 1e7-row probe hashing, which parallelizes cleanly.

parJoinThreshold :: Int Source #

Below this many probe rows the fork/coordination overhead is not worth it; the caller uses its sequential ST kernel instead.

parBuildThreshold :: Int Source #

Below this many build rows the shared CompactIndex is small and hot, so the sequential hash probe is already memory-bound-fast and the fork overhead loses (measured: a 1e4-row Text-key build probed by 1e7 rows is slower in parallel). Parallelism only pays once the build index is large enough to spill cache — exactly the regime where sort-merge used to be chosen.

parProbeThreshold :: Int Source #

Above this many probe rows the probe-side row hashing and table lookups dominate the join, so partitioning the probe across cores wins even when the build side is small and cache-resident (the regime shouldParallelizeJoin deliberately leaves sequential). Sized at 1e6: below it the per-question gain is swamped by forkIOcoordination overhead, so smallmedium-inner joins stay sequential (measured). This is the small-build large-probe lever closing the medium-factor 1e7 join (1e7 probe x ~1e4 build).