Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-88173

BinData bit comparisons give wrong results in many cases

    • Type: Icon: Bug Bug
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • 7.0.9, 7.3.2, 8.0.0-rc2
    • Affects Version/s: 5.3.2, 4.3.6, 3.6.23, 4.0.28, 5.1.1, 6.1.1, 5.2.1, 6.2.1, 4.2.25, 6.3.2, 7.1.1, 5.0.25, 4.4.29, 6.0.14, 8.0.0-rc0, 7.0.7, 7.2.2, 7.3.0-rc7
    • Component/s: None
    • Labels:
    • Query Execution
    • Fully Compatible
    • ALL
    • v8.0, v7.3, v7.0, v6.0, v5.0
    • QE 2024-04-01, QE 2024-04-15

      Issue Status as of May 15, 2024

      ISSUE SUMMARY

      In MongoDB versions 7.0.9 and 7.3.2, the behavior of bitwise query operators changed such that the bytes in BinData values were interpreted in reverse order. This can result in incorrect results for queries which use the bitwise operators either with BinData arguments or to match against stored BinData values.

      Bitwise operators using a numerical bitmask or specifying explicit bit positions matching against stored numbers are not affected by the bug in versions 7.0.9 and 7.3.2.

      These changes were introduced as part of this ticket (SERVER-88173), and were reverted by SERVER-90288 in versions 7.0.11 and 7.3.3. See the User Summary Box at SERVER-90288 for more information on the impact of these changes and workarounds.

      Original Description:
      This reproduces for me in today's latest master branch, both with Classic engine and SBE. This is a server bug. It was injected in version 3.1.6 on 2015-07-15 by SERVER-19385 "Optimize Bit Test Query Operators with Numbers". This change introduced at least two bugs:

      1. It treats everything as a sign-extended 64-bit integer, so it skips checking for bit positions > 63.
      2. It converts BinData bit masks into a vector of integer bit positions incorrectly.

      Bug number 2 explains the behavior in the reproduction in the first comment below. The code comments say the lowest-order bit of the entire mask is bit position 0, but the implementation actually records the lowest order bit of the leftmost byte of the bit mask as bit position 0. The leftmost byte thus contains bit positions 0-7 right to left, the second byte contains bit positions 8-15 right to left, etc. In the repro data, the query uses the same BinData as the document with _id: 1. The docs that should match are 1, 3, 4 but only 1, 4 are actually retrieved. This is because of the bit mask swizzling bug:

      Should match _id Description _bitMask # bytes Desired _bitPositions Actual _bitPositions
      Yes 1 1n << 80n 11 80 0
        2 1n << 100n 13 100 4
      Yes 3 1n << 80n | 1n << 100n 13 80, 100 4, 16
      Yes 4 1n << 80n | 1n << 85n 11 80, 85 0, 5

      We see that _ids 1, 3, 4 should all have bit position 80 set and thus all be retrieved, but in the code they have wrong bit positions as described above and shown in the right-most column of the table. _ids 1 and 4 both have bit position 0 set, so they match, but _id3, which should match, does not have any bit positions set in common with _id 1, so it does not match and is not returned.

      It appears that bit tests using BinData bit masks (either data or probes) wider than 64 bits will not work correctly. Also, even when <= 64 bits (8 bytes), they won't work correctly unless all the masks contain the same number of bytes. (If all the masks contain the same number of bytes, and this number is 8 or fewer, then they will work correctly because the same wrong ordering of the bit positions will be shared across all masks. As soon as any mask is a different number of bytes, however, that will no longer be true.)

            Assignee:
            kristina.znam@mongodb.com Kristina Znam
            Reporter:
            kevin.cherkauer@mongodb.com Kevin Cherkauer
            Votes:
            0 Vote for this issue
            Watchers:
            15 Start watching this issue

              Created:
              Updated:
              Resolved: