The ORDER BY Algorithm Is Harder Than You Think

Подписаться 19 тыс.

Просмотров 50 тыс.

50% 1

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

Наука

Опубликовано:

9 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 178

@paulstelian97 13 дней назад

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!

@tony_saro 13 дней назад

Maybe it can, I didn't implement it myself though.

@treelibrarian7618 11 дней назад

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.

@tony_saro 11 дней назад

@@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.

@paulstelian97 11 дней назад

@@tony_saro Even variable length has a maximum length, so you can conservatively estimate the maximum for that.

@tony_saro 11 дней назад

@@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.

@eduardoandrescastilloperer4810 14 дней назад

Something so simple ended up being so complex and you didn’t even talk about distributed DBs. Top notch

@ArkenGAMES 3 дня назад

Yeah how would that look like?

@eduardoandrescastilloperer4810 2 дня назад

@@ArkenGAMES imagine this but on like 10 or 20 servers and with backups and caching

@nirshadnijam2291 29 дней назад

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

@tony_saro 29 дней назад

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.

@ra2enjoyer708 10 дней назад

@@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.

@TreeLuvBurdpu 13 дней назад

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.

@tony_saro 13 дней назад

True, BTree indexes will skip this algorithm altogether.

@editxswajal 19 дней назад

This is what for I pay my internet bills. Btw great work and explained well

@tony_saro 19 дней назад

Thank you

@dearozero3631 3 дня назад

One of the coolest low level CS videos I've seen in a long time. The animation quality is amazing.

@neiliusflavius 7 дней назад

I remember my dad describing this algorithm to me - except he was doing it on an old mainframe where each of the temporary files were on tapes that needed manually changed between passes!

@ciberman 18 дней назад

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!

@ra2enjoyer708 10 дней назад

This video is pretty good at picturing file operations as something that just works and not a clusterfuck at all.

@tony_saro 10 дней назад

It just works but it's not easy to implement at all 😂

@alfredovr9111 19 дней назад

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

@Andre-kh3fl 14 дней назад

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!

@tony_saro 14 дней назад

I will at some point, now I'll focus on smaller projects because the database drained all my energy 😂

@cryptopatrick 16 дней назад

Damn! This guy is next level - insane quality. Bravo!

@levipalait683 14 дней назад

Very good explanation and amazing animations! Please keep up the content!

@sunkittsui7957 14 дней назад

Very intuitive and concise explanation!

@vinicius707 29 дней назад

This is some great content, man! I really appreciate the effort that you put into it and for making it available for free on RU-vid. Thanks!

@tony_saro 29 дней назад

Thanks man

@loocheenah 16 дней назад

This channel is lit, man, instant sub 🎉

@Israel220500 15 дней назад

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.

@ashwdq 19 дней назад

Que buen videoo!! Muchisima suerte y ánimo con este canal! Tienes muchísimo potencial para crecer. No te rindas y muchísimo ánimo❤❤

@urbaniv 16 дней назад

Awesome. Great work

@ViniciusVieira13 18 дней назад

Great presentation and explanation on this topic. I've happily subscribed

@m-alghobary 20 дней назад

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 🙏🏻

@tony_saro 20 дней назад

I will, thanks for the sub and like 👍

@Glovali 18 дней назад

Very well explained. I look forward to more videos!

@tony_saro 18 дней назад

Working on it 👨‍💻

@carylandholt 12 дней назад

Outstanding job! So well presented and extremely clear.

@gu1581 20 дней назад

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

@tony_saro 20 дней назад

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.

@TapetBart 14 дней назад

You do joins in the application instead of on the database???? Why???

@gu1581 14 дней назад

@@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

@TapetBart 14 дней назад

@@gu1581 ah, makes perfect sense then. I am doing something a bit similar with DuckDB.

@elraito 10 дней назад

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.

@tony_saro 10 дней назад

Working on it 📈

@adokana_ 18 дней назад

Buen vídeo, me alegro de volver a verte

@eric-seastrand 13 дней назад

Fascinating! Subscribed.

12 дней назад

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!

@amj864 12 дней назад

Just subed, love the video hopefully, you do many many more and gain a yuuugggee fan base

@lampham7874 15 дней назад

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 💪

@sidreddy7030 3 дня назад

This is so beautiful. Loved it

