This happened to me on a very high traffic website and I didn’t have the option to troubleshoot things by disabling plugins.
I deleted the relationship field, recreated it with the same name and the search started working again.
P.S. I use a plugin called “Custom Post Types UI” and I think the relationship field search broke after I created a new custom post type.
