Firebird

Nikolay Samofatov wrote:
> 
> In our builds of the engine we had to back-out NOT IN change and revert 
> behavior to the Firebird 1.5 logic.
> Are there plans to do the same or implement accurate fix to use index 
> again for Firebird 2.1 release?

I'm not going to rollback the change unconditionally. However, in the 
short term, I see two possible options (maybe offered together):

1) Follow the old code path when the inner (subselect) comparison field 
is defined as NOT NULL
2) Provide a legacy behavior config switch

I do plan to have a proper solution for the generic case in the long 
term, but I cannot guarantee that it will still use an index-based 
nested loop semi-join (maybe a hash or merge semi-join would be 
easier/proper to implement).


Dmitry

Dmitry Yemanov escreveu:
> I do plan to have a proper solution for the generic case in the long 
> term, but I cannot guarantee that it will still use an index-based 
> nested loop semi-join (maybe a hash or merge semi-join would be 
> easier/proper to implement).
>   
I suppose I didn't understand this issue completely, but what prevent we 
from inject some expressions, for example, in the query:

select t.id
    from things t
    where t.id not in (
       select st.thing
          from somethings st
    )

we already create:
    where st.thing <> t.id

but we may also create:
    or st.thing is null

and maybe:
    order by st.thing

and filter the NULLs?

-- 
Adriano dos Santos Fernandes
http://www.firebirdsql.org

Could one comment on this?

My initial tests says it works, with two (one for the lookup and one for 
the IS NULL) indexed access in the inner stream. ;-)

But I may completely missing something. :-)


Adriano


Adriano dos Santos Fernandes escreveu:
> Dmitry Yemanov escreveu:
>   
>> I do plan to have a proper solution for the generic case in the long 
>> term, but I cannot guarantee that it will still use an index-based 
>> nested loop semi-join (maybe a hash or merge semi-join would be 
>> easier/proper to implement).
>>   
>>     
> I suppose I didn't understand this issue completely, but what prevent we 
> from inject some expressions, for example, in the query:
>
> select t.id
>     from things t
>     where t.id not in (
>        select st.thing
>           from somethings st
>     )
>
> we already create:
>     where st.thing <> t.id
>
> but we may also create:
>     or st.thing is null
>
> and maybe:
>     order by st.thing
>
> and filter the NULLs?
>
>   


-- 
Adriano dos Santos Fernandes
http://www.firebirdsql.org

> Could one comment on this?
> 
> My initial tests says it works, with two (one for the lookup and one for 
> the IS NULL) indexed access in the inner stream. ;-)
> 
> But I may completely missing something. :-)

    Does your tests cover all possible cases ? With NULL's in both
"things" and "somethings". I.e.

a) value not in (value, value, ... , value)

b) value not in (value, null, ... , value)

c) null not in (value, value, ... , value)

d) null not in (value, null, ... , value)

In cases (a) and (c) there is no NULLs in "NOT IN" list while
in cases (b) and (d) there is NULLs in "NOT IN" list.

Regards,
Vlad

Adriano,

You are correct about the logic. This is exactly how I wanted to 
implement temporary fix (until proper logic explained by Dmitry is 
implemented), but my tests did not produce the desired result in that 
couple hours which I could spend on the issue.

BTW, "IN" doesn't work correctly as well internally, but it always 
produces correct outside result because the engine does not implement 
"IS UNKNOWN" construct from SQL standard or any of its equivalents.
Probably, doing two index lookups for IN as well as NOT IN would be an 
overkill in the situation, but this is really a "kludge". :-)

Nikolay

Adriano dos Santos Fernandes wrote:
> Could one comment on this?
>
> My initial tests says it works, with two (one for the lookup and one for 
> the IS NULL) indexed access in the inner stream. ;-)
>
> But I may completely missing something. :-)
>
>
> Adriano
>
>
> Adriano dos Santos Fernandes escreveu:
>   
>> Dmitry Yemanov escreveu:
>>   
>>     
>>> I do plan to have a proper solution for the generic case in the long 
>>> term, but I cannot guarantee that it will still use an index-based 
>>> nested loop semi-join (maybe a hash or merge semi-join would be 
>>> easier/proper to implement).
>>>   
>>>     
>>>       
>> I suppose I didn't understand this issue completely, but what prevent we 
>> from inject some expressions, for example, in the query:
>>
>> select t.id
>>     from things t
>>     where t.id not in (
>>        select st.thing
>>           from somethings st
>>     )
>>
>> we already create:
>>     where st.thing <> t.id
>>
>> but we may also create:
>>     or st.thing is null
>>
>> and maybe:
>>     order by st.thing
>>
>> and filter the NULLs?
>>
>>   
>>     
>
>
>

