Since version 3.x Firefox is using SQLite-databases to store it’s interal stuff like history, awsome-bar etc. Because the database can get fragmented over time, you might want to do some cleanup once in a while.

To do so, just open up Tools\Error-Console and evaluate this statemant:

Components.classes["@mozilla.org/browser/nav-history-service;1"].getService(Components.interfaces.nsPIPlacesDatabase).DBConnection.executeSimpleSQL("VACUUM");

This should freeze the UI for a couple of seconds, but after that you’re all set to go.