Gmail doesn't even have substring search (e.g. searching for "hack" will not find instances of "hacker"). I think that would be a prerequisite for Instant-style searching.
True. But it's worth noting that those predictions are sufficient for a slow, partially-working substring search. Gmail could search for the n most likely completions of your query terms in addition to the normal search, and collate the results.
