Service discovery becomes a key to hastening the evolution of web services as the number of services is expected to increase dramatically. In this paper, we propose to index all the ontology-annotated outputs in registered services. For each ontology-annotated output, there is a service list which records all the services in the registry that deliver the output. Based on the indexing, we propose a composition-oriented service discovery algorithm, which greatly accelerates the filtering of irrelevant atomic services by making use of the inverted indexing, and increases the likelihood of finding a possible candidate by exploring service composition. Experimental results show that the proposed algorithm provides a better performance on response time than the sequential matchmaking, and a better recall rate than the algorithms without the exploration of composition.