search

don-tay / simpledb

Subset of SQL-compliant DBMS
0 stars 0 forks source link

Bug: Incorrect I/O count for sort merge join operation #14

Closed don-tay closed 2 years ago

don-tay commented 2 years ago

blocksAccessed method for sort merge join is implemented incorrectly: https://github.com/don-tay/simpledb/blob/nested-loop-join/src/simpledb/materialize/MergeJoinPlan.java#L55-L66

This results in sort-merge join always having the least block accessed, and being the join method used by the table planner. 

SQL> select sid, sname, eid from student, enroll where sid = studentid
p1Cost: 19 p2Cost: 3 p3Cost: 13
Running sort merge
 sid sname eid
--------------
  1  joe 14
  1  joe 24
  2  amy 34
  4  sue 44
  4  sue 54
  6  kim 64

without idx on sid:

SQL> select sid, sname, eid from student, enroll where sid = studentid
p1Cost: 2147483647 p2Cost: 3 p3Cost: 13
Running sort merge
 sid sname eid
--------------
  1  joe 14
  1  joe 24
  2  amy 34
  4  sue 44
  4  sue 54
  6  kim 64

Context: p1 - IndexJoinPlan | p2 - MergeJoinPlan | p3 - NestedLoopsJoinPlan

Originally posted by @xinyee20 in https://github.com/don-tay/simpledb/issues/11#issuecomment-1046645773