hpcc-systems/HPCC-Platform — pull request #2925 by jakesmith (2012-07-23 15:59:25+00:00)
Title: gh-2675 - Implementation of spilling hash dedup

Allow DEDUP,HASH to deal with datasets larger than memory.

General idea is to spill to buckets when memory full, then process each
bucket in turn, creating more buckets if still too much to deal with.
The impl. streams rows from the input, creating HT entries based on the keys
it's dedupping on. The 1st unmatched row is output, the rest are dedupped.

Each phase creates N in memory buckets. On a spill request, one of the
buckets will be spilled, any new rows that fall in this bucket that are not
dedupped are spilled to disk. The last bucket left in memory will be spilt
in stages, as spill requests come in. This allows the remaining bucket HT to
keep filtering out dedups whilst it can.

Once all have been filtered/spilt by the existing HT, Any reamining HT is discarded and the buckets are read as input, and the process repeated.

The # of buckets is estimated if possible, based on the # of inputs rows.
The 1st round the # of rows may not be available (unless in meta).
On subsequent rounds (reading back buckets), the total # of rows + # of rows it reached at the spill point are known and are used as the basis for # of buckets in the next round.

Signed-off-by: Jake Smith