Ongoing Purging Of Active Records Causes Deadlocks

Hi,

We have a Java application that runs against a variety of backends
including Oracle and MSSql 2000 and 2005. Our application has a
handful of active tables that are constantly being inserted into, and
some of which are being selected from on a regular basis.

We have a purge job to remove unneeded records that every hour "DELETE
FROM <tableWHERE <datafield< <sometimestamp>". This is how we are
purging because we need 100% up time, so we do so every hour. For
some tables the timestamp is 2 weeks ago, others its 2 hours ago. The
date field is indexed in some cases, in others it is not... the
DELETE is always done off of a transaction (autoCommit on), but
experimentation has shown doing it on one doesn't help much.

This task normally functions fine, but every once in a while the
inserts or counts on this table fail with deadlocks during the purge
job. I'm looking for thoughts as to what we could do differently or
other experience doing this type of thing, some possibilities include:
- doing a select first, then deleting one by one. This is a
possibility, but its SLOW and may take over an hour to do this so we'd
be constantly churning deleting single records from the db.
- freezing access to these tables during the purge job... our app
cannot really afford to do this, but perhaps this is the only option.
- doing an update of an "OBSOLETE" flag on the record, then deleting
by that flag... i'm not sure we'd avoid issues doing this, but its'
an option.

The failures happen VERY infrequently on sql2005 and much more
frequently on sql2000. Any help or guidance would be most
appreciated, thanks!

Bob