The ORDER BY Algorithm Is Harder Than You Think
HTML-код
- Опубликовано: 1 июл 2024
- In this video I describe in detail how my implementation of the K-Way External Merge Sort algorithm works. K-Way External Merge Sort is an algorithm used to sort large datasets that don't fit in main memory (usually RAM). Therefore, this algorithm is used by databases like Postgres to process ORDER BY queries when tables don't fit in memory. The algorithm consists of a series of "passes" through one or multiple files and a number of in-memory buffers used to load and process different chunks of a file in each pass. The end result is a file that contains all the requested rows sorted by the keys given in the ORDER BY clause.
🌐 LINKS
Algorithm Implementation:
github.com/antoniosarosi/mkdb...
✉️ CONTACT INFO
Business Email: business@antoniosarosi.io
Contact Email: sarosiantonio@gmail.com
Twitter: / antoniosarosi
Instagram: / antoniosarosi
LinkedIn: / antoniosarosi
🎵 MUSIC
• [Chillstep] Broken Ele...
• Ptr. - Genesis
• Digital Road
• Juno
📖 CHAPTERS
00:00 Introduction
00:22 The Memory Problem
01:32 Database Tables & Sorting
03:18 K-Way Data Structures
04:38 Algorithm Execution (Pass 0)
06:17 Pass 1
09:22 Pass 2
11:07 I/O Complexity
11:58 Variable Length Data
13:16 Final Thoughts
🏷️ HASHTAGS
#programming
#computerscience
#algorithm 
Наука
Since you do "limit 100", can't the query planner be smarter and do some sort of limited sorting that drops off entries automatically? Like an array that holds 100 entries, and every entry is just inserted into there, but the excess goes off and is discarded automatically.
I actually wonder if you can't do this for most reasonable queries too!
Maybe it can, I didn't implement it myself though.
I also had the same thought - for any limit N result that is easy enough fit in ram you could do this with no extra disk space required and only one pass of the data. take first N rows, sort them and then load more data from the file in big enough chunks (10MB?). check each row against the last in the sorted result table. if the checked row is before the last in the result table, keep it in an unsorted pile that just tracks the last in the pile, and then move the last-pointer in the sorted result table to the previous entry. continue till the last in the unsorted pile is after the current last in the sorted pile, then merge and sort the two together, keeping the first N again. repeat till whole database has been scanned.
@@treelibrarian7618 Yeah the algorithm seems pretty obvious, but you'd have to figure out if the limit actually fits in memory and the problem is you're dealing with variable length data (not all rows are the same size). It's not as easy as it seems, but it doesn't change much anyway, you still need an external sort algorithm, I don't even know why I added the limit in the example.
@@tony_saro Even variable length has a maximum length, so you can conservatively estimate the maximum for that.
@@paulstelian97 You can estimate a max size using the table schema, as long as it doesn't have TEXT or BLOB fields it's pretty reasonable. But anyway, I'm just so dumb that I didn't even think about optimizing LIMIT queries when I wrote the DB, I actually didn't even implement LIMIT, I only put it in the video example because usually you won't SELECT * FROM a giant table, so I thought it'd be more "realistic", but still, as mentioned, that doesn't change anything about the video, when applicable you still need an external sort algorithm. I might pin this comment if more people have doubts about this.
Something so simple ended up being so complex and you didn’t even talk about distributed DBs. Top notch
I'm watching this just from the perspective of someone wanting to sort tables that might become very large. This explains why it's so important to create indexes on any columns you might want to sort.
True, BTree indexes will skip this algorithm altogether.
This is top tier. The people who invented these algorithms. Insane. We are taking technology for granted. You explain this really well. For a person who doesn’t have a formal computer science background, this video helps me understands how the tools I use day to day work under the hood
I have a formal Computer Science background and I still find databases very hard to understand 😂. There's a lot of research that went into them over the past 5 decades. People who came up with these algorithms are definitely insane.
@@tony_saro Well CS is kinda orthogonal to the database design. While RMDBs are based on math more-or-less, you won't be able to explain why Mongodb, a No-SQL database, supports join operations, while an egregiously RDBMS Postgresql supports egregiously unrelational formats like JSON and XML, with math theory alone.
And SQL databases weren't THAT math-based to begin with, back when PostgreSQL started there was no such thing as "SQL compliant", since every RDB had its own incompatible flavour of SQL. Considering it was also the time when the applications were written expecting to talk to the DB directly, the hatred for SQL and the need for ORMs at the time makes sense, especially since there was no XML crutch to use as a go-to serializible format for messaging.
This is what for I pay my internet bills. Btw great work and explained well
Thank you
This video is pretty good at picturing file operations as something that just works and not a clusterfuck at all.
It just works but it's not easy to implement at all 😂
You are a legend. I've just watched your video coding a database and I'm very impressed. I'd really like to see you coding a compiler/interpreter. I know it takes a while, but you have awesome didactics. Keep going man, your channel is top tier!
I will at some point, now I'll focus on smaller projects because the database drained all my energy 😂
Que sorpresa encontrarme con videos tuyos de nuevo! Finalmente todos los años que llevo aprendiendo inglés valieron la pena 😂. Mucho animo con este canal me encantan tus vídeos y aprendo mucho de ellos
You opened a door of new kinds of algorithms for me. I never realized that there is a huge world of algorithms and data structures to work with data that don't fit in memory. Amazing!
This is actually valuable lessons presented in awesome way. Man i just hope you blow up because we need way more of this this type of content.
Working on it 📈
You have explained it in such a way that I have understood it even though I am an HTML programmer.
Damn! This guy is next level - insane quality. Bravo!
This is some great content, man! I really appreciate the effort that you put into it and for making it available for free on RUclips. Thanks!
Thanks man
No hay cosa más hermosa que ver tu contenido en inglés tambien 🥹🫶
Amo enserió tu contenido brou ❤
At my work, we have a project where in an application several queries are run, the results are mapped into memory via 'Object Relational Mapping' and then stuff like joins, limiting and SORTING is done in the application with the RAM of the query results. I pointed out the performance difference it would make but the fact that it's not even possible to do this for bigger tables real adds some fuel to the fire :D Great video, shows why leaving as much processing as possible to the DBMS is a good idea
If you're selecting only a few megabytes of data that's probably fine, but otherwise the database will do a much better job, it's designed and optimized for that.
You do joins in the application instead of on the database???? Why???
@@TapetBart We used microservices and chose to have one database per service. Turnrd out that joining across multiple databases is very cumbersome especially if they have different credentials. So we simply did the joins with ORM in the application... and by "we" I mean my team before I joined the project. Later I suggested we used one schema per service eliminating all of that. Don't even know why we used microservices in the first place - we don't have to scale out the app for higher throughput because only a few dozen users use it at once
@@gu1581 ah, makes perfect sense then.
I am doing something a bit similar with DuckDB.
I've heard this kind of algorithm since university but too lazy to dig to it, now thank you for helping me got its idea 💪
Very intuitive and concise explanation!
Really nice video man. Merge sort was my favorite sorting algorithm when I was beginning my journey into computing. Nice to see that what databases use is a variation of it (with a lot more complications hehe). Saludos de Brazil.
Very good explanation and amazing animations! Please keep up the content!
The explanation is so clear, I didn't have to put any effort to get the idea 👏👏👏
I subscribed, dropped a like and I hope you continue producing great content 🙏🏻
I will, thanks for the sub and like 👍
Awesome. Great work
Que buen videoo!! Muchisima suerte y ánimo con este canal! Tienes muchísimo potencial para crecer. No te rindas y muchísimo ánimo❤❤
Great presentation and explanation on this topic. I've happily subscribed
Outstanding job! So well presented and extremely clear.
Very well explained. I look forward to more videos!
Working on it 👨💻
This channel is lit, man, instant sub 🎉
Thank You again! A really interesting problem with different sizes.
Pretty good explanation! I just remember your first videos in the spanish channel and it's just amazing to see how you are progressing as engineer!
Fascinating! Subscribed.
Muy buenos tus videos. Las animaciones hacen que sea mucho más fácil de entender. Saludos!
wow such a clear explanation 👍👍
El rey a vuelto, ahora sí hay un buen motivo para aprender inglés.
Buen vídeo, me alegro de volver a verte
Gran explicación, sigue asi, ademas me ayudas a mejorar mi ingles, un saludo desde Colombia
Just subed, love the video hopefully, you do many many more and gain a yuuugggee fan base
Amazing explanation about the sorting, but I'm actually not sure you need to sort the whole table any time someone asks for top N values...
It would make much more sense to select the top 100,and then just sort that 100
Check the pinned comment
Hey! I think what you did in your Spanish channel was much less niche and this content definitely looks much much more polished and informative. Congratulations!
Excelente como siempre 💯💪
glad you went in-depth about this topic. will you do more like this with other sub-topics? or do you have a new big project you're working on that you will release in the future when done?
Both, next video will be similar to this one and then I'll move to another project
@@tony_saro awesome, looking forward to it. thanks a lot!
Wow, this was very well explained. Thanks for posting. Can we have more videos plz. Thank you again
Sure, I'm working on a video similar to this one focused on algorithms and then I'll start working on another #mkown episode
Really good content, like it
This video is complex as is, and now I am wondering what will happen when we have to implement Isolation.
I guess, it'd simply be reading required pages during initial run, and then we can work with that dataset and sort it
Here's one more, implementing postgres statement timeout
Regarding dealing with variable-length, during pass-0, when outputing a sorted page of tuples, offset from the start of the file and page size can be recorded in an in-memory 'page file' which can be just an ArrayList (java background here, use something which can grow and has 0-n lookup speed). Later stages can use that 'page file' list as a way to lookup the position of the page in the file for the cursor to use. Their outputs will generate a new 'page file'.
Now, if we want to parallelise this algorithm, since we have the offset and size, we can let each worker thread find the location of whichever page range its going to be working with using that 'page file'. The output will always be starting from the minimum offset and be the total size of the range and the 'page file' since its an Array List each thread can insert in the appropriate index the new page values.
That's more or less what I'm doing but you can't store it in memory only, let's say you need to sort 1TB and pages are 4KB, you'd need to store the offsets of approximately 250 million pages, using 4 bytes per offset would already require 1GB of memory. So in case that happens you need to store what you call "page file" on disk as well. Another very important detail is that the number of pages will change in each different run, just like I showed the example of producing 3 pages from 2 pages only, maybe in the next pass you produce 1 page using 3 pages. It's still paralelizable, but you have to store the offsets for each thread during each run.
And this is just a basic algorithm I came up with, if you take a look at the Postgres version it's much more complex than what I've explained here 😂.
@tony_saro Will take a look. Also I didn't consider such large queries where GBs or even TBs of data are involved.
The videos are great. Got me thinking on a lot of stuff around db engine design.
Looking forward to more videos 😁
Great video, so for every order by query, a separate file with the sorted results will be produced? Or does it actually sorts the records in place (in the db files) and keep them sorted for later queries ?
Separate file unless the results fit in memory
Another great video. I would really like to see the code of this.
It's on GitHub, linked in the description.
Please keep up the good job
This reminds me the bottom up approach of merge sort, tricky, would this K-way done in such approach actually? Subcribed and liked, hope this channel always continue. Here are DSA topics beyond textbooks but also explained well, specialized for DB . I remember "The Arts of Programming" mentioned external sort too, from random places, I bookmarked some other external sorting algo: Poly-phase Mergesort, cascade-merge, oscillating sort, I know I don't know them
It's similar to bottom up you can represent the passes as a tree
Nice seeing someone else writing Rust code
I found my new role model
Great!
Perfectamente explicado, y eso que no se me da muy bien el inglés
Are there any other external sorting algorithms like this?
Yes, SQLite 3 uses something called PMA (Packed Memory Array) to sort on disk. I don't know how it works, didn't research enough.
Cómo te volviste tan fluido en inglés? Llevo años con el inglés y no soy ni la mitad de fluido...
Escuchando cómo hablan los nativos y practicando la pronunciación. Una cosa es el inglés que te enseñan en la escuela o academias y otra es el inglés que se habla en la calle 😂.
Una pena que en la comunidad hispana no haya interés para este tipo de temas :( La mayoría de gente solo se centra en el desarrollo web, cuando no conocen el fascinante mundo del bajo nivel
Justo, por eso me he cambiado a la inglesa porque esto es lo que me interesa a mí.
@@tony_saro
Mucho ánimo con este nuevo canal.
Hey pal! Thank you very much! I wanna to create my own dbms(cloud, embedded and so on) too! If I would have a some result than can I send a repo github under you commentary?)
I think RUclips will flag it as spam if you add a link to your commentary
Volveras al canal de Antonio Sarosi?
Ahora mismo no
Sir, do you have a license for those guns?
They might be illegal ☠️
I felt myself a way worse software engineer after I saw you ...
This is leaning more towards pure Computer Science than software engineering.
El doble de Sarosi?
Sarosi es una IA
Ey there is man named Antonio who does programming videos too, is he your twince?
Nah man he's an AI
Either way, new sub!
Nos olvidaste, toñito:c
Ya he hablado sobre el tema en Instagram y Twitter.
Wouldn't that be unnecessary if you had index on name which could be already sorted on insert and just take first 100 elements from it? This algorithm was invented when hdds were expensive. Today 1gb is cheaper than one minute of your time.
If there's a BTree index and the query sorts by that index only then yes. Otherwise, if there are 100 queries sorting 1GB at the same time you still need an external sort algorithm, and if there's one query sorting 5TB you still need the same algorithm. All databases have some variant implemented.
Amazing work
thank you
You're welcome, thank you for commenting