An inner join is an operation that combines two data tables into one table, based on matching column values. The simplest way of implementing this operation is the nested loop join algorithm, but a more scalable alternative is the hash join algorithm.

Task[edit]
Implement the "hash join" algorithm, and demonstrate that it passes the test-case listed below.

You should represent the tables as data structures that feel natural in your programming language.

Guidance
The "hash join" algorithm consists of two steps:

 Hash phase: Create a multimap from one of the two tables, mapping from each join column value to all the rows that contain it.

 The multimap must support hash-based lookup which scales better than a simple linear search, because that's the whole point of this algorithm.
 Ideally we should create the multimap for the smaller table, thus minimizing its creation time and memory size.
 Join phase: Scan the other table, and find matching rows by looking in the multimap created before.


In pseudo-code, the algorithm could be expressed as follows:

let A = the first input table (or ideally, the larger one)
let B = the second input table (or ideally, the smaller one)
let jA = the join column ID of table A
let jB = the join column ID of table B
let MB = a multimap for mapping from single values to multiple rows of table B (starts out empty)
let C = the output table (starts out empty)

for each row b in table B:
   place b in multimap MB under key b(jB)

for each row a in table A:
   for each row b in multimap MB under key a(jA):
      let c = the concatenation of row a and row b
      place row c in table C

Test-case


 Input

 Output





 A =




 Age 
 Name


 27 
 Jonah


 18 
 Alan


 28 
 Glory


 18 
 Popeye


 28 
 Alan




 B =




 Character 
 Nemesis


 Jonah 
 Whales


 Jonah 
 Spiders


 Alan 
 Ghosts


 Alan 
 Zombies


 Glory 
 Buffy



 jA =

 Name (i.e. column 1)

 jB =

 Character (i.e. column 0)





 A.Age 
 A.Name 
 B.Character 
 B.Nemesis


 27 
 Jonah 
 Jonah 
 Whales


 27 
 Jonah 
 Jonah 
 Spiders


 18 
 Alan 
 Alan 
 Ghosts


 18 
 Alan 
 Alan 
 Zombies


 28 
 Glory 
 Glory 
 Buffy


 28 
 Alan 
 Alan 
 Ghosts


 28 
 Alan 
 Alan 
 Zombies


The order of the rows in the output table is not significant.

If you're using numerically indexed arrays to represent table rows (rather than referring to columns by name), you could represent the output rows in the form [[27, "Jonah"], ["Jonah", "Whales"]].




use framework "Foundation" -- Yosemite onwards, for record-handling functions
 
-- HASH JOIN -----------------------------------------------------------------
 
-- hashJoin :: [Record] -> [Record] -> String -> [Record]
on hashJoin(tblA, tblB, strJoin)
    set {jA, jB} to splitOn("=", strJoin)
 
    script instanceOfjB
        on |λ|(a, x)
            set strID to keyValue(x, jB)
 
            set maybeInstances to keyValue(a, strID)
            if maybeInstances is not missing value then
                updatedRecord(a, strID, maybeInstances & {x})
            else
                updatedRecord(a, strID, [x])
            end if
        end |λ|
    end script
 
    set M to foldl(instanceOfjB, {name:"multiMap"}, tblB)
 
    script joins
        on |λ|(a, x)
            set matches to keyValue(M, keyValue(x, jA))
            if matches is not missing value then
                script concat
                    on |λ|(row)
                        x & row
                    end |λ|
                end script
 
                a & map(concat, matches)
            else
                a
            end if
        end |λ|
    end script
 
    foldl(joins, {}, tblA)
end hashJoin
 
-- TEST ----------------------------------------------------------------------
on run
    set lstA to [¬
        {age:27, |name|:"Jonah"}, ¬
        {age:18, |name|:"Alan"}, ¬
        {age:28, |name|:"Glory"}, ¬
        {age:18, |name|:"Popeye"}, ¬
        {age:28, |name|:"Alan"}]
 
    set lstB to [¬
        {|character|:"Jonah", nemesis:"Whales"}, ¬
        {|character|:"Jonah", nemesis:"Spiders"}, ¬
        {|character|:"Alan", nemesis:"Ghosts"}, ¬
        {|character|:"Alan", nemesis:"Zombies"}, ¬
        {|character|:"Glory", nemesis:"Buffy"}, ¬
        {|character|:"Bob", nemesis:"foo"}]
 
    hashJoin(lstA, lstB, "name=character")
end run
 
 
-- RECORD FUNCTIONS ----------------------------------------------------------
 
-- keyValue :: String -> Record -> Maybe a
on keyValue(rec, strKey)
    set ca to current application
    set v to (ca's NSDictionary's dictionaryWithDictionary:rec)'s ¬
        objectForKey:strKey
    if v is not missing value then
        item 1 of ((ca's NSArray's arrayWithObject:v) as list)
    else
        missing value
    end if
end keyValue
 
-- updatedRecord :: Record -> String -> a -> Record
on updatedRecord(rec, strKey, varValue)
    set ca to current application
    set nsDct to (ca's NSMutableDictionary's dictionaryWithDictionary:rec)
    nsDct's setValue:varValue forKey:strKey
    item 1 of ((ca's NSArray's arrayWithObject:nsDct) as list)
end updatedRecord
 
 
-- GENERIC FUNCTIONS ---------------------------------------------------------
 
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from 1 to lng
            set v to |λ|(v, item i of xs, i, xs)
        end repeat
        return v
    end tell
end foldl
 
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map
 
-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: Handler -> Script
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn
 
-- splitOn :: Text -> Text -> [Text]
on splitOn(strDelim, strMain)
    set {dlm, my text item delimiters} to {my text item delimiters, strDelim}
    set lstParts to text items of strMain
    set my text item delimiters to dlm
    return lstParts
end splitOn