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"]].




 
Module HashJoin {
      \\ normally we define variables when we put values to names
      \\ so we can remove these two lines
      Def Name$, Nemesis$
      Def Long m, mc, items_size, A
 
      \\ Lets make a container which use keys with hash function
      Inventory A      
      \\ A now is a pointer to an Inventory, with Len(A)=0
      \\ Print Type$(A)="Inventory"
 
      \\ empty stack. We use current stack to place data
      Flush
      \Input B
      data "Jonah", "Whales"
      data "Jonah", "Spiders"
      data "Alan", "Ghosts"
      data "Alan", "Zombies"
      data "Glory", "Buffy"
      \\ Keys are unique, This is the HASH PHASE
      While not empty { 
            Read Name$, Nemesis$
            If Exist(A, Name$) Then {
                  m=Eval(A)  ' get a pointer to array
                  Stack m {Data Nemesis$}
            } Else Append A, Name$:=Stack:=Nemesis$  ' a stack object with one item
      }
      \\ Input A, this is the Long Table
      data 27, "Jonah"
      data 18, "Alan"
      data 28, "Glory"
      data 18, "Popeye"
      data 28, "Alan"
 
      \\ This is the JOIN PHASE
 
      items_size=stack.size/2
      \\ using items_size we can append data (using data) to stack
      \\ $(0) is the default handler for columns.
      \\ Letters justify to left, numbers to right.
      \\ Letters can use more columns, and maybe wrap to more lines.
 
      Print $(0), "Output during join"
      Print "A.Age", "A.Name","B.Character", "B.Nemesis"
      While items_size>0 {
            Read Age, Name$
            If exist(A, Name$) Then {
                  m=Eval(A)   ' extract a pointer, this is for a stack object
                  mc=Each(m)  ' make an iterator
                  While mc {
                        \\ we use $(1) for left justify numbers too
                        \\ normal StackItem$(stackobject) return top only
                        \\ we have to use StackItem$(stackobject, 3) to get 3rd
                        \\ or StackItem(stackobject, 3) if it is numeric.
                        \\ but here mc is iterator, and place the cursor value to it
                       Print $(1), Age, Name$,Name$, StackItem$(mc)
                        \\ so now we place at the end of current stack the same output
                       Data Age, Name$,Name$, StackItem$(mc)
                  }   
            } 
            items_size--
      }
      \\ split rem line after : to use second way
      rem : goto secondway
      Print $(0), "Output after join"
      Print "A.Age", "A.Name","B.Character", "B.Nemesis"
      While not Empty {
            Print $(1), Number, Letter$, Letter$, Letter$
      }
      Exit
secondway:
      Print $(0), "Output after join using format$()"
      Print Format$("{0:5} {1:10} {2:10} {3:20}","A.Age", "A.Name","B.Character", "B.Nemesis")
      While not Empty {
            Print format$("{0::5} {1:10} {2:10} {3:20}", Number, Letter$, Letter$, Letter$)
      }
}
HashJoin
 