>> SELECT *
>> FROM A_TABLE at
>> WHERE
>> at.VALUE1 = 'Y' AND
>> NOT EXISTS (
>> SELECT 1
>> FROM B_TABLE bt
>> WHERE bt.VALUE2 = 'X');
>
> The query PLAN would tell you for certain, but I would expect the answer to be:
> half of A_TABLE rows times all of B_TABLE rows.

If there's an index on B_TABLE.VALUE2, it would be at most half of
A_TABLE rows times log(B_TABLE rows). Besides, your sub-query doesn't
use values from A_TABLE, so in fact it would be enough to evaluate it
once (it yields the same results for all records of A_TABLE). Whether
Firebird takes advantage of this fact or not is unfortunately beyond my
league and someone with more thorough knowledge about Firebird internals
would have to cast some light on this matter.

regards
Tomasz