@Mariomm_marti 13 дней назад

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!

@66ussa77 19 дней назад

Excelente como siempre 💯💪

@robertchang-me 17 дней назад

Really good content, like it

@BrunoAlmeidaSilveira 7 дней назад

The animations are cool, and your explanation is right and on point. Really enjoyed your content 👏

@alexanderzikal7244 9 дней назад

Thank You again! A really interesting problem with different sizes.

@mayfly0 11 дней назад

wow such a clear explanation 👍👍

@josueC235 11 дней назад

No hay cosa más hermosa que ver tu contenido en inglés tambien 🥹🫶 Amo enserió tu contenido brou ❤

@ChrisHalden007 5 дней назад

Great video. Thanks

@user-ju7co9md1q 14 дней назад

El rey a vuelto, ahora sí hay un buen motivo para aprender inglés.

@borislavrangelov4770 16 дней назад

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.

@tony_saro 16 дней назад

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 😂.

@borislavrangelov4770 16 дней назад

@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 😁

@s8x. 16 часов назад

this video is top quality. such valuable information here explained so well

@facundopuerto4415 9 дней назад

Muy buenos tus videos. Las animaciones hacen que sea mucho más fácil de entender. Saludos!

@consciousmi4842 20 дней назад

Wow, this was very well explained. Thanks for posting. Can we have more videos plz. Thank you again

@tony_saro 20 дней назад

Sure, I'm working on a video similar to this one focused on algorithms and then I'll start working on another #mkown episode

@AqoCyrale 16 дней назад

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?

@tony_saro 16 дней назад

Both, next video will be similar to this one and then I'll move to another project

@AqoCyrale 16 дней назад

@@tony_saro awesome, looking forward to it. thanks a lot!

@starc0w 2 дня назад

Very good!

@victormadu1635 9 дней назад

Please keep up the good job

@brayancortes7333 11 дней назад

Gran explicación, sigue asi, ademas me ayudas a mejorar mi ingles, un saludo desde Colombia

@_CJ_ 4 дня назад

So for this you would use things like RAM drive or buy Optane and it become much easier with modern SSD I would guess. I never thought that database use files and hard disk to sort stuff. Thank you for this lesson! Very cool animations, easy to follow and I like that you really implemented it and not just read some documentation! 💛Huge respect. It may be just basic and naive implementation but that is the best place to start with such complex thing. Looking forward to next video! :) Cheers

@genins21 10 дней назад

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

@tony_saro 10 дней назад

Check the pinned comment

@sebamarin12 14 дней назад

You have explained it in such a way that I have understood it even though I am an HTML programmer.

@yunlin-us8so День назад

great explain and introduce

@edwolt 5 дней назад

The page size can be the size the disk read at once (if you try to read a byte, disk will read more than a byte), or the size OS read at once (if I am not mistake, OS also read more to optimize IO)

@tony_saro 5 дней назад

It's at least equal to the file system page size. Otherwise it's a multiple of the FS page size.

@alejandroklever 15 дней назад

Another great video. I would really like to see the code of this.

@tony_saro 15 дней назад

It's on GitHub, linked in the description.

@atackhelikopter4303 5 дней назад

if you have a limit on the number of results, so you have to show the first k rows sorted in a particular way (so basically the first k rows in an ordered data set), it's better if you made k pages of size(maximum size of a row) and just select the first k rows to be in pages and keep going thru the list till you found the first k this way your algorithm has a complexity of O(n * logk), assuming that you can hold in memory the k pages, and you would use a priority_queue to handle the data, than you can sort it in O(k logk) but that is smaller than O(n logk), whilst that order by algorithm has O(n * logn * log base k (n)) where n is the number of rows in the database also you can get the rows a-b that would be in a data base if it were sorted, you can do the same thing, except you take the k as being b, with the same algorithm and limitation

@tony_saro 5 дней назад

We've already discussed the "LIMIT" thing in the pinned comment. Add your comment there if you want to contribute further to that conversation.

@macgyverswissarmykni 14 дней назад

Nice seeing someone else writing Rust code

@SurfingOnTheGuitar 12 дней назад

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 ?

@tony_saro 12 дней назад

Separate file unless the results fit in memory

@angelffg 11 дней назад

Great!

@ChrinovicMukanya 18 дней назад

I found my new role model

