Any web search speed depends on its functionality and features. When we search on the web, we all get almost the same result; this means web search work on cache, while there is no cache stored for Gmail searches. This is one reason; I think there are a few more reasons why Gmail search is slow;  Gmail search is real-time and needs to be a perfect match, while web search is sorted by relevance.  Gmail search needs to be 100% accurate.  Gmail does not have a cache or hot searches.