This longstanding bug has been found and fixed in the past few weeks. There’s a workaround as well (use the Places Maintenance addon to properly index your Places database).

https://bugzilla.mozilla.org/show_bug.cgi?id=686025