Issue Details (XML | Word | Printable)

Key: CORE-4302
Type: Bug Bug
Status: Closed Closed
Resolution: Fixed
Priority: Major Major
Assignee: Vlad Khorsun
Reporter: Vlad Khorsun
Votes: 0
Watchers: 5
Operations

If you were logged in you would be able to see more operations.
Firebird Core

Lookup (or scan) in descending index could be very inefficient for some keys

Created: 21/Dec/13 06:29 PM   Updated: 25/Sep/15 12:21 PM
Component/s: Engine
Affects Version/s: 2.1.5 Update 1, 2.5.2 Update 1, 3.0 Alpha 1
Fix Version/s: 3.0 Alpha 2, 2.1.6, 2.5.3

Issue Links:
Relate
 

QA Status: Done successfully
Test Details:
Test uses MON$ tables to gather statistics snapshot before and after each of query.
Database that is restored (''mon-stat-gathering-N_M.fbk') contains procedures for gathering statistics and view for displaying results in convenient form. In particular, this view has columns that show DIFFERENCE of fetches and thus we can estimate performance.
Numeric literals in the code (5, 20, 100, ... ) were adjusted after several measurements on:
1) WI-V2.5.4.26847 SuperServer:
1.1) with default value of DefaultDBCachePages and
1.2) when it was 8192
2) WI-T3.0.0.31708 (CS/SC/SS):
2.1) with default value of DefaultDBCachePages and
2.2) when it was: 256 on CS, 512 on SC and 8192 on SS.

These numeric literals are used as 'upper-bounds' for comparison with actual fetches. If actual value became equal or more than 'upper-bound' than output will be '!high!' and thus will lead test to FAIL, because expected result is 'normal'.


 Description  « Hide
Big thanks to the Pavel Zotov who found the issue and helped with testing.



Using FB3, default config (SS, page cache 2048, database page size is 4096).

Prepare data

set term ^;

create table t1 (id int, val int)
^

execute block as
declare i int = 0;
begin
  while (i < 1000000) do
  begin
    insert into t1 values (:i, mod(:i, 10));
    i = i + 1;
  end
end
^
commit
^

create descending index t1_desc_idx on t1 (val)
^

set stat on
^


Issue 1: insert three records and look at stats

insert into t1 values (100, 1)^
Buffers = 2048
Reads = 0
Writes 0
Fetches = 7

SQL> insert into t1 values (100, 2)^
Buffers = 2048
Reads = 0
Writes 0
Fetches = 386


SQL> insert into t1 values (100, 3)^
Buffers = 2048
Reads = 0
Writes 0
Fetches = 7

There was 7 fetches for keys "1" and "3" while 386 fetches for key "2" !


Another example (on the same data):

select * from t1 where val <= 1 order by val desc rows 1^

          ID VAL
============ ============
           1 1

Elapsed time= 0.00 sec
Buffers = 2048
Reads = 2
Writes 0
Fetches = 7


select * from t1 where val <= 2 order by val desc rows 1^

          ID VAL
============ ============
           2 2

Elapsed time= 0.64 sec
Buffers = 2048
Reads = 28576
Writes 4
Fetches = 645359

select * from t1 where val <= 3 order by val desc rows 1^

          ID VAL
============ ============
           3 3

Elapsed time= 0.00 sec
Buffers = 2048
Reads = 4
Writes 0
Fetches = 7

Again, key "2" produced very poor performance comparing with another keys

 All   Comments   Change History   Subversion Commits      Sort Order: Ascending order - Click to sort in descending order
Vlad Khorsun added a comment - 21/Dec/13 06:36 PM
The same test agains v2.5.2

insert into t1 values (100, 1)^
Buffers = 2048
Reads = 0
Writes 0
Fetches = 7

insert into t1 values (100, 2)^
Buffers = 2048
Reads = 0
Writes 0
Fetches = 386

insert into t1 values (100, 3)^
Buffers = 2048
Reads = 0
Writes 0
Fetches = 7


select * from t1 where val <= 1 order by val desc rows 1^

          ID VAL
============ ============
           1 1

Elapsed time= 0.04 sec
Buffers = 2048
Reads = 13
Writes 0
Fetches = 268


select * from t1 where val <= 2 order by val desc rows 1^

          ID VAL
============ ============
           2 2

Elapsed time= 0.07 sec
Buffers = 2048
Reads = 0
Writes 0
Fetches = 892


select * from t1 where val <= 3 order by val desc rows 1^

          ID VAL
============ ============
           3 3

Elapsed time= 0.05 sec
Buffers = 2048
Reads = 0
Writes 0
Fetches = 494


You see - v2.5.2 have same results for INSERT and a bit different (but steel bad) results for SELECT.

Vlad Khorsun added a comment - 21/Dec/13 07:12 PM
The problem is present in descending index when there are keys which are longer then inserted\searched key but have the same prefix.
In descending indices shorter keys are greater than longer keys and this fact was not accounted in some (not all) code parts.

For example, we are searching for key 'a' and keys 'aa', 'ab' etc are present.
With numbers in test case above i can say that key 2 is encoded as 0x3F while keys 3, 4, etc are encoded as two bytes with 0x3F as first byte.


