Since Firefox 3.0 bookmarks, history and most storage is kept in SQLite databases and, ass with any other database, SQLite databases become fragmented over time. But, since there are no managing processes checking and optimizing the database, these eventually result in a performance hit.

So, a good way to improve startup and some other bookmarks and history related tasks is to defragment and trim unused space from these databases.

• Open the Error Console: Tools menu/Error Console
• In the Code text box paste this (it’s a single line):

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

• Press Evaluate. Firefox will freeze for a few seconds while the databases are “VACUUMed”.

Thanks to PC Pro and Mozilla Links for this information.

Alternatively there are a couple of Firefox plugins available to do just this – Vacuum Places and PlacesCleaner.