#database
3.6 External-Memory and Database Structures
3.6 External-memory and database structures, 35 index slug name 1 external-memory-structure External Memory Structure 2 block-model Block Model 3 buffer-pool Buffer Pool 4 page-cache Page Cache 5 slotted-page Slotted Page 6 heap-file Heap File 7 sorted-file Sorted File 8 clustered-index Clustered Index 9 secondary-index Secondary Index 10 b-tree-index B Tree Index 11 b-plus-tree-index B Plus Tree Index 12 lsm-tree LSM Tree 13 memtable Memtable 14 sstable SSTable 15 bloom-filter-index Bloom...
TPMMS
Two Phase Multiway Merge Sort Two Phase Multiway Merge Sort (TPMMS) is a practical external sorting algorithm used in database systems. It assumes that all sorted runs can be merged in a single pass using available memory buffers. The method minimizes the number of disk passes, which dominates cost in external memory settings. Model Let: $N$ = total number of elements $M$ = memory capacity $B$ = block size Memory...
Sort Merge Join Sort Phase
Sort Merge Join Sort Phase The sort phase of sort-merge join orders each input relation by the join key before the merge phase begins. If an input is already ordered by a suitable index or previous query operator, the database can skip sorting that input. This phase is important because the merge join itself requires ordered streams. Without sorted inputs, the join cannot advance both sides efficiently. Problem Given two...
Spill Sort
Spill Sort Spill sort is a practical external sorting pattern used when an operator begins as an in-memory sort but exceeds its memory budget. When memory fills, the current data is sorted and spilled to temporary storage as a run. After all input has been read, the spilled runs are merged. This is common in databases, query engines, log processors, and stream processors. Problem Given an input stream and a...
Database External Sort
Database External Sort Database external sort is the disk-based sorting procedure used inside relational database query engines. It appears in query plans for operations such as ORDER BY , GROUP BY , DISTINCT , window functions, and sort-merge joins. The method is usually a variant of external merge sort with database-specific concerns: rows, tuple comparison, memory quotas, spill files, collation rules, NULL ordering, and stable execution under limited working memory....