F2023 #11 - Join Algorithms (CMU Intro to Database Systems)

Matt Butrovich (mattbutrovi.ch/)
Slides: 15445.courses....
Notes: 15445.courses....
15-445/645 Intro to Database Systems (Fall 2023)
Carnegie Mellon University
15445.courses....

[@nathanwilkinson2080]

Great lecture, thank you!

[@murtnowski]

Outstanding Job! I love it!

[@ibrahimrabbani94]

Thank you for the lecture! In the degenerate worst case where every tuple in relations R and S has the same value for the join key, Sort-Merge Join's merge cost is M + N where M and N are the number of pages in relations R and S respectively. Since this looks like a Block Nested-Loop Join, why can't we optimize this to M + CEIL(M/B-2)xN where B is the number of available pages in the buffer pool?

[@mephistotel87]

The lecture is great!

[@nanunsaram]

Thank you Matt!

[@Lecker9419]

Still confused about the part for the case of a simple block nested loop join (no index), why wouldn't I want to reserve as much BP space as possible for my inner table ? the inner table is the going to be iterated over and over but for the sequentially scanned outer table we just need one page which can be removed easily with the next because it's not going to be accessed anymore, why keep cold data in the BP ? ...

[@claudeli141]

I think it is because each iteration of the outer loop (for each block in R) needs to scan all N blocks of the inner table. If the inner table is too large to fit in memory, for each iteration, we always need to load N blocks into BP. So we need to reduce the number of iterations in the outer loop, from M to ceil(M/(B-2)). Hope it is clear.

[@blockpaper]

Simply do math for each case. We multiply the number of readings of the inner table blocks by the number of readings of the outer table blocks ("read some blocks from the outer table into memory, make a scan of inner table, find tuples to satisfy condition; read into memory, make a scan, find tuples, read.." and so on). Therefore, the more outer table blocks we put in memory, the better it will be (fewer inner table scans will need to be done). Ideally, we would like the outer table to fit completely into memory, and then we will read the outer table once and the inner table once.

[@user-lv2ht3qv2l]

thanks a lot!

[@Shadb8si]

@andypavlo what is the song used in the ending credits for each lecture ?

[@chriswong2748]

Why the right corner always hide part of the slide over all these years??

[@olegpatraschku3736]

download the slides, follow along.

[@BenHutchison]

Omg. This speaker is strenuous to follow. If he spoke half as fast with half the jargon he'd be twice as clear.

[@wujizhang5780]

I think it's pretty good, and the instructor's pronunciation is very standard and clear. As a Chinese student, I feel that this course allows me to learn about DBMS while also practicing my English listening skills, since both Andy and this teacher speak at a relatively fast pace.

[@connortsui646]

if you had twice the braincells maybe you would take half a second to reconsider commenting at all?

[@andypavlo]

@BenHutchison Please apply to CMU and come do a better job: csd.cmu.edu/academics/doctoral/admissions