Adriano,

> I suppose I didn't understand this issue completely, but what prevent we 
> from inject some expressions, for example, in the query:
> 
> select t.id
>     from things t
>     where t.id not in (
>        select st.thing
>           from somethings st
>     )
> 
> we already create:
>     where st.thing <> t.id
> 
> but we may also create:
>     or st.thing is null

{a NOT IN b} == {NOT (a = ANY b)} == {a <> ALL b}

This is just a single case of all possible usages of the ALL predicate. 
Your suggestion seems to work there, although it would require two index 
scans and one of them is independent from the outer stream. This is bad 
from the performance POV, and although it would be definitely better 
than a natural scan, it would still be a regression.

Going further, what about "value = ALL (subquery)"? I see no way how it 
could use an index. So your suggestion doesn't solve the problem in 
general, although I'd agree that NOT IN is used much more often than 
ANY/ALL.


Dmitry

Dmitry,

> Your suggestion seems to work there, although it would require two
index
> scans and one of them is independent from the outer stream. This is
bad
> from the performance POV, and although it would be definitely better
> than a natural scan...

(The answers to Vlad and Nikolay questions about the appropriateness of
the results of the proposed change are drop-dead issues)

Let's review the current reality of the current situation.

- The previous functionality worked fast but didn't return the correct
result!

- The current v2.1 functionality is a DOG!!  [a NATURAL scan is always
undesirable]

- The proposed change would require two index scan -- while not ideal it
is an index based operation so the performance should be reasonable.


May be I'm in the minority but:

A fast query which yields incorrect results == CRAP!!! 


So, while the proposed functionality would be a regression in
performance, it solves the significant issue of validity of results.

Someone evaluating FB might not like the performance of NOT IN, but will
reject it for any false results!


Sean

Dmitry Yemanov escreveu:
> {a NOT IN b} == {NOT (a = ANY b)} == {a <> ALL b}
>
> This is just a single case of all possible usages of the ALL predicate. 
> Your suggestion seems to work there, although it would require two index 
> scans and one of them is independent from the outer stream.
What exactly you mean by "independent" what direct problem it causes?

> This is bad from the performance POV, and although it would be definitely better 
> than a natural scan, it would still be a regression.
>   
I suppose N * 2 indexed scans will most of times be faster than N 
natural searches when N is a high value.

But we need some performance tests for it.
> Going further, what about "value = ALL (subquery)"? I see no way how it 
> could use an index. So your suggestion doesn't solve the problem in 
> general, although I'd agree that NOT IN is used much more often than 
> ANY/ALL.
I don't see a way... And Oracle also didn't uses indexes for ALL.

-- 
Adriano dos Santos Fernandes
http://www.firebirdsql.org

Adriano,

> What exactly you mean by "independent" what direct problem it causes?

A nested loop is an excellent choice when the inner stream depends on 
the outer one and this dependency maps to an index. In our case, this is 
true for "A op B" but wrong for "B IS NULL" which is an independent 
predicate. So the IS NULL scan will be performed against the same 
dataset on the every loop iteration. This is what I call sub-optimal.

>> This is bad from the performance POV, and although it would be definitely better 
>> than a natural scan, it would still be a regression.
>   
> I suppose N * 2 indexed scans will most of times be faster than N 
> natural searches when N is a high value.

