Sort vs Hash A Duality
summary
Claim: OLTP gets single-digit‑ms performance on seven‑join queries by using nested loop + B‑tree index lookups that are effectively independent of dataset size. Implementations: Postgres 9.6/10 adds parallel/hash improvements and Robin Hood hashing; proposed parallel hash join. Behavior: hash join builds an in‑memory hash on the smaller side, then probes, and shows a stair‑step cost when memory is constrained; external sorts and SIMD‑friendly merge strategies degrade more smoothly and may regain advantage as memory bandwidth per core stalls.
AI-written summary · about
chapters (11)
- 0:00Start
- 3:53Nested Loop Joints
- 6:16Example Using Sql
- 14:06Merge Joins
- 15:02Example of a Merge Join
- 22:31Hash Joins
- 27:15Memory Capacity
- 29:36Quicksort for External Support Operations
- 40:20Bandwidth Oblivious Sort
- 42:03Instruction Level Parallelism Simdi
- 44:17Sort Benchmark
related talks
26mBeyond Joins and Indexes
48mTricks from in-memory databases
37mRules of Indexing in PostgreSQL
29mExplaining the Postgres Query Optimizer
50mPerformance Improvements of Partitioning: Past and Future
41mParallel and distributed big joins in H2O
50mImproving Postgres' Efficiency
37mRules of Indexing in PostgreSQL