If your Katapult search are slow, it's probably because you are searching large directory structures that you really don't need to be searching. In my case, the slow Katapult searches were a result of Katapult searching my Amarok music directory (about 20GB worth of material).

If your searches are slow in Katapult, you can help make this better by disabling the searches of files in Katapult, or at least by altering the way these files are searched. To do this, bring up the Katapult configuration dialog. Select "Catalogs" on the left pane and then select the catalog you want to alter on the right pane. In my case, this is "Amarok Catalog". Once it is selected, you can choose to disable searching in this catalog, or you can indicate the number of characters that must be entered before this catalog is searched. Since I usually don't try to find music in this way, I prefer to disable searching of these files in Katapult. Once you make this change, I noticed a significant speed increase in my Katapult searches.