Searching Bookmarks or History is very slow

Recently, if I open the sidebars for History or Bookmarks, to search for a page, the bar opens fine, but then when I start to type in the search term, Firefox freezes up completely - typically for over a minute. This was not a problem until recently. I've tried running Firefox in Safe mode,but the problem still occurs. Any suggestions of what may be causing this or how to fix it would be welcomed. I'm running FF on a fairly powerful laptop purchased this year, so searching even a huge database of items shouldn't take that long.