Issue: Bug in bm25 ranking function with more than one term
Author: simonw
State: closed
Created: 2019-01-06 20:04:37

I think I've found a bug in the bm25 implementation:

https://github.com/coleifer/peewee/blob/a24b36da3a101458a854e6a4319f4bb8d8cb478f/playhouse/sqlite_ext.py#L1160-L1175

The specific problem is here:

https://github.com/coleifer/peewee/blob/a24b36da3a101458a854e6a4319f4bb8d8cb478f/playhouse/sqlite_ext.py#L1173-L1175

This code is supposed to extract the `term_frequency` and `docs_with_term` for term `i` and column `j`. BUT... I don't think the array pointer arithmetic here is correct. In particular, with more than one term I seem to be getting the wrong results.

After quite a lot of digging around, I think I've prepared an example that illustrates the problem. My code is here: https://gist.github.com/simonw/e0b9156d66b41b172a66d0cfe32d9391

I created a modified version of the bm25 function which outputs debugging information, then ran some sample searches through it. The output illustrating the problem is this:

```
search = dog cat
============
('both of them', 'both dog dog and cat here')
[2, 2, 5, 4, 5, 3, 6, 0, 1, 1, 2, 4, 2, 0, 1, 1, 1, 3, 2]
term_count=2, col_count=2, total_docs=5
term (i) = 0, column (j) = 0
  avg_length=4.0, doc_length=3.0
  term_frequency_in_this_column=0.0, docs_with_term_in_this_column=1.0
term (i) = 0, column (j) = 1
  avg_length=5.0, doc_length=6.0
  term_frequency_in_this_column=2.0, docs_with_term_in_this_column=2.0
term (i) = 1, column (j) = 0
  avg_length=4.0, doc_length=3.0
  term_frequency_in_this_column=0.0, docs_with_term_in_this_column=1.0
term (i) = 1, column (j) = 1
  avg_length=5.0, doc_length=6.0
  term_frequency_in_this_column=0.0, docs_with_term_in_this_column=1.0
-0.438011195601579
```

That's for a search for `dog cat` against the following five documents:

```
CREATE VIRTUAL TABLE docs USING fts4(c0, c1);
INSERT INTO docs (c0, c1) VALUES ("this is about a dog", "more about that dog dog");
INSERT INTO docs (c0, c1) VALUES ("this is about a cat", "stuff on that cat cat");
INSERT INTO docs (c0, c1) VALUES ("something about a ferret", "yeah a ferret ferret");
INSERT INTO docs (c0, c1) VALUES ("both of them", "both dog dog and cat here");
INSERT INTO docs (c0, c1) VALUES ("not mammals", "maybe talk about fish");
```

The bug is illustrated by the very last section of the above example output, this bit:

```
term (i) = 1, column (j) = 1
  avg_length=5.0, doc_length=6.0
  term_frequency_in_this_column=0.0, docs_with_term_in_this_column=1.0
```

Here the output is showing that the document `('both of them', 'both dog dog and cat here')` was found to match the search for `dog cat` - but that the statistics for the last term and column (so the term `cat` in the column `both dog dog and cat here`) have `term_frequency_in_this_column` of 0.0.

This is incorrect! The word cat appears once in that column, so this value should be 1.0.

The bug is in the `x = X_O + (3 * j * (i + 1))` line which calculates the offset within the matchinfo array.

I think the correct formula for that line is:

    x = X_O + ((i * term_count) + j) * 3

If I make that single line change to my example script I get the following output, which I think is correct:

```
search = dog cat
============
('both of them', 'both dog dog and cat here')
[2, 2, 5, 4, 5, 3, 6, 0, 1, 1, 2, 4, 2, 0, 1, 1, 1, 3, 2]
term_count=2, col_count=2, total_docs=5
term (i) = 0, column (j) = 0
  avg_length=4.0, doc_length=3.0
[0, 1, 1, 2, 4, 2, 0, 1, 1, 1, 3, 2]
  term_frequency_in_this_column=0.0, docs_with_term_in_this_column=1.0
term (i) = 0, column (j) = 1
  avg_length=5.0, doc_length=6.0
[2, 4, 2, 0, 1, 1, 1, 3, 2]
  term_frequency_in_this_column=2.0, docs_with_term_in_this_column=2.0
term (i) = 1, column (j) = 0
  avg_length=4.0, doc_length=3.0
[0, 1, 1, 1, 3, 2]
  term_frequency_in_this_column=0.0, docs_with_term_in_this_column=1.0
term (i) = 1, column (j) = 1
  avg_length=5.0, doc_length=6.0
[1, 3, 2]
  term_frequency_in_this_column=1.0, docs_with_term_in_this_column=2.0
-0.749035952142196
```

