LIFTI v7: The And-Not Operator

LIFTI is an open source full text index library for .NET - you can check it out on GitHub

LIFTI v7 introduces a new query operator that’s been on my wishlist for a while: the And-Not operator (&!). This operator allows you to efficiently subtract one set of search results from another - perfect for those “find this but not that” scenarios.

The use case

Imagine you’re searching a collection of documents about Paris. You want documents mentioning “eiffel” but you’re specifically not interested in the tower - maybe you’re researching the engineer Gustave Eiffel himself. With the new operator, you can write:

1var results = index.Search("eiffel &! tower");

This returns documents containing “eiffel” while excluding any that also mention “tower”. Simple and intuitive.

How it works

The &! operator is a binary operator that performs a set difference operation. Under the hood, it’s implemented as AndNotQueryOperator which extends the BinaryQueryOperator base class.

The evaluation logic is straightforward but has a neat optimization in line with the other similar binary operators:

 1public override IntermediateQueryResult Evaluate(
 2    Func<IIndexNavigator> navigatorCreator, 
 3    QueryContext queryContext)
 4{
 5    // Evaluate left side first
 6    var leftResults = this.Left.Evaluate(navigatorCreator, queryContext);
 7
 8    if (leftResults.Matches.Count == 0)
 9    {
10        // Nothing to subtract from
11        return IntermediateQueryResult.Empty;
12    }
13
14    // Only evaluate right side for documents that matched left
15    var documentFilter = leftResults.ToDocumentIdLookup();
16    if (queryContext.FilterToDocumentIds != null)
17    {
18        documentFilter = [.. queryContext.FilterToDocumentIds
19            .Intersect(documentFilter)];
20    }
21
22    var rightResults = this.Right.Evaluate(
23        navigatorCreator,
24        queryContext with { FilterToDocumentIds = documentFilter });
25
26    var timing = queryContext.ExecutionTimings.Start(this, queryContext);
27    var results = leftResults.Except(rightResults);
28    return timing.Complete(results);
29}

The key optimization is that we only evaluate the right-hand side for documents that appear in the left-hand results. There’s no point checking if document 42 contains “tower” if it didn’t contain “eiffel” in the first place. This filtering can significantly reduce the work needed for the right-hand query evaluation.

Once we have both result sets, we call leftResults.Except(rightResults) which does the actual set difference, preserving all the scoring and field match information from the left side.

Parsing the operator

The query parser needed minimal changes to support &!. The tokenizer recognizes it as a distinct token type:

1case '&':
2    if (this.ConsumeIf('!'))
3    {
4        return QueryTokenType.AndNotOperator;
5    }
6    // ... existing & handling

And the parser treats it like any other binary operator:

1case QueryTokenType.AndNotOperator:
2    var rightPart = this.CreateQueryPart(
3        fieldLookup, state, state.GetNextToken(), null);
4    return CombineParts(
5        currentQuery, rightPart, token.TokenType, token.Tolerance);

Precedence matters

One interesting detail is the operator precedence. The &! operator has the same precedence as OR, which might seem counterintuitive at first. However, this makes sense when you consider complex queries:

1// These are equivalent - & has higher precedence than &!
2food & cake &! cheese
3(food & cake) &! cheese

This means the AND operation binds tighter, which feels natural when reading the query: “find food AND cake, but NOT cheese”.

Query execution plans

The And-Not operator also integrates with LIFTI’s query execution plan visualization. It appears as an Except node in the plan tree, making it easy to debug complex queries:

1var results = index.Search("eiffel &! tower", 
2    QueryExecutionOptions.IncludeExecutionPlan);
3var plan = results.GetExecutionPlan();
4Console.WriteLine(plan.ToString());

More examples

1// Documents about Paris excluding museums
2index.Search("paris &! museum")
3
4// Technical articles excluding beginner content
5index.Search("technical &! (beginner | tutorial)")
6
7// Field-restricted exclusions
8index.Search("title=important &! content=spam")

One important note: the &! operator requires a left-hand operand. You can’t start a query with &! term - that wouldn’t make sense anyway since there’s nothing to subtract from!

That’s it! The And-Not operator is a simple but powerful addition to LIFTI’s query syntax that makes exclusion queries much more elegant.