How to create scalable & side-effect free integration tests?

Question

In my current project, I am having a hard time coming up with a good solution to create scalable integration tests that have no side effects. A little clarification on the side effect free property: it is mostly about the database; there shouldn't be any changes in the database after the tests are completed (state should be preserved). Maybe scalability and state preservation don't come together, but I really want to push for a better solution.

Here is a typical integration test (these tests touch the database layer):

public class OrderTests {

    List<Order> ordersToDelete = new ArrayList<Order>(); 

    public testOrderCreation() {
        Order order = new Order();
        assertTrue(order.save());
        orderToDelete.add(order);
    }

    public testOrderComparison() {
        Order order = new Order();
        Order order2 = new Order();
        assertFalse(order.isEqual(order2);
        orderToDelete.add(order);
        orderToDelete.add(order2);
    }
    // More tests

    public teardown() {
         for(Order order : ordersToDelete)
             order.delete();
    }
}

As one might imagine, this approach yields tests that are extremely slow. And, when applied to the whole integration tests, it takes around 5 seconds to test only a small portion of the system. I can imagine this number going up when the coverage is increased.

What would be another approach for writing such tests? One alternative I can think of is having kind of global variables (within a class) and all test methods share this variable. As a result, only few orders get created & deleted; resulting in faster tests. However, I think this introduces a bigger problem; the tests are no longer isolated and it gets more and more difficult to understand & analyze them.

It might just be that integration tests are not meant to be run as often as unit tests; therefore low performance might be acceptable for those. In any case, it would be great to know if someone came up with alternatives for improving scalability.