Welcome to TDBSoverflow, Our class's own StackOverflow. Our rules:
  1. Use only meaningful and self-explanatory titles
  2. Tag your questions with meaningful keywords
  3. Use upvotes and downvotes to rate the answers
  4. When you receive a satisfying answer - Click the "V" button
Remember: you may get up to 5 bonus points to your final grade!

2016 שאלה 3 א מועד

+1 vote

במבחן הבא


שאלה 3 סעיף א

למה בסעיפים 4 ו-5 עשו הכפלה של 


ולא חיבור כמו שלמדנו עד היום? 

כלומר, למה הם מחשבים את עלות הMERGE (סעיפים 4 ו5) עם מכפלה ?

תודה !

asked Feb 4, 2018 by tikitak (2,970 points)

1 Answer

+1 vote
Best answer
See http://courses.cs.tau.ac.il/0368-3458/forum/index.php?qa=321&qa_1=sort-merge-join-i-o-complexity (also the comments there) about this issue.

(To understand why it's multiplicative, take the edge case where the column has only 1 value in both relations, and each relation has 1,000 rows - The result will be a relation with 1,000,000 rows, and to create it you'll have to go over every page of one relation, for every page of the other)
answered Feb 4, 2018 by Assaf (31,090 points)
selected Feb 4, 2018 by tikitak