@ChrisNZ :
I've read your article ... and the comments. Thanks 1E6 for writing it - lots of work, well thought out and well presented. Methinks its greatest benefit is presenting a number of techniques, side by side, to expand the horizons of those who have used only one since they know how to use it.
As far as the performance comparisons are concerned per se, unfortunately, they're always circumstantial, as they can't account for a variety of different situations involving many confounding factors. The number/lengths of key components, the number/lengths of satellite variables, absolute and relative sizes of the files, number of matching keys, distribution of available system resources (e.g. disk vs memory), execution time limit vs shared resources limits - all come into play. The responsibility of a high-performance SAS programmer is to take all of those into consideration in order to find an optimal solution by using one's experience, the knowledge of different algorithms/techniques, a dose of heuristics, circumstantial business knowledge of the data, etc. .. well, you know it all too well.
As a little bit of example (purely for illustration rather than for any far-drawn conclusions), in your test case, you're joining on a single integer key. That, alone, represents a good deal of test skewness, as it can make the relative cost of table lookup very small compared to the rest of the task components - provided that an appropriate search algorithm is selected to take advantage of the integer nature of the key. None of the methods you've presented would make use of this integer key property; and yet it's possible since it makes the simplest hash function mod(key,tablesize) the fastest. For instance, try this (the outputs are _NULL_ified to make the comparo purer):
data a (keep = k) b ;
do d = 1 to 1e7 ;
k = floor (ranuni (1) * 1e15) ;
output a ;
if d <= 1e7 / 2 then output b ;
end ;
run ;
%let h =12100003 ; * first prime > 1.2E7 ;
data _null_ /*array_hash*/ ;
array hk [&h] _temporary_ ;
array hd [&h] _temporary_ ;
if _n_ = 1 then do until (z) ;
set b end = z ;
link hash ;
hk[_n_] = k ;
hd[_n_] = d ;
end ;
set a ;
link hash ;
if hk[_n_] ne . ;
d = hd[_n_] ;
return ;
hash: do _n_ = 1 + mod (k, &h) by 1 until (hk[_n_] = k or hk[_n_] = .) ;
if _n_ > &h then _n_ = 1 ;
end ;
return ;
run ;
data _null_ /*canned_hash*/ ;
if _n_ = 1 then do ;
if 0 then set b ;
dcl hash h (dataset:"b") ;
h.definekey ("k") ;
h.definedata ("d") ;
h.definedone () ;
end ;
set a ;
if h.find() = 0 ;
run ;
proc sort data = a out = sa ;
by k ;
run ;
proc sort data = b out = sb;
by k ;
run ;
data _null_ /*sort_merge*/ ;
merge sa (in = a) sb ;
by k ;
if a ;
run ;
Note that the input data arrangement much favors the sort-merge (the files are long and narrow), and even then in combined run time the array-based hash (with the most primitive collision resolution by linear probing) is 33% faster (not to mention the canned hash blown out of the water). Also note that the array-based hash uses 0.4 and 0.5 the memory used by the sort and canned hash, respectively.
Kind regards
Paul D.
Click image to register for webinar
