[I prefer to keep the mailing list involved to share the discussion; I hope you don't mind ... ;-) ]
Oops, I didn't notice...
http://repository.cwi.nl/search/searchrepository.php?stheme=INS1), in particular http://repository.cwi.nl/search/fullrecord.php?publnr=14290 http://repository.cwi.nl/search/fullrecord.php?publnr=11117
and/or these PhD these: http://repository.cwi.nl/search/fullrecord.php?publnr=14832 http://repository.cwi.nl/search/fullrecord.php?publnr=14301 http://repository.cwi.nl/search/fullrecord.php?publnr=16706
Wow, thank you. Especially "Self-organizing Tuple Reconstruction in Column-stores" seems to be very informative. I'm going to study ...
In the first case, tuple reconstruction is cheap (almost "for free"), as columns are physically aligned, and hence, highly efficient in-order positional lookup can be exploited for tuple reconstruction. Obviously, with keeping the columns physically aligned does not allow to order them individually according to their values. Thus without further indeces, value-lookups using binary search are only possible for on sorted column; for all other columns, some secondary index structure would be required. MonetDB only used (automatically) hash-indeces for single-value (point-)lookups, but resorts to (highly optimized) sequential scans for any range lookups on non-sorted columns.
In the second case, value-lookups can be done (reasonably) efficient using binary search on each column, however tuple-reconstruction (i.e., OID lookups) can no longer be done with simple highly efficient in-order positional lookups. In that case, MonetDB would (automatically on-the-fly) build a hash-index on the non-ordered (non-dense) OID columns.
In general, there is no such thing as a "free lunch" ... ;-)
Again, thank you very much for your fast and illuminating answer. Gruß Tim