4 ms·

The BOOM guys have also shown that thinking in terms of unordered collections translates much better to distributed systems, where guaranteeing order is expensi

by jamii 13y ago

The BOOM guys have also shown that thinking in terms of unordered collections translates much better to distributed systems, where guaranteeing order is expensive: http://boom.cs.berkeley.edu/ http://boom.cs.berkeley.edu/

gtani 13y ago
The other day i thought i had found a textbook chapter on stream algo's/online learning, but Chapter 17 has yet to be written http://ciml.info/ http://ciml.info/
stass 13y ago
BOOM project came up with a very impressive ideas. Their half page long paxos implementation in Overlog blew my mind. I don't think they new Bloom language is as expressive, however.
beagle3 13y ago
I'm going to read about BOOM later, but can you give an executive summary about why that is? People who subscribe to the Relational Database dogma often claim that sets are superior to vectors, and yet despite asking a lot of them I never received an example -- whereas I have numerous real life examples in which vectors are superior.
- jacques_chester 13y ago
  The main thing is that order isn't always necessary, but maintaining order isn't free. So if it isn't necessary, why pay the cost? Moreover, the order you want will change from case to case. Today I care about the alphabetical order of names, tomorrow about the order of dates, next week I am most interested in the top 100 transactions by value. Imposing a single order imposes an access pattern which may or may not hold true. With sets I delay that binding until the last possible moment, when I understand it best of all.
  - beagle3 13y ago
    > The main thing is that order isn't always necessary, but maintaining order isn't free. > So if it isn't necessary, why pay the cost? But if you use the APL/K approach, you don't pay the cost. There is in order to every result, but you can only rely on it if you know it (or force it, by some sort). Specifically, my question is this: The order of results of "select ... where" without an order-by clause in SQL is never guaranteed. The order of a ksql/q result is sometimes guaranteed, and can be used. Where's the cost of just giving every result row a running index, which some operations can rely on / change, and most ignore?
    - jacques_chester 13y ago
      That the order isn't guaranteed is a feature, not a bug. It frees the implementation to collect records in the most efficient fashion and from having to maintain ordering. > Where's the cost of just giving every result row a running index, which some operations can rely on / change, and most ignore? The cost is that you need to keep an index updated. A trite observation, but there it is. Sometimes that cost is worth paying, sometimes it isn't. SQL doesn't forcefully extract that cost, it lets the database programmer or administrator decide, based on local conditions, what is best.
      - beagle3 13y ago
        > That the order isn't guaranteed is a feature, not a bug. It frees the implementation to collect records in the most efficient fashion and from having to maintain ordering. Yes, I understand the theoretical argument. I'm looking for real world examples where that actually helps anything, or theoretical examples where it is superior (in the sense that "there is no way to assign order which would not move the problem to a higher complexity class"). > The cost is that you need to keep an index updated. A trite observation, but there it is. Sometimes that cost is worth paying, sometimes it isn't. SQL doesn't forcefully extract that cost, it lets the database programmer or administrator decide, based on local conditions, what is best. My point is that ksql does the same -- except that in most cases, the cost is 0, so you get the order "for free"; when the cost is not zero, ksql doesn't make guarantees, and you'll need to ask for ordering, just like in sql. Every sql engine already assigns order in one way or another (ROWID, etc.), except it is unpredictable, non-standardized, and doesn't provide most of the benefits even though it is there. And the "no order" default often does have a cost; e.g., if you are trying to store e.g. tax brackets in your database and find out which tax bracket a salary falls into: Either you store both lower and upper bound of bracket in a record, which means you can't normalize (and it is hard to express the integrity requirement of "no gaps" as a constraint) - or you do normalize, and then every query is a self join or correlated query that many optimizers won't handle properly. Whereas in ksql, you store it normalized (just start-of-bracket), order by start-of-bracket, and then get the bin that corresponds to your question.

by jamii 13y ago

gtani 13y ago

The other day i thought i had found a textbook chapter on stream algo's/online learning, but Chapter 17 has yet to be written http://ciml.info/ http://ciml.info/

stass 13y ago

BOOM project came up with a very impressive ideas. Their half page long paxos implementation in Overlog blew my mind. I don't think they new Bloom language is as expressive, however.

beagle3 13y ago

I'm going to read about BOOM later, but can you give an executive summary about why that is? People who subscribe to the Relational Database dogma often claim that sets are superior to vectors, and yet despite asking a lot of them I never received an example -- whereas I have numerous real life examples in which vectors are superior.

jacques_chester 13y ago
The main thing is that order isn't always necessary, but maintaining order isn't free. So if it isn't necessary, why pay the cost? Moreover, the order you want will change from case to case. Today I care about the alphabetical order of names, tomorrow about the order of dates, next week I am most interested in the top 100 transactions by value. Imposing a single order imposes an access pattern which may or may not hold true. With sets I delay that binding until the last possible moment, when I understand it best of all.
- beagle3 13y ago
  > The main thing is that order isn't always necessary, but maintaining order isn't free. > So if it isn't necessary, why pay the cost? But if you use the APL/K approach, you don't pay the cost. There is in order to every result, but you can only rely on it if you know it (or force it, by some sort). Specifically, my question is this: The order of results of "select ... where" without an order-by clause in SQL is never guaranteed. The order of a ksql/q result is sometimes guaranteed, and can be used. Where's the cost of just giving every result row a running index, which some operations can rely on / change, and most ignore?
  - jacques_chester 13y ago
    That the order isn't guaranteed is a feature, not a bug. It frees the implementation to collect records in the most efficient fashion and from having to maintain ordering. > Where's the cost of just giving every result row a running index, which some operations can rely on / change, and most ignore? The cost is that you need to keep an index updated. A trite observation, but there it is. Sometimes that cost is worth paying, sometimes it isn't. SQL doesn't forcefully extract that cost, it lets the database programmer or administrator decide, based on local conditions, what is best.
    - beagle3 13y ago
      > That the order isn't guaranteed is a feature, not a bug. It frees the implementation to collect records in the most efficient fashion and from having to maintain ordering. Yes, I understand the theoretical argument. I'm looking for real world examples where that actually helps anything, or theoretical examples where it is superior (in the sense that "there is no way to assign order which would not move the problem to a higher complexity class"). > The cost is that you need to keep an index updated. A trite observation, but there it is. Sometimes that cost is worth paying, sometimes it isn't. SQL doesn't forcefully extract that cost, it lets the database programmer or administrator decide, based on local conditions, what is best. My point is that ksql does the same -- except that in most cases, the cost is 0, so you get the order "for free"; when the cost is not zero, ksql doesn't make guarantees, and you'll need to ask for ordering, just like in sql. Every sql engine already assigns order in one way or another (ROWID, etc.), except it is unpredictable, non-standardized, and doesn't provide most of the benefits even though it is there. And the "no order" default often does have a cost; e.g., if you are trying to store e.g. tax brackets in your database and find out which tax bracket a salary falls into: Either you store both lower and upper bound of bracket in a record, which means you can't normalize (and it is hard to express the integrity requirement of "no gaps" as a constraint) - or you do normalize, and then every query is a self join or correlated query that many optimizers won't handle properly. Whereas in ksql, you store it normalized (just start-of-bracket), order by start-of-bracket, and then get the bin that corresponds to your question.