Here's the spreadsheet I used to figure out the correct formula: https://docs.google.com/spreadsheets/d/1htR7CWjmF25TZQ8BLzAIh2QHCiInFlfBZbhg7lt-mrM/edit?usp=sharing

Just for reference, here are example implementations I based my code on:

* https://github.com/rads/sqlite-okapi-bm25/blob/master/okapi_bm25.c
* https://github.com/parantapa/sqlite-okapi-bm25/blob/master/okapi_bm25.c

Relevant snip:

```c
    for (int i = 0; i < termCount; i++) {
        int currentX = X_OFFSET + (3 * searchTextCol * (i + 1));
        double termFrequency = matchinfo[currentX];
        double docsWithTerm = matchinfo[currentX + 2];

        double idf = log(
            (totalDocs - docsWithTerm + 0.5) /
            (docsWithTerm + 0.5)
        );

        double rightSide = (
            (termFrequency * (K1 + 1)) /
            (termFrequency + (K1 * (1 - B + (B * (docLength / avgLength)))))
        );

        sum += (idf * rightSide);
    }
```

Specifically, where "searchTextCol" corresponds to "j" in my example:

```c
int currentX = X_OFFSET + (3 * searchTextCol * (i + 1));
```

Huh... maybe the bug is in their code as well?

I'm 80% sure I'm right about this, but that's why I posted so much supporting documentation: this definitely needs fresh eyes on it!

It looks like someone reported the same bug against one of those repos: https://github.com/rads/sqlite-okapi-bm25/issues/2

Indeed, I've got scrap paper out and am seeing it, too.

You suggested `x = X_O + ((i * term_count) + j) * 3`

But I think it is `x = X_O + ((i * col_count) + j) * 3` and it looks like the issue on the linked repo agrees with that.

Yes you're right - looks like a bug in my spreadsheet. Your version is giving me the expected results.

Ugh, travis-ci and its ancient sqlite...last patch should do the trick.

The reason I spotted this is I've been building a standalone library for packaging up some SQLite FTS4 functions. It includes an `annotate_matchinfo()` function which attempts to convert the matchinfo array into something a lot more useful.

You can see that in action here: https://datasette-sqlite-fts4.datasette.io/24ways-fts4-52e8a02?sql=select%0D%0A++++json_object%28%0D%0A++++++++%22label%22%2C+articles.title%2C+%22href%22%2C+articles.url%0D%0A++++%29+as+article%2C%0D%0A++++articles.author%2C%0D%0A++++rank_score%28matchinfo%28articles_fts%2C+%22pcx%22%29%29+as+score%2C%0D%0A++++rank_bm25%28matchinfo%28articles_fts%2C+%22pcnalx%22%29%29+as+bm25%2C%0D%0A++++json_object%28%0D%0A++++++++%22pre%22%2C+annotate_matchinfo%28matchinfo%28articles_fts%2C+%22pcxnalyb%22%29%2C+%22pcxnalyb%22%29%0D%0A++++%29+as+annotated_matchinfo%2C%0D%0A++++matchinfo%28articles_fts%2C+%22pcxnalyb%22%29+as+matchinfo%2C%0D%0A++++decode_matchinfo%28matchinfo%28articles_fts%2C+%22pcxnalyb%22%29%29+as+decoded_matchinfo%0D%0Afrom%0D%0A++++articles_fts+join+articles+on+articles.rowid+%3D+articles_fts.rowid%0D%0Awhere%0D%0A++++articles_fts+match+%3Asearch%0D%0Aorder+by+bm25&search=jquery+maps

The library I am building is here: https://github.com/simonw/sqlite-fts4

I believe this is fixed now. Thanks for the help! I'll push a new release today or tomorrow with the patch.

3.8.1