It seems I have more to learn about rdflib's SPARQL query engine. A persistent issue was the mis-use of indexing for what (I thought) should be simple queries. My error was in including triples of the form ?x rdf:type openworm:type in the query patterns. For reasons I don't yet understand, the engine evaluates such statements before others even if there's a more reductive join it could perform from other patterns. Hopefully I can understand this eventually.

In any case, standard object->property->value queries are effectively O(1) time again--yay!