Hi, my 2 cents
I don't think the base will need a massive parallel system (DB speaking) In essence because there is only one task that needs to be done per FOV at a given time: Matching what was just detected against what we knew from prior visits (from earlier this night or other nights). The amount of points that we need to match per FOV is very small, order of 10e5 x 6 10e6 in the worst case (The Galactic Plane). It is not big deal to dinamically build zones for a (10 deg^2) FOV and do the spatial match. There is nothing to be scared of about doing the spatial match inside the DBMS. The trick is to have the data organized/partitioned in such a way that we can quickly prepare what we know about the FOV we are about to process and build a "mini database" in real time for that area of the sky. The DBMS will put everything in memory if that is possibel. If not, the DBMS will know better than us how to move data from disk to memory. The key is being smart about how to partition the data and how to manage the partitions. In summary, how do we know what partitions contain what we need? Jacek is mentioning ~13 k partitions for the Object table. You need to add the partitions involved in breaking down the (DIA)Source table. Anyway, from my point of view, the cross-match is not an issue at the base, the actual issues/questions are: First, figuring out what are the attributes from the Object and Source tables that will be required to decide whether or not is necessary to trigger an alert and how complex are these queries. Second, If I am observing the same piece of the sky for a second time during the same night what do I need to know about what happened in the prior visit? The answer to those two questions will determine what needs to be inserted and updated in real or near real time at the base. We are talking a lot about having the indexes in memory, building our own indexes, and solving the problems in memory ... those are good thoughts. However, the indexes are not the actual data and sooner or later you will have to go to get the data out of disk. Talk to you tomorrow Cheers Maria On Wed, 1 Nov 2006, Becla, Jacek wrote: > Keywords: DataAccWG > > Hi Serge, > > I'm moving this discussion to the mailing list, yes, it is interesting enough. > > This might work, however, I worry that it solves only the cross match > problem. I am hoping that the solution to "the other problem" will > automatically solve the cross-match problem (at no extra cost). > This "other" problem is updating ~100K objects per visit. In practice we will > be updating only part of the object: most values for a given band, so ~1/6 of > all attributes, or ~300 bytes, but that is still too much to simply assume > that we will be able to keep that in memory. > > Thanks, > Jacek > > P.s. Why are you saying we have 5 min preparation time? I thought Tim > mentioned we would have information about next observing field ~30 sec in > advance. > > > > > > -----Original Message----- > > From: Serge Monkewitz [mailto:[EMAIL PROTECTED] > > Sent: Wednesday, November 01, 2006 5:53 PM > > To: [EMAIL PROTECTED]; Becla, Jacek; > > [EMAIL PROTECTED]; [EMAIL PROTECTED] > > Subject: An idea for the object catalog cross-match > > > > Hi all, > > > > I wasn't sure if this was of enough interest to post to > > the LSST-DM list, but let me know if I should post it there. > > > > I've been thinking about cross-matching against the > > object catalog problem, specifically in the context of the > > base camp and I have fairly simple idea that I think could > > work. The idea runs counter to the current "everything must > > be massively parallel" line of thinking: what about storing a > > compressed structure that represents the *entire* object > > catalog (in a fashion similar to the WAX band/lane and > > Maria's zone/ra approach) in the memory of a single machine? > > This attempts to address the following > > issues: > > > > - For a particular visit, we have a minimum of 5 min. preparation time > > - [using zone approach] If I have understood correctly, zone > > tables have to be created/indexed or brought into memory > > during this time. If they aren't created dynamically, then > > one must deal with various issues: the zone table(s) might > > have to be updated along with the object catalog, > > partitioning zone table(s) is complicated by the fact that a > > single object may belong to more than 1 zone table or zone > > table partition. > > - [using WAX approach] The equivalent of the zone table has > > to be read and created from the DBMS (basically it's the > > "create zone tables dynamically" > > approach with custom code for index creation and x-match). > > > > > > Instead, consider the bare minimum we need to do a distance > > based match - for objects and DIA sources: ID, ra, dec. > > Additionally, an object type might be useful. > > > > First of all, quantize ra, dec into 32 bit integers (e.g. > > write ra = 360*x degrees, store x as a 32 bit fraction: 0 <= > > x <= (2^32 - 1)/2^32 and dec = 180*y degrees, y is a 32 bit > > fraction 0 <= y <= (2^32 - 1)/2^32). This means we are > > storing ra as multiples of ~0.0003 arc seconds, and dec as > > multiples of ~0.00015 arc seconds. Finally, let the id be > > some 64bit integer and reserve a small number of bits for the > > object type (maybe just a single bit that says whether or not > > the object is variable?). > > > > If we were to stop there, storing 20 billion objects at 16 > > bytes per object would take ~320GB, which one might expect to > > be within the memory capacity of a single machine by 2012 (I > > can buy a 2 socket machine with 64GB of RAM today). However, > > it's quite easy to further reduce the memory > > requirements: > > > > - bin objects into (for example) 64k bands/zones. This means > > the band/zone an object is in automatically gives you the > > upper 16bits of that objects dec value. > > - within a band/zone, store objects in ascending ra order. > > Exploit this ordering to save space via delta-coding. > > - Instead of storing some arbitrary id for an object, > > stipulate that the first 40bits of the id are given by some > > combination of the upper ~20 most significant bits of ra and > > dec. The remaining ~24bits are dedicated towards guaranteeing > > uniqueness of the ID. > > > > [Note: I expect data structure overhead to be quite small > > compared to the object data, for the moment I am just ignoring it] > > > > So basically it seems quite feasible with only a very > > lightweight compression scheme to store the necessary > > information from the object catalog using roughly 8 bytes per > > object, or ~160GB of memory. Of course, fancier compression > > techniques could be applied on top of or instead of the above. > > > > Some further questions then arise: > > > > 1. How is this in-memory structure updated? > > ------------------------------------------- > > > > It is never updated. We are not allowed to update IDs > > anyway, and even if an object position is updated downstream, > > I am assuming that the new position will never differ much > > from the original one. The positions of the in-memory object > > representations are therefore somewhat fuzzy and this must be > > accounted for by increasing the search radius for finding matches. > > > > 2. What about new objects? > > -------------------------- > > > > These must of course be inserted into the structure (and > > such insertions must be logged to disk). Given the simple > > indexing and compression scheme as well as the fact that the > > number of inserts will in the common case be very small, this > > doesn't seem to be a problem. In fact, we can use the > > in-memory object index to generate the new object IDs: > > since the IDs correlate to position extremely well, we just > > have to do a cross match of the objects to insert against the > > existing ones with appropriate search radius to make sure we > > don't assign an ID already in use. Doing such a cross match > > also naturally tells us where in the structure the new > > objects must be inserted. > > > > 3. OK, but this is a (rough) distance match only - what next? > > ------------------------------------------------------------- > > > > The (DIA Source ID, object ID) match pairs are sent to > > the RDBMS. A 2-way join of the input DIA Source Collection > > with the full object > > table(s) then gives you the details necessary for further > > decision making. > > Hopefully the number of such pairs will be relatively small > > (when compared to the total number of objects in the visited > > region), otherwise the approach falls down. The speed of this > > join determines the viability of the approach. > > > > It seems to me this has the following pros: > > > > - should drastically reduce database reads > > - because everything stays in memory at all times, no advance > > knowledge of the observation schedule is needed (at least not > > for this step) > > - the object catalog at the base camp needs just a single > > B-tree index (on > > ID) > > - updates of the spatial index are eliminated > > - inserts are not complicated by having to distribute parts > > of the spatial index across machines > > - cross-match performance for a single visit will likely be > > extremely fast (consider that even a single machine will > > likely have 2 or 4 sockets with each socket having 4 or more > > cores) despite having to decompress data and compute (x,y,z) > > for each object position. > > > > and cons: > > > > - memory is expensive > > - for fault tolerance, we need at least 2 machines with > > enough memory to support this approach, and they really > > cannot be used for anything else > > - what if the fuzzy positions inflate the number of matches > > by a lot (especially early in the survey)? > > - not clear that this is useful for the archive center > > > > So what do you all think? Am I barking up a tree? > > > > Serge > > > > > > _______________________________________________ > LSST-data mailing list > [email protected] > http://www.lsstmail.org/mailman/listinfo/lsst-data > -- ------------------------------------------------ Maria A. Nieto-Santisteban ([EMAIL PROTECTED]) Johns Hopkins University 3400 N. Charles St. Physics & Astronomy Department Baltimore, MD 21218 (USA) Tel: 1 410 516-7679 Fax: 1 410 516-5096 _______________________________________________ LSST-data mailing list [email protected] http://www.lsstmail.org/mailman/listinfo/lsst-data