@LokendraSingh-42 11 дней назад

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

@user-yi6sb8qo1j 12 дней назад

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

@tony_saro 12 дней назад

It's similar to bottom up you can represent the passes as a tree

@sebastianfranco1507 4 дня назад

You could make a kind of hash for the variable data that keeps the order that way you only need to compare the actual variable size data if the hash is equal, you just have to not multiple the hash by a prime number

@tony_saro 4 дня назад

You know any algorithm that preserves order and doesn't cause collisions? When two hashes are equal how do you know if the original variable data, for example strings, were equal or they just produced the same hash value?

@nazarshvets7501 3 дня назад

Great explanation, great video 🔥 One thing I missed tho, how do we choose K?

@tony_saro 3 дня назад

Depends on how much memory you have and how big the page size ends up being. I didn't implement any algorithm that analyzes the current memory consumption to determine K, I just added a default constant value of 4 😂.

@retenim28 14 часов назад

impressive animation and knowledge. i don't think there's something similar on youtube about Database, congrats. May you suggest some resources (especially books) about DB? I don't want to be an expert, but i want only have a basic-medium knowledge about what's happening under the hood when I interact with DB. Right now, I am following a course by Andy Pavlo here on RU-vid (i don't think it's possibile to paste the link, but it's well known) which looks amazing , but some written resources are appreciated too

@tony_saro 10 часов назад

I did not read any books. The resources I used are linked in the full database video and also in the GitHub repository.

@cdavidd 7 дней назад

eso es contenido del bueno, eres el mejor crack, si se te ocurre hacer estos mismos videos en español , asi sean de paga, por aqui tiene un cliente! 😎

@tony_saro 7 дней назад

Estos videos son gratis, los hago en inglés porque tienen más público que en español.

@cdavidd 5 дней назад

@@tony_saro esque aun no domino bien en ingles maestro 😅

@SlackwareNVM День назад

Would it make sense to not keep track of the whole tuple but just the id and the columns used to perform the ordering? That would decrease the size of the data that needs to be transferred and make things potentially faster, but at the cost of having to do another lookup using this new "index" to satisfy the original select statement.

@tony_saro День назад

That's the problem, if you sort just the row IDs when you do the final lookup using the new "index" you'll have to do a bunch or random IO. Random is slow, you have to do Sequential IO.

@SlackwareNVM День назад

@@tony_saro Yeah, I've no idea how they compare in speed. Since you know the tuple size from the schema (at least a minimum), and you know how many rows you're sorting, perhaps some cut off point can be calculated (given some approximate constant for random IO cost) where you can switch between implementations.

@SlackwareNVM День назад

@@tony_saro I did afterwards read the thread in the pinned comment and saw you guys already discussed the topic. Thank you for the easy to follow explanations and for doing some additional passes of the algorithm to make it extra clear.

@sunkittsui7957 14 дней назад

Are there any other external sorting algorithms like this?

@tony_saro 14 дней назад

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.

@ProxyDev 18 дней назад

Amazing work

@valcubeto 9 дней назад

Perfectamente explicado, y eso que no se me da muy bien el inglés

@cat-.- 3 дня назад

What if I’m ORDERing BY a col that is b-tree indexed? I assume the db wouldn’t need to sort, because it’s already sorted?

@tony_saro 3 дня назад

If that's the only column you sort by then yes, it's already sorted.

@Ashley-sd5xn День назад

Did you happen to look into how any open source databases solve the problem with mixed page sizes? I wonder if they did it the same way as you or not.

@tony_saro День назад

Looked into Postgres but I didn't fully figured out how it works. Their implementation is much more complex than mine obviously. I also looked into SQLite 3 and they use PMA (Packed Memory Array) which a data structure basically designed to deal with this problem, but it seemed to be more complicated to implement than external sorting.

@poutineausyropderable7108 2 дня назад

I feel like if you are just sorting hy something, you can just argsort said thing and then shuffle following that. It skips the problem of changing size.

@tony_saro 2 дня назад

Sorting on disk isn't as easy, you have to avoid random IO.

@jaime7295 29 дней назад

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

@tony_saro 29 дней назад

Justo, por eso me he cambiado a la inglesa porque esto es lo que me interesa a mí.

@zeusjean 20 дней назад

@@tony_saro

@danields_04 15 дней назад

Mucho ánimo con este nuevo canal.

@cn-ml 2 дня назад

How does this work in combination with pagination queries like ORDER BY ... LIMIT ... OFFSET? Is there any way to optimize this without having to order the entire table every time?

@tony_saro 2 дня назад

We've talked about the LIMIT in the pinned comment, check it out. The OFFSET I'm not sure you can optimize that, it's similar to a limit so maybe you can.

@user-ur4ev7vl6c 9 дней назад

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?)

