[Bug]: fulltext index search in tpch 100g lineitem oom

[tom-csf]

Is there an existing issue for the same bug?

• I have checked the existing issues.

Branch Name

main

Commit ID

c93bbbd

Other Environment Information

- Hardware parameters:
- OS type:
- Others:

Actual Behavior

Expected Behavior

No response

Steps to Reproduce

1、load 100g tpch data to mo
2、set experimental_fulltext_index=1;
create fulltext index fdx on lineitem(L_COMMENT)
3、select * from lineitem where match(l_comment) against('"olphins nag slyly after the regular packa"' in boolean mode);

Additional information

No response

[aronchanisme]

Fulltext index issue. Hi Eric @cpegeric , could you please kindly help take a look? Thanks.

[cpegeric]

mysql> select count(*) from lineitem where match(l_comment) against('deposits' in boolean mode);
ERROR 20101 (HY000): internal error: Invalid alloc size 1147486208

[ouyuanning]

hash build时候的OOM。不知道跟 #20236 是不是类似问题
@badboynt1 先帮忙定位一下吧

[badboynt1]

跟 #20236不是同一个问题，我在129上可以成功创建索引，但是我跑query会hang住，看起来这条query要跑10分钟以上？ 没有报错也没有oom @cpegeric

[badboynt1]

select * from lineitem where match(l_comment) against('"olphins nag slyly after the regular packa"' in boolean mode);

这条query在我本地环境上依然会hang住，或者需要运行超过十分钟。

但是即便我扫描全表， select * from lineitem where l_comment like "%olphins nag slyly after the regular packa%";
这条语句也能在数秒内返回。 看起来fulltext index的实现似乎有些问题
@cpegeric

[cpegeric]

The slow query in fulltext index is

select * from `__mo_index_secondary_019386fe-f00c-7b42-8f99-ba608027eee7` where word in ('olphins', 'nag', 'slyly', 'after', 'the', 'regular', 'packa') order by doc_id;

order by is slow when the number of rows is large.

mysql> select count(*) from `__mo_index_secondary_019386fe-f00c-7b42-8f99-ba608027eee7` where word in ('olphins', 'nag', 'slyly', 'after'
, 'the', 'regular', 'packa');
+-----------+
| count(*)  |
+-----------+
| 309164415 |
+-----------+

Possible solutions:

1. make ORDER BY faster
2. use stop word
3. return a vector to represent the text. Right now, multiple rows per doc_id returns that why we need to sort by doc_id.
4. Our own index file format that enable us to sort the index in advance but not sort on the fly.
5. use disk hashtable to speed up the word -> docid look up. https://github.com/rosedblabs/diskhash
6. disk cache https://github.com/peterbourgon/diskv

[fengttt]

First let's double check fulltext index table schema and primary key/cluster by key.

Second, the following query is not going to work well

select * from `__mo_index_secondary_019386fe-f00c-7b42-8f99-ba608027eee7` where word in ('olphins', 'nag', 'slyly', 'after', 'the', 'regular', 'packa') order by doc_id;

I would rather issue the following

with 
kw1 as (select docid, to_array(position) as pos from __mo_index where word = 'olphins' group by docid),
kw2 as (select docs, to_array(position) as pos from __mo_index where word = 'nag' group by docid),
...
select kw1.docid, kw1.pos as pos1, kw2.pos as pos2 ... kw6.pos6
from kw1, kw2, ... kw6
where kw1.docid = kw2.docid and kw1.docid = kw3.docid ....    

Note the we need a new agg function to_array, otherwise, the join could become a cross product of positions and explode. Of course, for phrase query, we don't need this to_array, we can put this is
the join condition

where kw1.docid = kw2.docid ....     AND kw1.pos + 1 = kw2.pos and kw2.pos +1 = kw3.pos ...

But there could be more complex position processing inside the fulltext function -- such as 'foo NEAR bar', etc, so to_array seems to be a better solution.

[cpegeric]

