You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@spark.apache.org by "Wan Kun (Jira)" <ji...@apache.org> on 2022/02/17 09:16:00 UTC

[jira] [Updated] (SPARK-38238) Contains Join for Spark SQL

     [ https://issues.apache.org/jira/browse/SPARK-38238?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Wan Kun updated SPARK-38238:
----------------------------
    Description: 
Currently Spark SQL uses a Broadcast Nested Loop join when it has to execute the following string contains query:
{code:sql}
SELECT a.text, b.pattern
FROM fact_table a
JOIN patterns b
ON a.text like concat('%', b.pattern, '%');
{code}
OR
{code:sql}
SELECT a.text, b.pattern
FROM fact_table a
JOIN patterns b
ON position(b.pattern, a.text) > 0;
{code}

If there are many patterns to match in the left table, the query many execute for a long time.

Actually this join is called *Multi-Pattern String Matching* or *Multi-Way String Matching*, and many algorithm trying to improve this matching. One of  the famous algorithm called [*Aho–Corasick algorithm*|https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm]

The basic idea to optimize this query is to transform all the patterns into a trie tree and broadcast it. So then each row from the left table only need to match its content to the trie tree once. 


  was:
Currently Spark SQL uses a Broadcast Nested Loop join when it has to execute the following string contains query:
{code:sql}
SELECT a.text, b.pattern
FROM emails a
JOIN patterns b
ON a.text like concat('%', b.pattern, '%');
{code}
OR
{code:sql}
SELECT a.text, b.pattern
FROM emails a
JOIN patterns b
ON position(b.pattern, a.text) > 0;
{code}

If there are many patterns to match in the left table, the query many execute for a long time.

Actually this join is called *Multi-Pattern String Matching* or *Multi-Way String Matching*, and many algorithm trying to improve this matching. One of  the famous algorithm called [*Aho–Corasick algorithm*|https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm]

The basic idea to optimize this query is to transform all the patterns into a trie tree and broadcast it. So then each row from the left table only need to match its content to the trie tree once. 



> Contains Join for Spark SQL
> ---------------------------
>
>                 Key: SPARK-38238
>                 URL: https://issues.apache.org/jira/browse/SPARK-38238
>             Project: Spark
>          Issue Type: Bug
>          Components: SQL
>    Affects Versions: 3.3.0
>            Reporter: Wan Kun
>            Priority: Major
>
> Currently Spark SQL uses a Broadcast Nested Loop join when it has to execute the following string contains query:
> {code:sql}
> SELECT a.text, b.pattern
> FROM fact_table a
> JOIN patterns b
> ON a.text like concat('%', b.pattern, '%');
> {code}
> OR
> {code:sql}
> SELECT a.text, b.pattern
> FROM fact_table a
> JOIN patterns b
> ON position(b.pattern, a.text) > 0;
> {code}
> If there are many patterns to match in the left table, the query many execute for a long time.
> Actually this join is called *Multi-Pattern String Matching* or *Multi-Way String Matching*, and many algorithm trying to improve this matching. One of  the famous algorithm called [*Aho–Corasick algorithm*|https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm]
> The basic idea to optimize this query is to transform all the patterns into a trie tree and broadcast it. So then each row from the left table only need to match its content to the trie tree once. 



--
This message was sent by Atlassian Jira
(v8.20.1#820001)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org