4 ms·

> If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet. Anyone actually use this combo (I don't kn

by mamcx 5y ago

> If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet. Anyone actually use this combo (I don't know much about this) that show is good? --- If I were to build a rdbms today, and not for OLAP but OLTP, is this a good combination? I have imagine building my relational language about this stuff, and have wondered if building a paged "columnar" layout could be the best: DeletedBitArray(00100100...) Page1(SizeOfBlock) = col1 = 1, 2, 3, col2 = "hello" "cruel" "world" Page2(SizeOfBlock) = col1 = 1, 2, 3, col2 = "hello" "cruel" "world" So this flip the rows into columns but for a smallish batch. Probably making locks expensive but never have implemented this stuff.

jasonwatkinspdx 5y ago
I don't know about splay trees specifically, but the combination of an in memory index structor and append only log persistence has been a common theme in recent database research. Microsoft's bw-tree, a derivative of which powers CosmosDB is one example (though it uses a lock free hash table instead of a splay tree or similar).
- bob1029 5y ago
  The reason for the splay tree is because of their dynamic programming properties. When combined with an append-only log, you are naturally pushing the most frequently utilized information to the front, and letting older items fall to the back of the log. All you have to do to keep an item alive is to access it using a splay tree. Cleanup is as simple as deciding how many older log segment files to chop. In practical use cases you generally don't even have to worry about potential downsides. The sequential integer insert thing giving you log(N) is so rare. Most live systems are touching tons of items in arbitrary order so the probabilities work themselves out.
  - jasonwatkinspdx 5y ago
    I can see how that'd be very effective for a cache, but I'm not at all seeing how it'd work for a database. You'd need to touch all live data to copy it forward and keep track of the low water mark before you truncate the prefix of the log. That'd have horrific write amplification.
    - bob1029 5y ago
      > You'd need to touch all live data to copy it forward This is already happening as a natural part of the utilization patterns. Just looking at something in a splay tree will cause it to be relocated to the root (the most live part of the log). That is the dynamic part of the data structure. You are doing a huge part of the GC effort simply by reading the database. There are clearly applications where this would not be a good fit (i.e. data warehousing where you want to keep old shit on purpose). Even with the natural cleanup mechanism, you may still need to save stuff you haven't accessed in a while. Linked list nodes built on top being an example of an area that would need careful attention to avoid chopping up data structures unexpectedly. >That'd have horrific write amplification. This is precisely why I recommend batching as part of the approach in my original post above. With batching, you can take a total rewrite of all nodes in a linked list and squeeze them into a single I/O operation that flows into exactly the # of storage blocks required. In implementations without batching, you are talking about block I/O per linked list node that needs updating. Clearly this is a total non-starter for drive lifetime & performance.
atombender 5y ago
That particular page layout is called PAX, I believe [1]. [1] https://www.pdl.cmu.edu/PDL-FTP/Database/pax.pdf https://www.pdl.cmu.edu/PDL-FTP/Database/pax.pdf
- mamcx 5y ago
  Great, I was sure not the first to think like this :)

by mamcx 5y ago

jasonwatkinspdx 5y ago

I don't know about splay trees specifically, but the combination of an in memory index structor and append only log persistence has been a common theme in recent database research. Microsoft's bw-tree, a derivative of which powers CosmosDB is one example (though it uses a lock free hash table instead of a splay tree or similar).

bob1029 5y ago
The reason for the splay tree is because of their dynamic programming properties. When combined with an append-only log, you are naturally pushing the most frequently utilized information to the front, and letting older items fall to the back of the log. All you have to do to keep an item alive is to access it using a splay tree. Cleanup is as simple as deciding how many older log segment files to chop. In practical use cases you generally don't even have to worry about potential downsides. The sequential integer insert thing giving you log(N) is so rare. Most live systems are touching tons of items in arbitrary order so the probabilities work themselves out.
- jasonwatkinspdx 5y ago
  I can see how that'd be very effective for a cache, but I'm not at all seeing how it'd work for a database. You'd need to touch all live data to copy it forward and keep track of the low water mark before you truncate the prefix of the log. That'd have horrific write amplification.
  - bob1029 5y ago
    > You'd need to touch all live data to copy it forward This is already happening as a natural part of the utilization patterns. Just looking at something in a splay tree will cause it to be relocated to the root (the most live part of the log). That is the dynamic part of the data structure. You are doing a huge part of the GC effort simply by reading the database. There are clearly applications where this would not be a good fit (i.e. data warehousing where you want to keep old shit on purpose). Even with the natural cleanup mechanism, you may still need to save stuff you haven't accessed in a while. Linked list nodes built on top being an example of an area that would need careful attention to avoid chopping up data structures unexpectedly. >That'd have horrific write amplification. This is precisely why I recommend batching as part of the approach in my original post above. With batching, you can take a total rewrite of all nodes in a linked list and squeeze them into a single I/O operation that flows into exactly the # of storage blocks required. In implementations without batching, you are talking about block I/O per linked list node that needs updating. Clearly this is a total non-starter for drive lifetime & performance.

atombender 5y ago

That particular page layout is called PAX, I believe [1]. [1] https://www.pdl.cmu.edu/PDL-FTP/Database/pax.pdf https://www.pdl.cmu.edu/PDL-FTP/Database/pax.pdf

mamcx 5y ago
Great, I was sure not the first to think like this :)