Patent ID: 8832077

Claim:
A method, comprising: receiving, from a client, a search query including filter criteria, wherein the filter criteria specify a plurality of operands including a first operand associated with one or more filters and a second operand associated with one or more filters, and a logical relationship between the plurality of operands, wherein the logical relationship between the plurality of operands is a Boolean NOT; and in response to the search query: identifying a plurality of index portions including a first set of one or more index portions matching the filter(s) of the first operand and a second set of one or more index portions matching the filter(s) of the second operand, wherein the plurality of index portions are identified in accordance with the plurality of operands and a criterion that index entries in the first set of index portion(s) and the second set of index portion(s) are sorted in a same sort order in accordance with identifiers for the index entries, and each of the plurality of index portions has a distinct combination of operands and sort order; identifying one or more matching entities that match the search query, wherein the identifying includes: (A) identifying a first set of one or more index entries in the first set of index portion(s) having a first identifier and matching the filter(s) of the first operand; (B) identifying, in the second set of index portion(s), a second set of one or more index entries in accordance with a second identifier, wherein the second identifier is closest to the first identifier in the sort order for index entries in the second set of index portion(s) that match the filter(s) of the second operand; (C) determining whether the first set of index portion(s) includes a respective set of one or more index entries that (i) matches the filter(s) of the first operand, and (ii) has respective identifiers between the first identifier and the second identifier; and (D) in accordance with a determination that the first set of index portion(s) includes a respective set of one or more index entries (i) having a respective identifier between the first identifier and the second identifier and (ii) matching the filter(s) of the first operand, marking a respective entity associated with the respective identifier as matching the search query; and providing representations of one or more of the matching entities to the client.