How longer you use firefox how slower the automatic search will be. There is a plugin thats defragment the search database.
Quote Vacuum Places Improved 1:
Defragments your Firefox “Places” database (history/bookmarks)
This greatly reduces the lag while typing in the address bar and the start-up time.
This extension features configurable automatic cleaning, periodic reminder, and internationalization.