@tony_saro 9 дней назад

I think RU-vid will flag it as spam if you add a link to your commentary

@kesocialuwu 6 дней назад

No sabia que tenias un canal en inglés 😮

@tony_saro 6 дней назад

Lo sabes ahora jaja

@JonBrase 8 дней назад

Why do databases tend to do their own swapping to temporary files for tables that don't fit in RAM rather than just doing everything in-memory (with a cache-friendly algorithm) and letting the OS's paging facilities handle swapping to disk. Process memory can already be much larger than RAM (with appropriate swap space configured).

@tony_saro 8 дней назад

Because the replacement algorithm is determined by the OS in that case. Databases don't have control over that, and the OS doesn't know anything about databases so they just roll their own optimized algorithms.

@victorramos3110 14 дней назад

Cómo te volviste tan fluido en inglés? Llevo años con el inglés y no soy ni la mitad de fluido...

@tony_saro 14 дней назад

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 😂.

@NathanaelNewton 7 дней назад

I feel like this could take a while 😂

@iajaydandge 7 дней назад

Just wanted to thank you for this. In near future, if you have time will you implement redis from scratch with master replica command propagation.

@tony_saro 7 дней назад

I don't know, I won't touch databases any time soon after this project.

@iajaydandge 7 дней назад

@@tony_saro Well it Iooks like I need to wait

@user-fj9hf4bu9f 3 дня назад

did you really need to have built a DB to realize you can't assume some arbitrary piece of data may not necessarily fit into memory (ram) ?

@tony_saro 3 дня назад

Yes, I have a negative IQ.

@diegoparra8859 18 дней назад

Volveras al canal de Antonio Sarosi?

@tony_saro 18 дней назад

Ahora mismo no

@edwinroman30 18 дней назад

Ey there is man named Antonio who does programming videos too, is he your twince?

@tony_saro 18 дней назад

Nah man he's an AI

@edwinroman30 18 дней назад

Either way, new sub!

@MrC0MPUT3R 15 дней назад

Sir, do you have a license for those guns?

@tony_saro 15 дней назад

They might be illegal ☠️

@rayilisto 9 дней назад

Nos olvidaste, toñito:c

@tony_saro 9 дней назад

Ya he hablado sobre el tema en Instagram y Twitter.

@lazarus6983 4 дня назад

I think you didnt really explain something well because im confused...... You say you need to implement k way merge sort with paging because you cant assume the tuple set fits in memory But based on your explanation, the buffer seems to double each time as the pages are merged, presumably until the # of pages inside the buffer = the number of records / page size.... . Meaning in the kast pass, you will have the final output buffer size (in memory) = the entire result set? Now toure back at the original problem you had at the beginning of the video. That is, for the bulk of the algorithm you are space efficient but in the last oass, the final output buffer will have the entire resultset in memory before writing it to the final output file ..... How do you get around this issue? Are you writing to the disk as you are merging basically?

@tony_saro 4 дня назад

Look at 04:43. Pages you see at the bottom are on disk and the ones you see at the top are in memory. I think it's pretty clear what's in memory and what isn't. You only load as many pages as input buffers you have, that's it, last pass included. The memory buffers never change their size, and in the last pass you can see with the animations that it's still loading 2 pages at a time.

@XMaverick20 6 дней назад

Virtual memory?

@user-ey5xw2nx9s 6 дней назад

Nah, because too dependent on OS

@julionavarro2600 14 дней назад

El doble de Sarosi?

@tony_saro 14 дней назад

Sarosi es una IA

@baranacikgoz 13 дней назад

I felt myself a way worse software engineer after I saw you ...

@tony_saro 13 дней назад

This is leaning more towards pure Computer Science than software engineering.

@user-ey5xw2nx9s 6 дней назад

What so you mean?

@adriankal 17 дней назад

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.

@tony_saro 17 дней назад

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.