points by senderista 3 days ago | 0 comments
Postgres folks will need to correct me but I believe the append-only MVCC design originated from the original "time-travel" requirement (which IIRC was soon dropped). There are better approaches to time-travel anyway such as time-split B-trees (https://www.microsoft.com/en-us/research/wp-content/uploads/...).
[–] mike_hearn 3 days ago
[–] senderista 2 days ago
The time-split B-tree is designed to make time-travel queries efficient in both time and space. That is not a trivial problem.
I don’t know if Flashback uses this technique, but the SQL Server architect who taught me time-split B-trees now works at Oracle :)
[–] mike_hearn 2 days ago
Hah, interesting. I need to investigate that data structure. I don't know if Flashback uses it either - if you enable the time travel feature then undo logs are processed into internal tables partitioned by SCN, but I suppose it's possible those tables are stored in a different way to regular heap-organized or index-organized tables.
[–] senderista 1 day ago
The nodes in a time-split B-tree tile the 2-D time/primary-key space in an arbitrary way except they must cover it fully with no overlaps (think of each node as an arbitrary rectangle with primary key as one axis and time as the other). That gives you a lot of freedom in how you partition the space, allowing you to exploit local sparsity in either the time distribution or the primary key distribution.
[–] mike_hearn 22 hours ago
Thanks, that's interesting!
[–] xyzzy_plugh 3 days ago
Yes and that would make sense, and what I would expect, if it were available. I understand it is load-bearing but it is nonetheless surprising that it hasn't been revisited. It is surprising, at least to me, that time-travel never shipped given its feasibility.
The simplest form of Flashback just uses the undo logs. Normally undo is deleted once no live transaction uses it, but you can set a retention time to allow SELECT ... AS OF ... queries to go back at least that far.
However, keeping undo logs around forever isn't practical. If you want to go back a year then there's Flashback Time Travel which copies old data into tables in a form that the query engine can use to answer AS OF queries more efficiently.