Hi Tim, [I prefer to keep the mailing list involved to share the discussion; I hope you don't mind ... ;-) ]
On Mon, Jul 04, 2011 at 07:30:36PM +0200, Tim Speier wrote: > Hello Stefan, > > thanks for your fast reply. > > I am especially interested in tuple reconstruction mechanisms in > column-oriented databases. So I'm not a user. I see; please also consider reading our papers (cf., 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 Basically, "even" in main memory, sequential access is fast, while random access is slow. > > > Further, for any set of BATs the represent the individual columns of a > > relational table, the BATs' "heads" (first/left column) are aligned and > > consist of OIDs that form a dense (i.e., increment == 1) ascending sequence > > of integer numbers starting at a given offset (usually 0). Thus, these OIDs > > can indeed be seen as tuple-/record- identifiers. Be aware, though, that > > these OIDs are only used internally and not available as tuple-/record- > > identifiers in SQL. > > Given their denseness properly, these OIDs are usually not materialized > > (read: physically stored) but rather computed on the fly, and they > > effectively indicate (module offset) the physical position of the respective > > record's attribute values in all BATs involved. > > I am sorry, but it is not yet clear to me. Let me create an example: > A relation R with two attributes X and Y. It consists of the following > tuples: > > +---+-----+ > | X | Y | > +---+-----+ > | A | 300 | > +---+-----+ > | B | 100 | > +---+-----+ > | C | 400 | > +---+-----+ > > Now let's create two BATs: each record gets its own OID and, my naive > approach, map each attribute values to a BAT: > > BAT X BAT Y > +---+---+ +---+-----+ > |OID|VAL| |OID|VAL | > +---+---+ +---+-----+ > | 0 | A | | 0 | 300 | > +---+---+ +---+-----+ > | 1 | B | | 1 | 100 | > +---+---+ +---+-----+ > | 2 | C | | 2 | 400 | > +---+---+ +---+-----+ > > Now I could reconstruct each tuple by its OID and the index. But I would > loose some advantages of the column-oriented databases. Like which? I guess you mean having each column sorted individually? > A more sophisticated approach would be to store values in ascending > order like this: > > BAT X BAT Y > +---+---+ +---+-----+ > |OID|VAL| |OID|VAL | > +---+---+ +---+-----+ > | 0 | A | | 1 | 100 | > +---+---+ +---+-----+ > | 1 | B | | 0 | 300 | > +---+---+ +---+-----+ > | 2 | C | | 2 | 400 | > +---+---+ +---+-----+ > > But how can I now reconstruct the tuples efficient now? > Is there an additional index structure (as you said in > your foregoing email). ? 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" ... ;-) Hope this helps you further --- don't hesitate to keep asking in case you have more questions ... Gruß, Stefan > > I'm very sorry for my innocent questions. > Tim -- | Stefan.Manegold @ CWI.nl | DB Architectures (INS1) | | http://CWI.nl/~manegold/ | Science Park 123 (L321) | | Tel.: +31 (0)20 592-4212 | 1098 XG Amsterdam (NL) | ------------------------------------------------------------------------------ All of the data generated in your IT infrastructure is seriously valuable. Why? It contains a definitive record of application performance, security threats, fraudulent activity, and more. Splunk takes this data and makes sense of it. IT sense. And common sense. http://p.sf.net/sfu/splunk-d2d-c2 _______________________________________________ Monetdb-developers mailing list Monetdb-developers@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-developers
