hpcc-systems/HPCC-Platform — pull request #2777 by jakesmith (2012-07-05 14:47:01+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.

On a spill request, some of the HT is spilt to key buckets and all new
rows that are not dedupped are spilled to row buckets. It will spill a % of
the HT at a time, not wanting to discard if all, because the more you have
the more you can continue to dedup by.

Once all have been filtered/spilt by the existing HT, the 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