Optimizing bitwise filtering in SQL

Question

I am implementing a bitwise filter using SQL, and I want to see if the following optimization is always valid in all cases, and I'm not sure how to prove it. My goal is to limit the number of rows that get compared.

Standard filter pseudo-sql:

IF (A & B = A) // SHOW VALUE

The question is, will it work to add this? :

IF (A = B) OR (A & B = A) WHERE (B >= A) // SHOW VALUE

It seems to me that B must always be >= to A - is there a case where this is not true?

I realize that the above code is still not optimal, I just want to know if this is a viable direction to go in.

Does someone have some amazing maths to help me?

Answer 1

As long as you are dealing with unsigned ints (whether as a column type in mysql, or as a contraint in other dbs), then this is true:

(A & B == A) implies (B >= A) *not* (A >= B)

The math of it is that B must have all of the bits in A set, and possibly more. If a single bit from A was not set in B, then A & B != A.

(Note that the converse is not always true: (B >= A) does not imply that (A & B == A). As a simple counterexample, 5 > 3, but 3 & 5 = 1.)

Also, as soon as you get into negative numbers, you may run into situations where A & B = A, but B < A.

One more thing: (A & B = A) includes the case where (A = B), so saying

IF (A = B) OR (A & B = A) ...

is redundant. Remove the (A = B) unless you can see a speed difference with your SQL engine.