It depends on data in your queries. If the data is not stored consecutively in disk, then OS has to read more than necessary pages so perf is bad. Now we have to look at how data is stored physically in disk. OpenTSDB is built on top of HBase which orders data based on rowkey. In OpenTSDB design, a data point's rowkey is something like this:
metric uid + partial timestamp + tag1 <key,value> + tag2 <key, value> + ....
So if your query contains a tag value '*', OS has to scan all of related rows. If unfortunately the tag in you query is not the first tag in physical storage, then lots of rows scanned are not related to your query. You can tell that even with explicit tag values you will still have such performance issues.
FYI, we are developing a TSDB, TickTockDB (
https://github.com/ytyou/ticktock), compatible to OpenTSDB APIs but with more than 50x better performance than OpenTSDB, after years of pains and frustrations with OpenTSDB. You can give a try if you are interested.
thanks