Checked, Cluster By word got some speed improvement but ORDER BY is not going to work.

only pharse search can use JOIN. For OR operation like natural language mode, we cannot use JOIN at all. I think we need to save the data from SQL into temporary file when the data size is large.

1. store the SQL result into map just like what we are doing
2. when data size exceed limit, sort the data with doc_id and save to temp file
3. After getting all results from SQL, we will have several temp files which is sorted by doc_id
4. use heapsort to get the sorted doc_id for each words by getting the top item from each files.
5. merge the doc_id into the data structure
6. when number of doc_id reach 8192 limit, process the batch
7. go back to step 4 to read the data

Note: use ordered map to prevent us from sorting the keys before save the file
https://github.com/elliotchance/orderedmap

[fengttt]

I think it should be cluster by at least, by (word, docid) or even (word, docid, position).

Next, I am really curious what is the performance if we just issue

where ...
AND kw1.docid = kw2.docid ....     AND kw1.pos + 1 = kw2.pos and kw2.pos +1 = kw3.pos ...

I don't see any reason this could be bad.

[fengttt]

Checked, Cluster By word got some speed improvement but ORDER BY is not going to work.

only pharse search can use JOIN. For OR operation like natural language mode, we cannot use JOIN at all. I think we need to save the data from SQL into temporary file when the data size is large.

1. store the SQL result into map just like what we are doing
2. when data size exceed limit, sort the data with doc_id and save to temp file
3. After getting all results from SQL, we will have several temp files which is sorted by doc_id
4. use heapsort to get the sorted doc_id for each words by getting the top item from each files.
5. merge the doc_id into the data structure
6. when number of doc_id reach 8192 limit, process the batch
7. go back to step 4 to read the data

Note: use ordered map to prevent us from sorting the keys before save the file https://github.com/elliotchance/orderedmap

I still don't see any reason/benefit of the order by. Just avoid it.

And for OR, it is not a join but a UNION ALL then group by. Basically, translate all fulltext query to proper SQL -- our query engine should be faster than any hand rolled code -- if not, we should optimize our query engine.

[fengttt]

But there could be more complex position processing inside the fulltext function -- such as 'foo NEAR bar', etc, so to_array seems to be a better solution.

Now I believe foo NEAR bar should be just compiled to foo.pos > bar.pos - 100 and foo.pos < bar.pos + 100, suppose NEAR means pos within 100. Why not.

[cpegeric]

I changed my mind on the design.

1. For large data scale, we need a hashtable with spill (do we have it?)
2. For OR operation,

• ignore Position
• minimize the memory footprint in hashtable say, 3 words in Search ["hello", "happy", "world"] with internal index [0, 1, 2],
  The result from multiple words in SQL group by doc_id into single row with an []uint8 value which store the document count of the word w1 present in a row.
  say doc_id=1 contains words "hello", "world". Two rows from SQL [{0, doc_id("hello")}, {2, doc_id("world")}] and will aggregate into a uint8 array is [1, 0, 1] and the Hashtable definition is map[doc_id][]uint8. This will minimize the hashtable size and []uint8 is simillar to vector which can evaluate the score by each vector instead of batch. This new GROUP BY operation is done in table function. Maybe it is good to implement in query engine?

3. For AND operation (phrase search), use JOIN and filtering with position to do phrase search. We will have answer immediately from SQL.

[cpegeric]

Even worse with SELECt UNION, ERROR 20101 (HY000): internal error: mpool memory allocation exceed limit with requested size 1147486208

SELECT doc_id from table where word in (w1, ...wn) has smaller memory footprint.

[Ariznawlll]

testing

[Ariznawlll]

commit: 2b6ab7e
测试步骤：

1、load 100g tpch data to mo
2、set experimental_fulltext_index=1;
create fulltext index fdx on lineitem(L_COMMENT)
3、select * from lineitem where match(l_comment) against('"olphins nag slyly after the regular packa"' in boolean mode);

本地测试通过