Have you tried out using ripgrep [0] or fzf [1]? 200ms is quite a lot for history search, I'd expect search to be 20ms or less. In fact, it should be instantaneous as it should all fit in memory really. I've been using fzf and the searches are all faster than my monitor can display frames (so less than 16ms), although I only have 10k entries on my history as I clear it up once in a while.
[0]: https://github.com/BurntSushi/ripgrep
[1]: https://github.com/junegunn/fzf