In general I go for partitioning only for tables expected to hold in excess of 100M rows, partitions 100K rows in size really does not make a lot of sense.

For some reason a lot of people believes partitioning will improve performance in some magical way - let me break some news here, in general(*) table partitioning does not improves performance but helps - if well designed - during administrative tasks like archiving and purging.

(*) an exception meaning, a scenario where table partitioning improves performance would be to serve queries that have to return several millions of granular data level rows. In this particular case a well designed partitioning strategy will make cheaper to full scan a particular partition rather than doing index access. Please note that this only works when partition key is the main filtering condition on query's predicate.

Going back to the original question. Is there any indexing strategy in place? Did you trace the query to see what it is doing?