4 ms·
I believe it's more due to the fact that sorting, and less/greater than operators come up way more often in databases and using an ordered index makes a much be
by halayli 7y ago
I believe it's more due to the fact that sorting, and less/greater than operators come up way more often in databases and using an ordered index makes a much better use case.
And the other reason is MVCC. It's easy to maintain multiple snapshots of a b-tree index and swap a root's ptr to point to a new sub-tree.
- grogers 7y agoAFAIK only LMDB implements MVCC with immutable pages and path copying. Everybody else uses multiple rows distinguished by transaction ID. This works perfectly fine with btrees or hash indexes.
- senderista 7y agoSorting in a database makes sense even when you never use ORDER BY. You can do streaming joins/unions, and implement streaming, non-blocking aggregation operators (because you know when you've seen the last row for a grouping key, so you can output the result for that group immediately and evict its state from memory). Query plans will sometimes sort inputs (or intermediate results) for these reasons even when the final output is unordered; this is known as "interesting orders".
- halayli 7y agocorrect. There are many parts of the db planner that checks if the output is sorted to take a more optimal path.