Hi,
Index table is definitely the way to go. Indexing over 400 000 items will take a lot of hours. The number of keywords seems to be okay to me. It is also possible that the stats may not load from time to time, so just keep the indexing running until it finishes.
For that amount of content I highly suggest only indexing the most neccessary fields, as it will generate more than enough data to search. In your case probably indexing the post titles is more than enough: https://i.imgur.com/s3axyhD.png
Contents and excerpts may contain a lot of data, and for that amount of items the user will definitely get enough results for any search phrase.
Once the indexing is finished, you have to make sure the index table is enabled.
The rest is up to the underlying server performance and configuration. Make sure the server is on par with the amount of information, there is enough CPU and RAM, and if so, that the PHP has enough memory limit to perform the tasks. Querying such a large database for WordPress will take a lot more CPU and memory in general.
I also strongly suggest using this plugin to run an index query optimization on the database. It is super useful for generally big databases to make some very common queries much faster.