I can't optimize a check for out-of-order bills

Question

Bills must be consecutive by date and number. I'm doing this query to check that I don't have out-of-order bills, but the performance is awful (I have millions of bills, so it takes minutes to check a month) :

SELECT NUMBER, DATE
FROM BILLS
WHERE DATE BETWEEN @FROM AND @TO AND
      EXISTS (SELECT *
              FROM BILLS OUT_OF_ORDER
              WHERE OUT_OF_ORDER.NUMBER < BILLS.NUMBER
              AND OUT_OF_ORDER.DATE > BILLS.DATE)

I already have indexes by NUMBER, DATE and DATE + NUMBER, but the compound index can't really be used in that query.

I have also tried removing the subquery with no noticeable difference.

SELECT DISTINCT BILLS.NUMBER, BILLS.DATE
FROM BILLS
INNER JOIN BILLS OUT_OF_ORDER ON OUT_OF_ORDER.NUMBER < BILLS.NUMBER AND
                                 OUT_OF_ORDER.DATE > BILLS.DATE
WHERE DATE BETWEEN @FROM AND @TO

Do you know how this kind of queries (using the >< operands on two different fields at the same time) can be improved ?.

I have added the execution plan. The problem obviously is on checking the OUT_OF_ORDER bills, it just uses the plain DATE index. As far as I know you can't define a compound index that allows you to search with >< operands on two different fields.

Answer 1

@Damien_The_Unbeliever made me remember that I have no gaps (or I shouldn't have them, which is verified on a second query). So I can just check the one previous bill and not all the previous bills.

Checking the previous bill uses the primary key, because I directly look for the bill NUMBER - 1.

Now this query only takes a few seconds instead of a few minutes.

SELECT BILLS.NUMBER, BILLS.DATE
FROM BILLS
INNER JOIN BILLS OUT_OF_ORDER ON OUT_OF_ORDER.NUMBER = BILLS.NUMBER - 1 AND
                                 OUT_OF_ORDER.DATE > BILLS.DATE
WHERE DATE BETWEEN @FROM AND @TO

Thank you all.