How accurate the search hits should be (cf. Precision and Recall? Do you need "best ranked results" or "some result" or "all the matching documents? or How fast should the query be: sub-second or a second / minute / hour / day? What is the expected workload regarding read and write? I guess consistency is must have, how fast do you need writes to be available for read? Do you need deep traversal kind of queries? Do you need textual search, and / or multiple criteria look up with exact match, sorting, and possibly facets?