How nested loop, hash, and merge joins work.

System Design for SDE-2 and above: arpitbhayani.me/masterclass
System Design for Beginners: arpitbhayani.me/sys-design
Redis Internals: arpitbhayani.me/redis
Build Your Own Redis / DNS / BitTorrent / SQLite - with CodeCrafters.
Sign up and get 40% off - app.codecrafters.io/join?via=...
In this video, I delved into the essential concept of joins in databases, exploring the algorithms used for table joins. I explained the nested loop join, where each row from one table is matched with every row from the other. The merge join involves sorting tables on join attributes for efficient merging. Hash join uses hash functions to prepare and match rows based on the join attribute. SQL engines choose these algorithms based on table statistics. Understanding these join algorithms is key to optimizing database performance.
Recommended videos and playlists
If you liked this video, you will find the following videos and playlists helpful
System Design: • PostgreSQL connection ...
Designing Microservices: • Advantages of adopting...
Database Engineering: • How nested loop, hash,...
Concurrency In-depth: • How to write efficient...
Research paper dissections: • The Google File System...
Outage Dissections: • Dissecting GitHub Outa...
Hash Table Internals: • Internal Structure of ...
Bittorrent Internals: • Introduction to BitTor...
Things you will find amusing
Knowledge Base: arpitbhayani.me/knowledge-base
Bookshelf: arpitbhayani.me/bookshelf
Papershelf: arpitbhayani.me/papershelf
Other socials
I keep writing and sharing my practical experience and learnings every day, so if you resonate then follow along. I keep it no fluff.
LinkedIn: / arpitbhayani
Twitter: / arpit_bhayani
Weekly Newsletter: arpit.substack.com
Thank you for watching and supporting! it means a ton.
I am on a mission to bring out the best engineering stories from around the world and make you all fall in
love with engineering. If you resonate with this then follow along, I always keep it no-fluff.

[@dave-smith]

Database internals are just amazing. Thanks for explaining.

[@arpanmukherjee4625]

The biggest take away is, this gives some better algorithms to use when you need to join data coming from two different services and then augument it with your own DB's data and present it. Manual joins as we call them.

[@theonewhobullies]

Bro I was thinking about it a few days back as how it works internally, thanks a lot

[@tesla1772]

Hash join is something that we also do in application level code when large data is to be processed. Good to know various others ways as well✌️

[@irshadmohideen]

Excellent explanation, thanks so much.

[@rishabhthakur2028]

Thanks for explaining arpit 👍🏻

[@JainNamit]

First of all, thanks for the information. So, i wanted to know, can we tell mysql or postgress to do this type of merge on these two tables evrytime or when i merge this on this specific column only, or i can force it using some kywords in my sql query. If yes, then please upload next part of this video as practical explaination with query running on mysql, as this was mostly theoretical.

[@GauravSingh-tn8sv]

amazing. Does anyone know if we can get these notes anywhere. Helps in recalling post watching

[@rushidesai2836]

Arpit, you are one of the most intelligent software engineer I have ever come accross in my life. Lots of respect.

[@AsliEngineering]

Thank you Rushi!

[@kaustubhgupta12]

One question: In merge join, does the SQL engine choose the type of sorting algorithm to implement as well or it is usually fixed?

[@cheems2586]

next on subQuery vs joins please

[@arpanghoshal2579]

Is the intial query that was shown in the start of the video correct? I believe we need to group by to get the count of all belongs from a user something like select u.id, count(*) b_count from blogs b inner join users u on b.user_id = u.id grouby u.id order by b_count desc

[@Han-ve8uh]

Agree. Makes author lose huge credibility when i saw that

[@abdelilahou2822]

I just discovered your channel today, the way you explain things is unique and i love it ❤

[@AsliEngineering]

Thank you so much :)

[@anukulprakashsaxena47]

I didn't know, the implementation of joins could be so simple.

[@getumangon]

Average Time complexity for HashJoin algorithm is O(n + k), where n=no. of users & k=no. of ids stored in one hash index Please correct me if I’m wrong

[@natraj6120]

This is so far best way to explain things everything by example and the beauty is making it extremely simple to understand is your your USP

[@AsliEngineering]

Thanks!

[@pococopo2538]

I'm a an average programmer and I want to develop my own programming language but I didn't know anything about programming languages other than the high level. Could you please list down the things that I would need to know in order to develop my own programming language.

[@user-tp9bg7sz1t]

Summary of this Video: Database joins are essential for relational databases, enabling transactional and analytical queries. Databases employ various algorithms to perform joins, including: Nested Loop Join: Iterates through each row in the left table and matches it with every row in the right table, checking the join condition. Merge Join: Sorts both tables on the join attribute and merges them, efficiently joining rows with matching join attributes. Hash Join: Creates a hash table from one table using the join attribute as the key, then performs a hash lookup for each row in the other table to find matching rows. The choice of algorithm depends on factors such as data size, distribution, and join type. Database query optimizers analyze statistics to determine the most efficient algorithm for each join operation.

[@SakshiChaudhary-ug8uw]

Does merge join also go through a nested loop? If so, how is it better than nested loop join?

[@AsliEngineering]

Because of sorting, the join becomes an O(n) operation. Exactly how we merge two sorted arrays into one is O(n).

[@soundharis8582]

Ji, y blog id is not sorted how to do that too while joining

[@junior.santana]

because the join clause uses the user id, not really necessary in this context but if you want the result sorted bu blog id you can just add an order by clause to your query

[@nihshrey]

No fluff as always.

[@VisKu-ck1wr]

you start a DBMS series

[@AsliEngineering]

There are 25 database engineering videos on my channel. You can find the playlist on my channel

[@bostonlights2749]

This looks like a leetcode question

[@anukulprakashsaxena47]

me first

[@anukulprakashsaxena47]

hehehe

[@aakashyadav1589]

what happened to your eyes?