storage vs. retrieval typically comes down to optimizing for space vs. optimizing for time.

For instance, there's the concept of data normalization -- you associate data with its main identifier (eg, a person has a address, and a reservation has a person, and a reservation has a room, and a room has a capacity, and on down the chain). The problem comes when you need to retrieve data -- it's stored in a very compact manner, but the system has to join multiple tables together to do its basic day-to-day operations. (and what if something changes? When Bob Smith moves, do we want it to reflect that his bill from the stay last year was sent to his old address, as opposed to his new address?)

Often, when you're optimizing for retrieval, you have more indexes (based on how you're going to look for the data -- when optimizing for storage, you just need them for maintaining unique constraints (PK is a type of unique contraint), so you won't do things like having multi-field indexes (so you can pull out the most commonly used fields from the table, without reading in the whole record), and other such tricks.

Um... I could ramble on for hours on this, but that should give you a quick idea of the issues.

Oh -- and have you even tried analyzing the app? eg, check to where the program is spending all of its time?