I don't know if FSA is a sqlite database.
but if you have this many files, cataloging filenames into some type of DB might be faster for finding files later.
If your files are only appended and in some structure that you can catalog by day/month or something I would take the hit of a few months to catalog it, then have some way to add new files to that catalog.
Remember you can breakup find into multiple threads to build that last by directories, but sounds like you need some kind of metadata store thats not the filesystem.
Let us know what you end up doing for this, curious.