We are developing a grid information service, RGIS, that is based on the relational data model. RGIS supports complex queries written in SQL that search for compositions (using joins) of resources. For example, we might ask it to find a Linux cluster with a certain bisection bandwidth and total memory. Such queries can be expensive to execute, however, and so we have developed several approaches that leverage our GIS schema to let us trade off between the number of results returned and the execution time. In this paper, we describe two of them: scoped queries and approximate queries. Scoped queries constrain search to a network neighborhood, returning all matching results in the neighborhood. Approximate queries reduce the number of joins done by replacing collective constraints with constraints on individual resources, returning a subset of all the possible results in the grid. Scoping, approximation, and nondeterminism (described elsewhere), can be combined. In this paper, we describe scoped and approximate queries, how they are implemented, and present performance evaluations for two examples. The evaluation suggests that scoping and approximation can greatly reduce query times while still returning a useful number of results.