Not just in Windows 10. The start menu search in W7 was also always absymally slow, completely independent of hardware. Even on an SSD it's unusably slow.
Which I just don't understand. That thing isn't doing shit. I have literally no idea why it's this slow. I've written an equivalent of it for my Linux/i3 setup, which is completely stupid and naive (no caching at all, parses _all_ program definitions every time it's opened) and that is at least a hundred times faster. The latter is instantaneous (<10 ms on this computer), while the W7 start menu takes seconds to find anything -- on the same computer!
Also, the only start menu w/ search that is comparatively slow is the Unity search. Most others are practically instantaneous (eg. KDE), even on weaker hardware...
Back "in the day" I built an AMD 5x86 machine with 4mb that ran DOS and could -just barely- decode 128K MP3s using some DOS-based MP3 player I found. On top of that, I ran a custom menu system (wrote it using TurboC iirc) that drove a 16x2 LCD via the parallel port. I had this idea that I would set it up as a car pc, but never actually did.
Remember TSRs eating up precious conventional memory?
All of which is to say: Windows has an "accumulated cruft" problem that exists independently of what the hardware could do. The search built into Windows 10 is abysmally slow - in fact, almost every interaction with the toolbar or Explorer tends to be slow if you've installed a lot of stuff, because you oftentimes are "paying for what you don't use" when the program adds an Explorer extension, and there's a paucity of diagnostic tools to throw that fact in your face, so it just manifests as "Windows sure is slow lately". DOS doesn't have that problem because DOS does almost nothing, and cannot be extended to do more.
(On that note, Windows 10 did make a major breakthrough in responsiveness: it compresses memory in inactive programs, so you hit disk much less when running and switching between lots of programs.)