3 ms·

It actually may be an order as you suggest -- the difference gets bigger as the tree gets bigger. I just stopped benchmarking at about 300MB of data where the p

by rusbus 9y ago

It actually may be an order as you suggest -- the difference gets bigger as the tree gets bigger. I just stopped benchmarking at about 300MB of data where the perf was almost 2x. If you run it on a 1GB tree it might be 4x

joe_the_user 9y ago
Sure, maybe. The problem is that doesn't seem enough to necessarily compensate for the added complexity. The thing is a self-balancing binary tree is so much faster than the alternatives for large chunks of data that you really have to use it. Here, I'm not so sure. Anyway, thinking about this lead me to this discussion about fractal trees and LSM trees. https://www.quora.com/What-are-the-major-differences-between-LSM-trees-used-in-BigTable-etc-and-Fractal-Trees-used-in-TokuDB?share=1 https://www.quora.com/What-are-the-major-differences-between... Another question here is how will this play out if the high-performance DB is going to be moving to a GPU where cache levels and scans would be quite different.
- dspillett 9y ago
  > Sure, maybe. The problem is that doesn't seem enough to necessarily compensate for the added complexity. A 50% improvement could be massively significant if processing a huge data-set on thousands of nodes and it is still taking days/weeks/more of wall-clock time. Given the choice between waiting longer, buying more computer power, or using a more complex algorithm, the best of those choices will depend a lot on the circumstances of the project. If it is a one-off then waiting or paying for power will likely win out. Of course in some circumstances paying for more power won't help: you can only get so much out of each node and for some processes factors like interconnect throughput & latency might eat into the ROI significantly as the number of nodes grow. In some cases a 10% or less boost might be worth the extra complexity. And if the algorithm can be generalised and packages as a library, you aren't actually having to deal with that complexity each time the method is useful.

by rusbus 9y ago

joe_the_user 9y ago

Sure, maybe. The problem is that doesn't seem enough to necessarily compensate for the added complexity. The thing is a self-balancing binary tree is so much faster than the alternatives for large chunks of data that you really have to use it. Here, I'm not so sure. Anyway, thinking about this lead me to this discussion about fractal trees and LSM trees. https://www.quora.com/What-are-the-major-differences-between-LSM-trees-used-in-BigTable-etc-and-Fractal-Trees-used-in-TokuDB?share=1 https://www.quora.com/What-are-the-major-differences-between... Another question here is how will this play out if the high-performance DB is going to be moving to a GPU where cache levels and scans would be quite different.

dspillett 9y ago
> Sure, maybe. The problem is that doesn't seem enough to necessarily compensate for the added complexity. A 50% improvement could be massively significant if processing a huge data-set on thousands of nodes and it is still taking days/weeks/more of wall-clock time. Given the choice between waiting longer, buying more computer power, or using a more complex algorithm, the best of those choices will depend a lot on the circumstances of the project. If it is a one-off then waiting or paying for power will likely win out. Of course in some circumstances paying for more power won't help: you can only get so much out of each node and for some processes factors like interconnect throughput & latency might eat into the ROI significantly as the number of nodes grow. In some cases a 10% or less boost might be worth the extra complexity. And if the algorithm can be generalised and packages as a library, you aren't actually having to deal with that complexity each time the method is useful.