6 ms·

This seems interesting but to me there is a flaw near the beginning. They state a btree assumes worst case distribution. That's a feature . Much better than a "

This seems interesting but to me there is a flaw near the beginning. They state a btree assumes worst case distribution. That's a feature . Much better than a "this will be fast, if you're lucky" distribution. But who knows, maybe for read heavy analytical workloads this will be an interesting way of improving performance or reducing space usage.

Donald 9y ago
This is the exact point of view they are rejecting. You want spectacular average-case performance at the cost of a slow but not catastrophic worst-case.
- anonacct37 9y ago
  So basically suitable for batch mode only? There's really no other situation in software where average is a useful measure.
  - willchang 9y ago
    How about searching the web? I'd rather most queries take 1 second, and 10% taking 10 seconds, than every query taking 5 seconds. I don't understand how you can be so confident about attaching a utility function to latency.
  - KirinDave 9y ago
    This is not only wrong for most user-facing cases, but it misses the key notion of training 1-N sub-models, which is a gateway to actually measuring the degree of success or failure in the index building step and modifying it as needed.
  - PeterisP 9y ago
    Well, no, for many user-facing use cases your performance essentially averages out if you have enough users - i.e. for a single user even the worst case performance is faster than they care about, but you're limited by how many concurrent users your hardware can serve. In that case, you want the average to be as low as possible because then you need less hardware for the same throughput, or you can get faster response time for any users once the waiting/delay caused by other users is taken into account. A blocking read operation that predictably takes 10 ms will limit you to 100 requests per second, and with an uneven/bursty distribution many of those requests will be queued for 100ms; A blocking read operation that sometimes takes 50 ms but has 5 ms on average will have almost no queuing in 100 requests per second, so the 50ms will really be the worst case.
- DonbunEf7 9y ago
  And they will be forced to learn, the hard way, that this is a bad way to approach algorithms design. The same argument applies to quicksort, and we know how that turned out: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
  - czardoz 9y ago
    That argument cannot be generalized to every use-case. In fact it's very specific to quick sort. Yes, this approach may not work for a lot of situations, but there are some (as pointed out elsewhere in the comments), where it's perfectly reasonable, even desirable to improve the average runtime at the cost of the worst case.
  - goialoq 9y ago
    That adversarial quicksort only applies under specific constraints (2. Pivot-choosing takes O(1) comparisons; all other comparisons are for partitioning. ) that are easily worked around.
- bunderbunder 9y ago
  Depends on application. They're looking at analytical workloads, which presumably means they're focused on batch jobs. For OLTP-type workloads, I care very much about worst-case performance.
3pt14159 9y ago
Honestly, for this specific use case what I want is for btree to be _much_ better than learned index structures in some cases and _much_ worse in other cases. That way I can run both in parallel and whichever queries back first is the one I go with. My overall performance skyrockets.
KirinDave 9y ago
> Much better than a "this will be fast, if you're lucky" distribution. This is a really wrongheaded way to look at this. BTrees are themselves an adaptive function that can be used at the top of bottom of an index. We've just got other ones here being proposed that are much faster and smaller, when they work. And there is a methodology here to identify and train them, when they do. This exists in sharp contrast to our existing family of algorithms, which tend to lack any sort of introspective features in their operation. Tree building, for example, is (like many divide-and-conquer algorithms that are actually trees) incredibly sensitive to the ordering of the arguments, and algorithms that balance them use only structural information and balance them at the last possible (and often most expensive) moment. What's most amazing about this approach is that you've got a recursive model where the model is trained in layers that propose a submodel, or "an expert which has a better knowledge about certain keys." That model could be a tree, or a b-tree, or a linear regression, or a neural network. They actually test using other tree types and search algorithms (which are implicitly tree types) in the paper. This process adaptively trains models which can, in a very real sense, increase and decrease their level of detail as the structure of the data demands. And in the later case (which seems to excite people less but excites me more) they propose a bloom filter alternative that can automatically identify useful structural elements and latch onto those as part of its categorization, which is is perhaps one of the most revolutionary ideas I've seen bringing ML into the distributed systems world.
- goialoq 9y ago
  B-trees incrementally rebalance on every insert https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree
  - KirinDave 9y ago
    I thought maybe I had made an error in writing or editing that implied that b-trees were not self-balancing. So I reread it twice. Maybe I just don't see where I implied otherwise. That doesn't mean that the amount of computation and memory comparisons done doesn't vary based on the order of the input.
