When you run a query on 10,000 anything, it’s going to be slow unless you’ve seriously optimized your servers to handle that kind of load. In general, we recommend you not have that many categories in part because of inherent database limitations.
Categories should be fairly broad things. Perhaps a mix of many fewer categories and lots of tags would achieve the result you want.