Okay, so now a simple query like this:

#Cats
SELECT ?item ?itemLabel ?stateLabel
WHERE{
  ?item wdt:P17 wd:Q668.
  ?item wdt:P131 ?state.
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}

is giving me an error.

I checked the second query without the label service and than it works, but it returns almost 200k results. That already takes a long time and if each found triple needs to go through the label service as well, that is too long and it times out. If I limit to 1K results it takes about 4 seconds. 200k will take a lot longer. Without the label service the query takes 4534 ms, which is about just as long as 1k with the label service.

For the airport query, I'd try with " hint:Query hint:optimizer "None" . ". Unfortunately, sometimes Optimizer misinterprets the queries, especially when services and paths are involved.

I realize where I was wrong. Thank you! I think this ticket can be closed.