Of course. But in the same time, it will be slower than using one index 
(as we did before). So people who want fast NOT IN queries will still 
notice a performance regression, although a lesser degree one than 
currently. And I'm afraid, they don't really care about their results 
correctness, because just a very few people are aware about the 
differences between NOT IN and NOT EXISTS in terms of the result set, 
while the majority votes for the same results as before delivered with 
the same speed :-( Look as Nickolay's customer case for example.

But anyway, your suggestion look like the best solution possible in the 
short-term, so let's try going this way and test the results properly. 
If it requires us to handle "A <> ALL" differently from other "A op ALL" 
operations, let it be so.

> I don't see a way... And Oracle also didn't uses indexes for ALL.

AFAIK, it doesn't use indices for NOT IN either, unless the inner 
comparison field is declared as NOT NULL.


Dmitry

Dmitry,
>> I suppose N * 2 indexed scans will most of times be faster than N 
>> natural searches when N is a high value.
>>     
>
> Of course. But in the same time, it will be slower than using one index 
> (as we did before). So people who want fast NOT IN queries will still 
> notice a performance regression, although a lesser degree one than 
> currently. And I'm afraid, they don't really care about their results 
> correctness, because just a very few people are aware about the 
> differences between NOT IN and NOT EXISTS in terms of the result set, 
> while the majority votes for the same results as before delivered with 
> the same speed :-( Look as Nickolay's customer case for example.
>   
In the customer's case (which is the large R&D shop), the problem is 
critical not because of speed, but because the change causes many basic 
functionality failures everywhere in the applications, which cannot be 
cured by DBAs (via adding indices, etc). The change in NOT IN algorithm 
complexity from O(N) to O(N*M) often translates to O(N^2) for them.  The 
application in question uses NOT IN construct for inner tables with 
1000000+ rows, with base tables having many rows to filter too. In this 
situation the application simply stops working because queries never 
finish. With this behavior NOT IN construct becomes unfit for production 
use.

And because the application is very large and routinely deals with large 
quantities of data, probably thousands of queries need to be 
reviewed/changed to eliminate all uses of NOT IN construct.
Also various reports were written by outside contractors for particular 
end customers, and the R&D budgets are now closed, making roll-out of 
Firebird 2+ with this issue literally impossible.

The ultimate problem is that it is not possible to justify allocation of 
a budget to fix/rewrite queries which were correct in the first place.

Nikolay

>> What exactly you mean by "independent" what direct problem it causes?
> 
> A nested loop is an excellent choice when the inner stream depends on 
> the outer one and this dependency maps to an index. In our case, this is 
> true for "A op B" but wrong for "B IS NULL" which is an independent 
> predicate. So the IS NULL scan will be performed against the same 
> dataset on the every loop iteration. This is what I call sub-optimal.

    Any chance to cache bitmap with NULL's between loop iterations ?

Regards,
Vlad

All,

As we discussed a while back, I've done a very simple change to use 
indexes for NOT IN.

The change doesn't involve BLR changes, so future more appropriate 
changes will not be affected.

The change just convert in CMP, queries of type:

select ... from <t1> where <x> not in (select <y> from <t2>)
(and variants that uses the same BLR: {NOT (a = ANY b)} and {a <> ALL b})

to:

select ... from <t1> where not exists (select <y> from <t2> where <y> = 
<x> or <y> is null)
(if <t2> has a boolean, the condition is ANDed)

It still requires more testing... I think it's worth commit in HEAD. 
What do you think?


Adriano

> As we discussed a while back, I've done a very simple change to use 
> indexes for NOT IN.
> 
> The change doesn't involve BLR changes, so future more appropriate 
> changes will not be affected.
> 
> The change just convert in CMP, queries of type:
> 
> select ... from <t1> where <x> not in (select <y> from <t2>)
> (and variants that uses the same BLR: {NOT (a = ANY b)} and {a <> ALL b})
> 
> to:
> 
> select ... from <t1> where not exists (select <y> from <t2> where <y> = 
> <x> or <y> is null)
> (if <t2> has a boolean, the condition is ANDed)

    Is it works if <x> and <y> is complex expressions ?
 
> It still requires more testing... I think it's worth commit in HEAD. 
> What do you think?

    It seems you have not noticed my question about correctness. Sad.
You also must add "and x is not null" to the outer table booleans, i.e. equal 
expression is :

select ... from <t1> 
  where not exists (select <y> from <t2> where <y> = <x> or <y> is null)
     and <x> is not null



    Look at simple example :

create table t1 (x int)
create table t2 (y int)
commit

insert into t1 values (1)
insert into t1 values (3)
insert into t1 values (null)

insert into t2 values (0)
insert into t2 values (1)
insert into t2 values (2)
insert into t2 values (null)
commit

create index t2_y on t2 (y)
commit

select * from t1
 where x not in (select y from t2)

X
----
3


select * from t1
 where not exists (select * from t2 where (y = x or y is null))

X
----
3
<null>


Regards,
Vlad

Oops, corrrection :

> insert into t2 values (null)

    Remove line above, please.

Regards,
Vlad

Vlad Khorsun wrote:
>> select ... from <t1> where not exists (select <y> from <t2> where <y> = 
>> <x> or <y> is null)
>> (if <t2> has a boolean, the condition is ANDed)
>>     
>
>     Is it works if <x> and <y> is complex expressions ?
>   
Yes, cloning expressions. Not sure how easy and really useful would be 
to implement hidden variables there direct in the engine.

>  
>   
>> It still requires more testing... I think it's worth commit in HEAD. 
>> What do you think?
>>     
>
>     It seems you have not noticed my question about correctness. Sad.
> You also must add "and x is not null" to the outer table booleans, i.e. equal 
> expression is :
>
> select ... from <t1> 
>   where not exists (select <y> from <t2> where <y> = <x> or <y> is null)
>      and <x> is not null
>   
Yes. Thanks.


Adriano

Vlad Khorsun escreveu:
>> As we discussed a while back, I've done a very simple change to use 
>> indexes for NOT IN.
>>
>> The change doesn't involve BLR changes, so future more appropriate 
>> changes will not be affected.
>>
>> The change just convert in CMP, queries of type:
>>
>> select ... from <t1> where <x> not in (select <y> from <t2>)
>> (and variants that uses the same BLR: {NOT (a = ANY b)} and {a <> ALL b})
>>
>> to:
>>
>> select ... from <t1> where not exists (select <y> from <t2> where <y> = 
>> <x> or <y> is null)
>> (if <t2> has a boolean, the condition is ANDed)
>>     
>
>     Is it works if <x> and <y> is complex expressions ?
>  
>   
>> It still requires more testing... I think it's worth commit in HEAD. 
>> What do you think?
>>     
>
>     It seems you have not noticed my question about correctness. Sad.
> You also must add "and x is not null" to the outer table booleans, i.e. equal 
> expression is :
>
> select ... from <t1> 
>   where not exists (select <y> from <t2> where <y> = <x> or <y> is null)
>      and <x> is not null
>
>
>
>     Look at simple example :
>
> create table t1 (x int)
> create table t2 (y int)
> commit
>
> insert into t1 values (1)
> insert into t1 values (3)
> insert into t1 values (null)
>
> insert into t2 values (0)
> insert into t2 values (1)
> insert into t2 values (2)
> --insert into t2 values (null)	removed
> commit
>
> create index t2_y on t2 (y)
> commit
>
> select * from t1
>  where x not in (select y from t2)
>
> X
> ----
> 3
>
>
> select * from t1
>  where not exists (select * from t2 where (y = x or y is null))
>
> X
> ----
> 3
> <null>
>   
Seems we identified the conditions incorrectly. Can anyone confirm that 
it should be?
    select ... from <t1>
        where not exists (
            select <y> from <t2> where <y> = <x> or (<y> is null and <x> 
is not null)
        )


Adriano

> Vlad Khorsun escreveu:
>>> As we discussed a while back, I've done a very simple change to use 
>>> indexes for NOT IN.
>>>
>>> The change doesn't involve BLR changes, so future more appropriate 
>>> changes will not be affected.
>>>
>>> The change just convert in CMP, queries of type:
>>>
>>> select ... from <t1> where <x> not in (select <y> from <t2>)
>>> (and variants that uses the same BLR: {NOT (a = ANY b)} and {a <> ALL b})
>>>
>>> to:
>>>
>>> select ... from <t1> where not exists (select <y> from <t2> where <y> = 
>>> <x> or <y> is null)
>>> (if <t2> has a boolean, the condition is ANDed)
>>>     
>>
>>     Is it works if <x> and <y> is complex expressions ?
>>  
>>   
>>> It still requires more testing... I think it's worth commit in HEAD. 
>>> What do you think?
>>>     
>>
>>     It seems you have not noticed my question about correctness. Sad.
>> You also must add "and x is not null" to the outer table booleans, i.e. equal 
>> expression is :
>>
>> select ... from <t1> 
>>   where not exists (select <y> from <t2> where <y> = <x> or <y> is null)
>>      and <x> is not null
>>
>>
>>
>>     Look at simple example :
>>
>> create table t1 (x int)
>> create table t2 (y int)
>> commit
>>
>> insert into t1 values (1)
>> insert into t1 values (3)
>> insert into t1 values (null)
>>
>> insert into t2 values (0)
>> insert into t2 values (1)
>> insert into t2 values (2)
>> --insert into t2 values (null) removed
>> commit
>>
>> create index t2_y on t2 (y)
>> commit
>>
>> select * from t1
>>  where x not in (select y from t2)
>>
>> X
>> ----
>> 3
>>
>>
>> select * from t1
>>  where not exists (select * from t2 where (y = x or y is null))
>>
>> X
>> ----
>> 3
>> <null>
>>   
> Seems we identified the conditions incorrectly. Can anyone confirm that 
> it should be?
>    select ... from <t1>
>        where not exists (
>            select <y> from <t2> where <y> = <x> or (<y> is null and <x> 
> is not null)
>        )

    I missed the case when <t2> is empty set. In this case any value in <t1>
must be accepted. So correct expression seems is :

select ... from <t1> 
   where not exists (select <y> from <t2> where <y> = <x> or <y> is null)
      and (<x> is not null or not exists(select <y> from <t2>))

and it is not equal to your variant in case when both <t1> and <t2> contains NULL's.

Regards,
Vlad