Vlad Khorsun added a comment - 21/Dec/13 07:15 PM
Stats after the fix for fb3:

insert into t1 values (100, 1)^
Fetches = 7

insert into t1 values (100, 2)^
Fetches = 7

insert into t1 values (100, 3)^
Fetches = 7


select * from t1 where val <= 1 order by val desc rows 1^

          ID VAL
============ ============
           1 1

Reads = 2
Fetches = 7


select * from t1 where val <= 2 order by val desc rows 1^

          ID VAL
============ ============
           2 2

Reads = 0
Fetches = 7


select * from t1 where val <= 3 order by val desc rows 1^

          ID VAL
============ ============
           3 3

Reads = 0
Fetches = 7

Vlad Khorsun added a comment - 21/Dec/13 07:17 PM
Stats after the fix for v2.5.2

insert into t1 values (100, 1)^
Fetches = 7

insert into t1 values (100, 2)^
Fetches = 7

insert into t1 values (100, 3)^
Fetches = 7



select * from t1 where val <= 1 order by val desc rows 1^

          ID VAL
============ ============
           1 1

Reads = 13
Fetches = 268


select * from t1 where val <= 2 order by val desc rows 1^

          ID VAL
============ ============
           2 2

Reads = 0
Fetches = 374


select * from t1 where val <= 3 order by val desc rows 1^

          ID VAL
============ ============
           3 3

Reads = 0
Fetches = 494

Vlad Khorsun added a comment - 21/Dec/13 07:33 PM
Stats for the v2.1 is the same as for the v2.5

Pavel Zotov added a comment - 23/Dec/13 04:02 PM
> In descending indices shorter keys are greater than longer keys and this fact was not accounted in some (not all) code parts.

Seems that in the following case we have the same high cost and poor statistics but for building bitmap and single search rahter than index navigating:

DDL:
=====
set echo off;
commit;
recreate table td(id int, s varchar(50)); commit;
set term ^;
execute block as
begin
  begin
    execute statement 'create sequence g';
    when any do begin end
  end
end^
set term ;^
commit;
alter sequence g restart with 0;
commit;

set term ^;
execute block as
declare n int = 1000000;
declare m int;
begin
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'q' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qw' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwe' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwer' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwert' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwerty' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyu' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyui' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyuio' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyuiop' ) returning :m-1 into m;
end^ set term ;^ commit;
--create index td_s_asc on td(s); commit;
create descending index td_s_des on td(s); commit;

Query:
=====
set stat on;
set plan on;
set echo on;
select count(*) from rdb$database where exists(select * from td where s='qwertyuioo'); -- note: `o` duplicated at the end of key

Output:
======
PLAN (TD INDEX (TD_S_DES))
PLAN (RDB$DATABASE NATURAL)
. . .
Elapsed time= 6.57 sec
Buffers = 524288
Reads = 140644
Writes = 2
Fetches = 18012008

So, we have over 18 mil fetches when search single key that is absent in index :(

Sean Leyne added a comment - 23/Dec/13 05:05 PM
I am thinking that the Summary wording, to better reflect the problem, should be more along the lines of:

Descending index with large number of duplicates can cause inefficient index operations

Thoughts?

Vlad Khorsun added a comment - 23/Dec/13 06:02 PM - edited
Pavel,
sooner of all this is completely different issue.


Sean,
I object to changing summary in a way you offer.

Sean Leyne added a comment - 23/Dec/13 06:09 PM - edited
@Vlad, Please suggest some alternate. The current description seems 'vague'/ambiguous.

Vlad Khorsun added a comment - 23/Dec/13 07:36 PM
Sean,

so far i see no need to do it.

Explain what kind of ambiguity do you see here ?

Sean Leyne added a comment - 23/Dec/13 07:48 PM
The word "inefficient" without any other context is the problem. What is inefficient? The index navigation logic (how)? The index data storage?

Vlad Khorsun added a comment - 23/Dec/13 08:39 PM
Well, we can change subject to something like:

Search for some keys in descending index requires much more fetches\reads than it is necessary

PS So, why "inefficient index operations" is less ambigious then just "inefficient" ? :)

Sean Leyne added a comment - 23/Dec/13 09:29 PM
Ok, how about:

Descending index can cause large number of data reads/fetches when large number of duplicate index values present.

Vlad Khorsun added a comment - 23/Dec/13 09:57 PM
Why do you make accent on duplicates ? They makes issue more visible, yes, but are not an essential part of the problem.
The real problem was that *some keys* in *descending* index handled in a wrong\inefficient way.
I make summary text reflect most significant sides of the issue.
I don't want to create poema in summary text, there is test case with all necessary details in it.
I see no sense to spend so much time discussing this.

Dmitry Yemanov added a comment - 24/Dec/13 08:16 AM
I'd only suggest to add "Lookup in" in front of the title, as it's not the index itself that's inefficient but the index scan.

Vlad Khorsun added a comment - 24/Dec/13 02:52 PM
Re-opened to fix the new issue found by Pavel.
While it is different from the code POV it also could be formulated as "indefficient descending index scan for some values".

Pavel Cisar added a comment - 25/Sep/15 12:21 PM
Test created.