In my experience the limiting factor in response time is the traversal of the FS/OS structures in your step 1. It seems unlikely that anything this program is doing would be any slower than what you are describing.
On Windows for example there is Everything search engine which scans NTFS table and installs filter driver. Its instant on any disk size. If it were keeping its database in sqlite, we would have exactly what AtlasBarfed suggested.
I am drawing a distinction between actually using an SQL database as the dynamic attribute store of the file system, vs “dumping the FS to SQLite”, which implies an on-demand traversal to me.
