inner_sort_merge_join.py

def inner_merge_join(left: List[dict], right: List[dict], on: str) -> List[dict]:
	""" (Sort) Merge JOIN: Sort both by JOIN key. Loop through both simulateneously. 

	If matching, advance inner till no match. If no match, advance the smaller attr

	INNER JOIN only implemented
	"""
	output = []

	sorted_left = sorted(left, key = lambda dic: dic[on])
	sorted_right = sorted(right, key = lambda dic: dic[on])

	outer = sorted_left if len(sorted_left) < len(sorted_right) else sorted_right
	inner = sorted_left if len(sorted_left) > len(sorted_right) else sorted_right

	outer_pointer = 0
	inner_pointer = 0 
	mtches = 0

	while(outer_pointer < len(outer) and inner_pointer < len(inner)):
		outer_row = outer[outer_pointer]
		inner_row = inner[inner_pointer]

		if(outer_row[on] != inner_row[on]):
			# Advance the pointer of the lower attr
			if(outer_row[on] < inner_row[on]):
				outer_pointer = outer_pointer + 1
			else:
				inner_pointer = inner_pointer + 1
		else:
			if(outer_row[on] == inner_row[on]):
				# Return rows and advance inner until no match
				row_ret = dict(list(outer_row.items()) + list(inner_row.items()))
				output.append(row_ret)
				inner_pointer = inner_pointer + 1


	return output
	
if __name__ == "__main__":
	tbl1 = [
		{"id": 11, "tbl1_field": "A"},
		{"id": 22, "tbl1_field": "AB"},
		{"id": 55, "tbl1_field": "AE"},
		{"id": 33, "tbl1_field": "AC"},
		{"id": 44, "tbl1_field": "AD"}
	]

	tbl2 = [
		{"id": 11, "tbl2_field": "B"},
		{"id": 11, "tbl2_field": "BB"},
		{"id": 22, "tbl2_field": "BC"},
		{"id": 66, "tbl2_field": "BD"},
		{"id": 77, "tbl2_field": "BE"},
		{"id": 88, "tbl2_field": "BF"},
		{"id": 44, "tbl2_field": "BG"}
		
	]

	# SELECT * FROM tbl1 INNER JOIN tbl2 ON tbl1.id = tbl2.id
	l_out = inner_merge_join(tbl1, tbl2, "id")