I just hava a zsh binding for using fzf to doing a fuzzy search of my history. The fzf package actually includes the implementation of the zsh "widget".
We shelled out to fzf in the very early days, but found the initial indexing to be a bit slower + add latency vs SQLite