No. As soon as you need to read more than <cache line bytes>, it no longer matters that that the the fields are near each other. So, e.g., if your record is 128 bytes but your cache line is 32 bytes, you have 4 cache misses per record. If you use only 4 fields from the record, you have 4 cache misses per record -- so, we're on parity.
As M increases beyond the cache line size, the advantage (compared to column major) no longer increases. So it is at most a constant in practice.
> The big thing is that their access patterns are rarely random.
That's true for almost all programs, almost all of the time, actually -- which is why I was willing to be the other side of your original wager.
> They aren't so fast if you need to find a specific entry. For maximum speed there, you need a dedicated index, and then it doesn't really matter whether the data is stored row-major or column-major.
And again, that's true for many workloads as well.
The main advantage of row-major is simpler appending; if you write a lot and read little, row-major is faster; this is usually the case for e.g. audit logs.
In most typical cases, column major is equal or better.
Huh? Why would you have 4 cache misses for a 128-byte record? If you need to access 4 fields and they all fall onto the same cache line, you get only one cache miss. If your fields are spread far apart, you might have 4 cache misses, but that isn't a given. With parallel arrays, the fields will be in separate arrays and necessitate 4 cache misses.
> That's true for almost all programs, almost all of the time, actually -- which is why I was willing to be the other side of your original wager.
I didn't make the original wager. :)
I wrote earlier "if your cache line is 32 bytes".
If you need all the fields - you will have 4 cache misses. If you need only some of the fields, and they all fall into 1 cache line, then -- as you said, you will only have one cache miss.
My point (poorly worded, upon rereading, but I didn't have much time, dayjob and all...) was that the potential advantage of record-major does NOT increase beyond what is packed into one cache line -- so it is a small constant, rather than deserving of O() notation.
> I didn't make the original wager. :)
Ah, apologies. (But maybe you'd still let me take your money? :) )
I see what you mean, now. You're right that it's a constant multiplier.
Sorry, I'm really confused. Is this supposed to be "O(M/L)"?
The note about clumped records is valid. That is often the case. Without knowing more about their workload, it's difficult to say whether they have that behavior, but it's quite likely.
As for the fastest DBs, they use column order for a number of reasons. The big thing is that their access patterns are rarely random. They're optimized for scanning on keys. DBs like Fastbit can be extremely fast for whole-table scans. They aren't so fast if you need to find a specific entry. For maximum speed there, you need a dedicated index, and then it doesn't really matter whether the data is stored row-major or column-major.