Thank you for your reply.

We can look into migrating to version 0.6 (or later)...

There exists an index for indexed-prop1, indexed-prop2, and indexed-prop3, but there are no multi-column indices (e.g., indexed-prop1 and indexed-prop2).  In our application, the columns that might be used for the search are specified by the user, and we wouldn't have any way of knowing in advance what combination of columns they might ask for.  The only thing that we can do now is to ensure that all of the columns that are used in a 'has' step are indexed.  

One approach that I thought might be an improvement is to perform the first traversal (i.e., " g.V().has('indexed-prop1', 'value1')") separately, collect the set of vertices which satisfy this query, then perform an additional query for each 'has' step that is currently in the 'union' step.  So, for example, we run g.V().has('indexed-prop1', 'value1') initially, and it returns 3 vertices (V1, V2, and V3).  We then run a traversal for indexed-prop2:   "g.V(V1, V2, V3).has('indexed-prop2', 'value2')", which returns a subset of the vertices returned by the first traversal.  Then, run another traversal, this time:   "g.V(V1, V2, V3).has('indexed-prop3', 'value3')", again returning a subset of the vertices.  Finally, figure out (programatically, without executing another traversal) the union of the vertices returned by the last 2 traversals.  This is an inelegant and brute-force technique which would probably work, but I would rather do this in a single traversal, and I haven't been able to figure out how to do this.  Can you recommend an approach for doing this kind of action in a single traversal?

Thanks,
Brad