Azure Table Storage? Uggh. Nasty. I've tried half a dozen times to use them, and every time I've given up. Great for write-only data that you never want to see again. Horrible for real-world querying.
Your Table Storage queries should be really fast with Cosmos DB since, Cosmos DB supports efficient indexing and query.