Service directories are a key component of distributed systems where shared information must be managed effi- ciently. For a directory with a large numbers of entries, the result set of a query may be large, too. In this case it is important to order the results according to heuristics and to retrieve them incrementally. Our contribution is an integrated directory system specially adapted to large-scale service discovery and composition. We introduce DirQL, a flexible query language for the matching and ranking of service descriptions. As results are incrementally retrieved, our system is able to lazily compute the result set based on: 1) the organization of the directory as a special balanced search tree that has an extra "intersection" discriminator, 2) a scheme for transforming the original query into one taking into account the tree structure of the directory, and 3) the organization of partial results in a heap structure sorted according to the transformed query. We also report on experimental results regarding the usage of the directory by a composition engine solving randomly generated problems.