For the record, we never suggested massive parallel system
at the base:
- we think we will get away with just one ingest server
(well two because of mirroring for fault tolerance)
- we are planning to serve Object Catalog from several
servers (naturally no one would want to dump 50TB of data
on a single server =).
Jacek
Maria A. Nieto-Santisteban wrote:
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
_______________________________________________
LSST-data mailing list
[email protected]
http://www.lsstmail.org/mailman/listinfo/lsst-data
