OP_PHRASE should support more non-leaf subqueries

[Olly Betts]

Updated summary reflecting changes in this area:

Since 1.4.3, OP_PHRASE (and other positional operators) support non-leaf subqueries which only use OP_OR.

Ideally we would support other subqueries, although the best semantics aren't always entirely obvious (we interpret B OR C as occurring at any position where B or C occurs, but what positions does B AND C occur at? At first glance "any position where both B and C occurs" seems obvious, but doesn't work well because typically multiple terms don't occur at the same position...)

Long ago, Xapian would instead distribute the operation - e.g.

A OP_PHRASE (B OP_OR C)

was converted it to:

(A OP_PHRASE B) OP_OR (A OP_PHRASE C)

I think this worked for one level subqueries, and for more (maybe arbitrary?) operators, not just OP_OR.

It built more complex and less efficient queries than the newer support.

It provides a way to interpret a phrase with an OP_AND subquery, though I'm not sure I'd expect A OP_PHRASE (B OP_AND C) to mean exactly the same as "A B" AND "A C".

Perhaps it's easier to think about OP_NEAR - to me at least A NEAR (B AND C) seems to more naturally mean "find an occurrence of A which is near an occurrence of B and an occurrence of C, but (A NEAR B) AND (A NEAR C) also matches cases where different occurrences of A are near B and near C.

This is likely an internal implementation change, without any API or ABI changes required.

[Olly Betts]

It's time we got 1.3.1 out.

[Olly Betts]

Also well past time we got 1.3.2 out.

[Olly Betts]

As noted above, this doesn't involve an ABI change.

However, IIRC 1.3.x no longer supports even the distribution of the operator indicated in the description, so this is probably currently a regression compared to 1.2.x.

[Olly Betts]

However, IIRC 1.3.x no longer supports even the distribution of the operator indicated in the description

Tested and confirmed.

For OP_OR, we can have an OrPositionList which merges the positions lists (much like OrPostList) , but there's not an obvious matching interpretation for all the operators - e.g. (a AND b) NEAR c can't really require a and b occur at the same position, as generally only one term occurs at each position. Expanding this to (a NEAR c) AND (b NEAR c) as 1.2.x does makes sense (though if we're clever we create the equivalent (a AND b AND c) plus two positional filters which can get hoisted).

[Olly Betts]

Looks like currently this case segfaults! Reproducible with:

q = xapian.Query(xapian.Query.OP_PHRASE, [xapian.Query(xapian.Query.OP_OR, "a", "b"), "c"])
db = xapian.Database("../../xapian-core/tests/.chert/db=etext")
enq = xapian.Enquire(db)
enq.set_query(q)
m = enq.get_mset(0, 10)

It looks like the issue here is that a OR b decays to a (since b isn't a term in that database), and the OrPostList gets deleted, but the hoisted phrase check still uses the OrPostList...

[Olly Betts]

Patch to add OrPositionList

[Olly Betts]

The attached patch adds OrPositionList, which seems to work aside from the same issue if the OR decays.

[Olly Betts]

I noticed that expanding (a AND_NOT b) NEAR c to (a NEAR c) AND_NOT b seems more natural than expanding it to (a NEAR c) AND_NOT (b NEAR c).

[Olly Betts]

[0a01a2f6f309bd1477233937f580639b144e167b/git] addresses the segfault by checking for and rejecting non-leaf subqueries of OP_PHRASE and OP_NEAR with UnimplementedError.

Such cases should be supported, but it's not worth holding up 1.4.0 for now the segfault is addressed.

[Olly Betts]

This branch supports OP_OR with 2 subqueries under OP_NEAR and OP_PHRASE:

​https://github.com/ojwb/xapian/tree/orpositionlist

The 2 subquery restriction needs a bit of work on the new OrPositionList class to fix - the patch attached here used a series of pairwise OrPositionList objects, but the new patch needs a single one instead - the class needs reworking to handle that.

[Olly Betts]

I've pushed a commit to the above branch which handles any sub-tree using only OP_OR as a subquery of OP_NEAR and OP_PHRASE.

Marking to consider for next 1.4.x release.

[Olly Betts]

JFD mentioned the cases of OP_PHRASE and OP_NEAR used in subqueries, which have an obvious meaning (approximately they occur where they match at the location of each term for that match). Currently the positional check exits as soon as it finds a match in a given document - when used in a subquery it would need to (potentially) keep going and find all matches.

[Olly Betts]

OP_OR handling branch applied to master in dba350ba15b7eaf315d5270ac3eca4deb40f4b93 and 55e12a7a0b68b49b209945caa708eaab64dfb7fa, and those backported for 1.4.3 as 8ba3f148713fe0dbb693a0f1f57907c05cbde581 and 076d877224200ee70452fad104a61c0acc63df78.

[Olly Betts]

The rest of this ticket isn't for 1.4.3.

[Olly Betts]

Milestone renamed