Query planner generating wrong bounds for compound indexes

[apkar]

$ python test/correctness/document-correctness.py --doclayer-host localhost --doclayer-port 27018 forever doclayer mm --seed 9203356367461099619 --num-doc 300 --num-iter 1 --no-update --no-sort --no-numeric-fieldnames
Instance: 0459504932136
========================================================
ID : 35746 iteration : 1
========================================================
Query results didn't match!
Query: {'$and': [{u'E': None}, {'$and': [{u'C': None}, {u'A': {'$lte': 'c'}}]}]}
Projection: OrderedDict([(u'C', True), (u'D', True)])

  pymongo.collection   (0)
  mongo_model          (1): {u'_id': datetime.datetime(1970, 1, 22, 10, 7, 43)}

  RESULT SET DIFFERENCES (as 'sets' so order within the returned results is not considered)
    Only in mongo_model : {'_id': 1970-01-22 10:07:43}

python /Users/bmuppana/src/fdb-document-layer/test/correctness/document-correctness.py --mongo-host localhost --mongo-port 27018 --doclayer-host localhost --doclayer-port 27018 forever doclayer mm --seed 9203356367461099619 --num-doc 300 --num-iter 1 --no-update --no-sort --no-numeric-fieldnames

Found this against d2840e9. Consistently reproducible with the above seed.

[apkar]

A simpler case that reproduces the bug

db.test.remove()
db.test.drop_indexes()
db.test.insert({'A': 'hello', 'B': 'world', 'C': 'HELLO'})
db.test.create_index([('A', pymongo.ASCENDING), ('B', pymongo.ASCENDING)])
db.test.create_index([('A', pymongo.ASCENDING), ('B', pymongo.ASCENDING), ('C', pymongo.ASCENDING)])

A simple query on this that supposed to match the document returns nothing

In [38]: for row in db.test.find({'A': 'hello', 'B': 'world', 'C': 'HELLO'}):
    ...:     print row
    ...:

In [39]: db.test.find({'A': 'hello', 'B': 'world', 'C': 'HELLO'}).explain()
Out[39]:
{
    "explanation":{
        "source_plan":{
            "projection":"{}",
            "source_plan":{
                "filter":"ANY(ExtPath((B\\x00) matching EQUALS(\"world\"))",
                "source_plan":{
                    "bounds":{
                        "begin":"(hello\\x00(HELLO\\x00",
                        "end":"(hello\\x00(HELLO\\x00"
                    },
                    "index name":"A_1_B_1_C_1",
                    "type":"index scan"
                },
                "type":"filter"
            },
            "type":"projection"
        },
        "type":"non-isolated"
    }
}

In [40]:

If we drop the indexes and try again

In [40]: db.test.drop_indexes()

In [41]: for row in db.test.find({'A': 'hello', 'B': 'world', 'C': 'HELLO'}):
    ...:     print row
    ...:
{u'A': u'hello', u'C': u'HELLO', u'B': u'world', u'_id': ObjectId('5c5b62e2945b2617f81e60a6')}

In [42]: db.test.find({'A': 'hello', 'B': 'world', 'C': 'HELLO'}).explain()
Out[42]:
{
    "explanation":{
        "source_plan":{
            "projection":"{}",
            "source_plan":{
                "filter":"AND(ANY(ExtPath((A\\x00) matching EQUALS(\"hello\")), ANY(ExtPath((C\\x00) matching EQUALS(\"HELLO\")), ANY(ExtPath((B\\x00) matching EQUALS(\"world\")))",
                "source_plan":{
                    "type":"table scan"
                },
                "type":"filter"
            },
            "type":"projection"
        },
        "type":"non-isolated"
    }
}

In [43]:

That gives the correct result.

The bug is in the compound index matching scheme - code handles term by term in a multi-term predicate and tries to extend index such that longest prefix is matched. We have a bug in prefix handling. In the above example after matching term on A, instead of taking prefix A we take prefix A:B causing the missing index key on B.

This part of the code is a bit of a mess. As we do store integer only field names as integers (instead of strings), we try to store the index prefixes as byte streams (DataKey) making all this code super hard to analyze. This code can be cleaned up and simplified a lot.