One common technique is vertical splitting, so you hold only the most recent records in the (main) table and create a history table for the old ones. To achieve this you have to conditionally (based on the time frame) do a union on the history table, and also create a mechanism to shift records from your main table to the history table. Also, you can try to (as another poster wrote) optimize / add indexes, and/or invest in a speedier DB-server ..