News for hackers. Stuff that matters.
Re:Introducing Druid: Real-Time Analytics at a Billion Rows ... by stavros on Sunday May 01, 2011 @05:35AM (#2502753)
The difference is that you're scanning, they're aggregating. Scanning is O(logn), aggregating is O(n).
Re:Introducing Druid: Real-Time Analytics at a Billion Rows ... by barrkel on Sunday May 01, 2011 @07:34AM (#2502894)
It depends on the commutitvity and associativity of your aggregation operator. With sufficient parallelism, aggregation may also be logarithmic.
Re:Introducing Druid: Real-Time Analytics at a Billion Rows ... by StavrosK on Sunday May 01, 2011 @07:36AM (#2502897)
Are you saying you can somehow sum numbers without reading all of them?
Re:Introducing Druid: Real-Time Analytics at a Billion Rows ... by barrkel on Sunday May 01, 2011 @11:08AM (#2503132)
I'm saying that in terms of real time, if you have enough parallelism, you don't have to wait for n units, but rather log n units. As a function of CPU time, sure it's linear, but ignoring what parallelism gives you is just not being realistic, IMHO.

As to the sibling comment, that's another good point. You say it's because it knows about the queries ahead of time, but you don't get excellent real-world performance without what an academic might consider cheating. Special-case your data structures to expected queries, where those queries are either empirically discovered and adjusted for manually, or learned automatically over time. A closed-minded approach that simply shuts down creative thinking by parroting out "linear time, no can do better, sorry" is poor form.

Re:Introducing Druid: Real-Time Analytics at a Billion Rows ... by StavrosK on Sunday May 01, 2011 @12:13PM (#2503251)
This doesn't change the fact that searching is at least as fast as aggregating, no matter how much you cheat. Besides, how is precomputing relevant to the discussion here? By that reasoning, I can convert any algorithm to O(1) time and O(1) space.

The topic is about how search was faster than aggregation, and I'm saying that searching is faster than aggregation generally. You can parallelize all you want, it's still going to be faster to search than to aggregate.

Re:Introducing Druid: Real-Time Analytics at a Billion Rows ... by jchrisa on Sunday May 01, 2011 @10:28AM (#2503057)
CouchDB does this. It stores precomputed sub-aggregates in the inner-nodes of its B-Tree, so that at query time, it is only summing a handful of numbers instead of all of them.
Re:Introducing Druid: Real-Time Analytics at a Billion Rows ... by StavrosK on Sunday May 01, 2011 @10:52AM (#2503100)
It can do this because the queries are known in advance, though...