Search is instant because it never queries your content tables directly: everything searchable is extracted into a dedicated index. The index builds on activation, updates live when content is published, rebuilds itself when the search scope changes, and can run on one of two storage engines: MySQL (the default) or SQLite. The engine switch lives under Elevated › Site Search › Settings › Advanced Options › Indexer.
Both engines power identical features; they differ in where the index lives.

Click the engine you want under Search Engine, then click Force Index Rebuild: the index builds fresh on the chosen engine and search switches over when it completes. The status line always names the active engine and its document count.
The status line says there is no index for the active engine. The engine changed without a rebuild. Click Force Index Rebuild to build it.
Document count looks lower than expected. The count covers published items of the indexed post types only. Check the scope under Content to Index.