sparql query get slow with order by on Particular server

Question

I have simple sparql query. Same query works faster on my local system, while on stage server it takes 20 sec. If I remove the order by from the query, it take 2 sec on both server. Record counts are same on both the server; approx 1,50,000.

PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT * WHERE
{
     ?instance rdf:type  <http://example.com/vocab/Sample>.
     ?instance rdfs:label ?label
}ORDER BY ?label OFFSET 0 LIMIT 20

setups which I have are : Hadoop, Marmotta, zookeeper, Redis, tomcat

Appreciate some help to figure out the root cause..