You've got most of the ones I'm familiar with there, barring arguably the SAS data set. Albeit that one is "row based", in terms of storage, like the database tables of yore, albeit the application of formats/types is done intellectually on a columnar level.
The main thing I know of is that R's data.table package has the concept of indices on columns like SQL. R doesn't have that.
I don't know if any of the others like Pandas, Arrow, or dplyr have it.
I just Googled and found this article and a very old gist:
http://appsilondatascience.com/blog/rstats/2017/03/02/r-fast...
https://gist.github.com/arunsrinivasan/7997521
I would guess that most implementations don't have indices, and that might be an indication that they're not essential. But for someone with a computer science background it seems annoying not to use hash tables when they are so obviously applicable.
As you've said, I think the inclusion of indices comes from people used to working with more of a database background speeding up frequent common queries. SAS data sets can be indexed, but I don't think there's anything intellectually to be gained there that isn't gotten just from general database indexes, since SAS data sets are designed to be on-disk data structures and operate very similarly to database tables.
Talking completely off the cuff here, I imagine it has to do with the fact that these are mostly designed to be in-memory/columnar based structures, by people doing particular kinds of analysis on those structures. I'm not saying indices can't play a part, but that given the context, they're mainly in the realms of micro and query optimisations.
I think one has to ask what kind of use case would an index support, and what does it gain in efficiency vs take away in complexity?
For in memory columnar analysis on highly mutable data structures, its not quite so clear that it gains that much.
First of all, if you're scanning an entire column, you're not gaining anything from indexes. Indeed, you're losing out because of the cost/space to store one.
Second of all, if you're updating or mutating the data structure frequently in memory, then the cost of re-indexing the data structure needs to be paid each time. A cost even more questionable when in-memory access is already pretty fast. And in a lot of this field, that's a common use case.
Thirdly, if you're just randomly accessing into points within the column, well usually columns are set out as collections of continuous arrays of memory. To offset into the array at a particular index i is likely faster than the double indirection of looking up an index (also in memory) and then offsetting into another point in the original array.
R and the like already have the concept of indexing into a data frame using an array of integers, which you could argue not only covers the concept of an index, but possibly might even be more efficient than storing them in a hash.
Lets say you want to index on a string or a complex object/combination of objects/values? Well there's a potential use case (since a string doesn't usually index straight into a low-level continuous array), but the likes of R does have the concept of row names (albeit, i can't remember how efficiently its implemented), which already lets you access a dataframe notionally based on the name of a row.
Indeed, that's one of the places hashes have in my own implementation: figuring out how to index into the objects via strings labels. But I deliberately left the inclusion of row/column names optional (though column names are included by default since that seems to be the defacto norm).
In practice, many programmers/programs in this space either legitimately don't need or don't use the concept.
Indeed, I struggled quite intently whether to include rowname indexing as a concept at all, since I personally have barely used them in my day to day life for the last 10+ years. But I can't say there isn't a use for them. I suppose transition matrices on real world entities come to mind...
Maybe they are used for fast lookup? In other words, its like an index? If you want to retrieve a particular row, it's usually an O(n) scan. But maybe row names are like a limited kind of index and you can retrieve by name in O(1) time.
I tend to follow Hadley Wickham's model -- column labels are essential, but I'm pretty sure he would say row names are not in the model? I haven't seen it addressed actually.
If I'm understanding correctly the transition matrix example, I think data frames and matrices are vastly different. And it makes sense to have labels for every dimension on matrices, but not data frames.
What language are you implementing your data frame library in? I'm curious about both the API and the algorithms. I looked at Hadley's newer dplyr code, and it's mostly in C++., as opposed to plyr which was mostly in R.
Are you a R user? If I were doing this (which I may but not for like a year), I would probably use Hadley's API and model the code after his. I'm curious if you have any criticisms of the way he does things.
FWIW the summary of using indices is that it changes the computational complexity of an algorithm -- and O(n + m) algorithm can be turned into O(m log n), and this makes an orders of magnitude difference in running time. It's not small difference. I've used this to good effect in real programs.
It's more like data preparation than analysis, but that is a big part of what people use data frames for.