skybrian 9y ago
Databases see order-of-magnitude slowdowns depending whether the query plan uses an index. Operating system caches result in high performance variation for disk I/O. Even CPU's have highly variable performance depending on branch prediction and the size of on-CPU caches. So this is nothing new; other than hard real-time programming, we already live with high performance variation.

Donald 9y ago

This is the exact point of view they are rejecting. You want spectacular average-case performance at the cost of a slow but not catastrophic worst-case.

anonacct37 9y ago
So basically suitable for batch mode only? There's really no other situation in software where average is a useful measure.
- willchang 9y ago
  How about searching the web? I'd rather most queries take 1 second, and 10% taking 10 seconds, than every query taking 5 seconds. I don't understand how you can be so confident about attaching a utility function to latency.
- KirinDave 9y ago
  This is not only wrong for most user-facing cases, but it misses the key notion of training 1-N sub-models, which is a gateway to actually measuring the degree of success or failure in the index building step and modifying it as needed.
- PeterisP 9y ago
  Well, no, for many user-facing use cases your performance essentially averages out if you have enough users - i.e. for a single user even the worst case performance is faster than they care about, but you're limited by how many concurrent users your hardware can serve. In that case, you want the average to be as low as possible because then you need less hardware for the same throughput, or you can get faster response time for any users once the waiting/delay caused by other users is taken into account. A blocking read operation that predictably takes 10 ms will limit you to 100 requests per second, and with an uneven/bursty distribution many of those requests will be queued for 100ms; A blocking read operation that sometimes takes 50 ms but has 5 ms on average will have almost no queuing in 100 requests per second, so the 50ms will really be the worst case.
DonbunEf7 9y ago
And they will be forced to learn, the hard way, that this is a bad way to approach algorithms design. The same argument applies to quicksort, and we know how that turned out: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
- czardoz 9y ago
  That argument cannot be generalized to every use-case. In fact it's very specific to quick sort. Yes, this approach may not work for a lot of situations, but there are some (as pointed out elsewhere in the comments), where it's perfectly reasonable, even desirable to improve the average runtime at the cost of the worst case.
- goialoq 9y ago
  That adversarial quicksort only applies under specific constraints (2. Pivot-choosing takes O(1) comparisons; all other comparisons are for partitioning. ) that are easily worked around.
bunderbunder 9y ago
Depends on application. They're looking at analytical workloads, which presumably means they're focused on batch jobs. For OLTP-type workloads, I care very much about worst-case performance.

3pt14159 9y ago

Honestly, for this specific use case what I want is for btree to be _much_ better than learned index structures in some cases and _much_ worse in other cases. That way I can run both in parallel and whichever queries back first is the one I go with. My overall performance skyrockets.

KirinDave 9y ago

> Much better than a "this will be fast, if you're lucky" distribution. This is a really wrongheaded way to look at this. BTrees are themselves an adaptive function that can be used at the top of bottom of an index. We've just got other ones here being proposed that are much faster and smaller, when they work. And there is a methodology here to identify and train them, when they do. This exists in sharp contrast to our existing family of algorithms, which tend to lack any sort of introspective features in their operation. Tree building, for example, is (like many divide-and-conquer algorithms that are actually trees) incredibly sensitive to the ordering of the arguments, and algorithms that balance them use only structural information and balance them at the last possible (and often most expensive) moment. What's most amazing about this approach is that you've got a recursive model where the model is trained in layers that propose a submodel, or "an expert which has a better knowledge about certain keys." That model could be a tree, or a b-tree, or a linear regression, or a neural network. They actually test using other tree types and search algorithms (which are implicitly tree types) in the paper. This process adaptively trains models which can, in a very real sense, increase and decrease their level of detail as the structure of the data demands. And in the later case (which seems to excite people less but excites me more) they propose a bloom filter alternative that can automatically identify useful structural elements and latch onto those as part of its categorization, which is is perhaps one of the most revolutionary ideas I've seen bringing ML into the distributed systems world.

goialoq 9y ago
B-trees incrementally rebalance on every insert https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree
- KirinDave 9y ago
  I thought maybe I had made an error in writing or editing that implied that b-trees were not self-balancing. So I reread it twice. Maybe I just don't see where I implied otherwise. That doesn't mean that the amount of computation and memory comparisons done doesn't vary based on the order of the input.

skybrian 9y ago

Databases see order-of-magnitude slowdowns depending whether the query plan uses an index. Operating system caches result in high performance variation for disk I/O. Even CPU's have highly variable performance depending on branch prediction and the size of on-CPU caches. So this is nothing new; other than hard real-time programming, we already live with high performance variation.