believe it or not, but many hugely popular applications from 20+ years ago didn't even implement indexing. in this case if you had too much mail your imap client would just time out.
well through the mid-2000s you even had to use a third party plugin for outlook called "lookout" if you wanted searches to not take minutes.