[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16912715#comment-16912715 ] Stamatis Zampetakis commented on CALCITE-2979: -- I also had a look in the PR sometime ago and it was in good shape so +1 for pushing this to 1.21.0. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance, pull-request-available > Time Spent: 2h 20m > Remaining Estimate: 0h > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian Jira (v8.3.2#803003)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16912517#comment-16912517 ] Julian Hyde commented on CALCITE-2979: -- +1 > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance, pull-request-available > Time Spent: 2h 20m > Remaining Estimate: 0h > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian Jira (v8.3.2#803003)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16912315#comment-16912315 ] Ruben Quesada Lopez commented on CALCITE-2979: -- Hi everyone, I think the PR is in a pretty good shape, if anyone has the opportunity to take a look at it, it will be very helpful. In any case, I believe we can safely push this into 1.21; even though this is a "brand new" join implementation, the risk is very limited since the new rule that generates the batch nested loop operator is not part of the "default" Calcite rule set, so this change should not break anything. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance, pull-request-available > Time Spent: 2h 20m > Remaining Estimate: 0h > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian Jira (v8.3.2#803003)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16848539#comment-16848539 ] Stamatis Zampetakis commented on CALCITE-2979: -- Hey [~danny0405], can you explain why you think that correlated variables cannot be pushed down? It seems that you have though of a problem but I am not sure what this is. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16848331#comment-16848331 ] Danny Chan commented on CALCITE-2979: - Thanks for your kindly sharing [~zabetak], it helps a lot. But for this issue case, do you think the multiple correlate variables can be push down ? How can that happen ? > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16848204#comment-16848204 ] Stamatis Zampetakis commented on CALCITE-2979: -- The technique/algorithms that are discussed here can be found with many names and variations. Some common ways to refer to these algorithms are [selective join pushdown|http://www.vldb.org/pvldb/vol12/p502-lang.pdf], Batched Key Access Joins, Bloom Joins, Bind Joins, Magic Sets and they fall into the more general problem usually referred as [sideways information passing|https://repository.upenn.edu/cgi/viewcontent.cgi?article=1045=db_research]. The join inputs do not need to be only TableScan operators. The filter that is generated in the left/right side can be pushed down (as any other filter) passing through other operators (joins, etc.) and eventually be combined with the TableScan. Even if it cannot be combined in the TableScan it can still help improving the performance of the query. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16848052#comment-16848052 ] Danny Chan commented on CALCITE-2979: - I have a question here, how about if the join inputs are not TableScan but some other nodes, say, an agg or another join, the proposals above seems not to work any more ? Correctly me if i'm wrong. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16848051#comment-16848051 ] Danny Chan commented on CALCITE-2979: - The runtime filter kind of has the same purpose to promote join efficiency. [1] While this issue aims to reduce the scan times. Runtime filter aims to reduce the total data that needed scan. Do we need to support runtime filters for hash join in Calcite ? [1] [https://www.cloudera.com/documentation/enterprise/5-9-x/topics/impala_runtime_filtering.html] > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16846227#comment-16846227 ] Julian Hyde commented on CALCITE-2979: -- By 'assigning keys to batches' I meant deciding when you have enough keys in a batch that it is worthwhile making a round-trip. [~zabetak] described a strategy using BLK_SIZE. Let's BLK_SIZE is 1000. Then the first batch will consist of key 0 through key 999. The second batch will consist of key 1000 through key 1999. But it's not the only possible strategy for assigning keys to batches. Let's suppose that the keys are date values, and you are probing into a table that is partitioned by month. You could construct batches that contain all keys that fall within a particular month, and therefore you would make at most one round-trip to each partition. Other strategies are possible, if you generalize away from using fixed size batches with BLK_SIZE entires. I will note that what you are doing is a form of work scheduling. (Fetching a row that corresponds to a particular key is an item of work, and of course grouping work items into batches is a well-known way to increase efficiency by trading off latency.) There are many strategies for work scheduling, such as [round-robin|https://en.wikipedia.org/wiki/Round-robin_scheduling]. Some of those strategies could be considered here. Schedulers often distribute work via queues, and I have a feeling that queues could be useful in this algorithm, too. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16845723#comment-16845723 ] Khawla Mouhoubi commented on CALCITE-2979: -- Thank you for your comments. [~sereda] the order will most likely be based on the size of the tables, the smaller one being the outer table. For the teminology Batch will be used in the code. [~julianhyde] can you please clarify what you mean by assigning keys to batches? > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16845257#comment-16845257 ] Julian Hyde commented on CALCITE-2979: -- No objections from me to adding a new operator implementation. I will be curious to see what strategy (or strategies) you use to assign keys to batches. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16844977#comment-16844977
]
Andrei Sereda commented on CALCITE-2979:
Thanks for starting this conversation. I have some questions:
1. How would the order of {{Scan(A)}} and {{Scan(B)}} be decided in nested loop
(for inner join) ?
2. Nomenclature proposal (minor). I'd favor term {{batch}} instead of
{{block}}.
{{batchSize}} / {{batch access}} sound more familiar to me than block. Perhaps
block is more used in research ?
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Assignee: Khawla Mouhoubi
>Priority: Major
> Labels: performance
>
> Currently, Calcite provides a tuple-based nested loop join algorithm
> implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16844641#comment-16844641
]
Khawla Mouhoubi commented on CALCITE-2979:
--
After discussing the matter with [~zabetak] and [~rubenql], a good way to start
would be implementing a block based version of the
EnumerableDefaults.correlateJoin or EnumerableDefaults.thetaJoin. There needs
to be a new operator which implementation will be close to EnumerableCorrelate
but with blocks of correlation variables and bloom filters applied to the inner
table. A new rule will do the following:
{code:java}
Join(A.id = B.id)
Scan(A)
Scan(B){code}
Will be turned into:
{code:java}
NestedLoop(blockSize=3)
Scan(A)
Filter(OR(=(cor0[0],B.id), =(cor0[1],B.id), =(cor0[2],B.id))
Scan(B)
{code}
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Assignee: Khawla Mouhoubi
>Priority: Major
> Labels: performance
>
> Currently, Calcite provides a tuple-based nested loop join algorithm
> implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16843147#comment-16843147 ] Stamatis Zampetakis commented on CALCITE-2979: -- MySQL is doing a similar thing to what we want to achieve through what they call [Batched Key Access Joins|https://dev.mysql.com/doc/refman/5.6/en/bnl-bka-optimization.html#bka-optimization]. Maybe it is worth looking a bit. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16842148#comment-16842148
]
Khawla Mouhoubi commented on CALCITE-2979:
--
I mean keeping current implementation (simple nested loop) for INNER and LEFT
join.
{code:java}
// correlateJoin pseudo code
if joinType == SEMI/ANTI
blockBasedNL()
else // for INNER and LEFT
nestedLoop()
{code}
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Assignee: Khawla Mouhoubi
>Priority: Major
> Labels: performance
>
> Currently, Calcite provides a tuple-based nested loop join algorithm
> implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16842141#comment-16842141 ] Stamatis Zampetakis commented on CALCITE-2979: -- Thanks for the analysis [~khawlamhb]! Can you clarify what do you mean by Method 3? > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16842061#comment-16842061
]
Khawla Mouhoubi commented on CALCITE-2979:
--
I don't see a common solution for all types of joins but rather different
strategies depending on the join type.
For SEMI and ANTI an idea would be reading blocks from the inner table and
applying a filter to the outer table, just like [~rubenql] mentionned. These
two steps are enough since we do not need to keep data from inner table.
Drawback would be duplicates. How to handle duplicates is yet to be studied.
For INNER and LEFT join I see three options:
# Read blocks from the outer table and filter the inner one. In order to know
which correlation variable matched, return every correlation variable with
every tuple from the filtered inner table. Then apply another filter to get
only tuples where the correlation variable matches. Something like that:
{code:java}
// select * from books join author on books.fk = author.id
Filter(books.fk = author.id)
SimpleBlockCorrelate() // might generate false results, to be filtered by
above filter
Scan(author)
Filter(OR(=(cor0,book.fk), =(cor1,book.fk), =(cor2,book.fk))
Scan(book)
{code}
# Read blocks from the outer table and filter the inner table. Then filter the
block with each tuple from the filtered inner relation. Something like that:
{code:java}
// select * from books join author on books.fk = author.id
BlockCorrelate(condition: books.fk = author.id)
Scan(author)
Filter(OR(=(cor0,book.fk), =(cor1,book.fk), =(cor2,book.fk))
Scan(book)
// pseudo-code for block based NL
for corrVars in getBlockFromOuterEnumerable()
innerEnumerable = inner.apply(corrVars)
for inner in innerEnumerable
// Filter correlation variables
for cV in corrVars
if cV matches inner
// cV + inner is a result
{code}
So basically the two last steps (SimpleBlockCorrelate & Filter) of the previous
plan are merged into the BlockCorrelate.
# Keep current NL.
Advantages & drawbacks of each strategy:
|| ||Method 1||Method 2||Method 3||
||Description|Filter inner table with a block of correlation variables,
projecting each corr var with each tuple from filtered
table, re-filtering|Filter inner table with a block of correlation variables,
filter the block with each tuple from filtered inner table|Keep current NL|
||Advantages| Less scans than NL
New algorithm rather straightforward|Less scans than NL
BlockCorrelate only generate correct results| Keeps order|
||Drawbacks| SimpleBlockCorrelate generates false results
Doesn't keep order| Doesn't keep order
New algorithm not trivial| No improvement |
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Assignee: Khawla Mouhoubi
>Priority: Major
> Labels: performance
>
> Currently, Calcite provides a tuple-based nested loop join algorithm
> implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16840343#comment-16840343 ] Danny Chan commented on CALCITE-2979: - It kind of have same thoughts as [~rubenql], let's make agreement that Correlated variables are kind of "Columns" of the left table, but from this design, it seems that the Correlated variables are multiple "Column" from left table which comes to a component. We actually could not expression such a logic from the plan. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16839555#comment-16839555 ] Ruben Quesada Lopez commented on CALCITE-2979: -- Thanks for your answer [~zabetak]! I agree, that kind of solution should work fine with a correlated INNER join (though it would not be applicable for SEMI / ANTI, and I'm not quite sure about the LEFT). Anyway, let us wait until [~khawlamhb] shares with the rest of us her study on this subject :) > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Khawla Mouhoubi >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16839542#comment-16839542
]
Stamatis Zampetakis commented on CALCITE-2979:
--
Thanks for the analysis [~rubenql]!
I haven't figured out all the details of what is the best way to do it and I
guess there is not only one choice. It would be nice if [~khawlamhb], who is
working on it right now, outlines some possible alternatives with
advantages/disadvantages. Just a quick thought (that I guess could work) would
be to generate a plan like the following:
{noformat}
Filter(A.id > B.id)
Correlate(blockSize=3)
Scan(A)
Filter(OR(>(cor0_0,B.id), >(cor0_1,B.id), >(cor0_2,B.id))
Scan(B)
{noformat}
so the implementation of correlate basically does a cartesian product and the
filter on top eliminates the tuples that shouldn't be there.
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Assignee: Khawla Mouhoubi
>Priority: Major
> Labels: performance
>
> Currently, Calcite provides a tuple-based nested loop join algorithm
> implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16839358#comment-16839358
]
Ruben Quesada Lopez commented on CALCITE-2979:
--
[~zabetak], I have a general question regarding the design of this new
block-based nested loop join algorithm. Let use say that the plan that you just
wrote in your last comment implements an inner join:
{code}
Join(A.id > B.id; type=INNER)
Scan(A)
Scan(B)
==>
NestedLoop(blockSize=3)
Scan(A)
ElasticScan(table=B, query="OR(>(cor0[0],B.id), >(cor0[1],B.id),
>(cor0[2],B.id)")
{code}
The result of the NestedLoop operator must contain a tupleA concatenated with a
tupleB that match. If we have a block of correlated variables, and we translate
the join condition as a filter with an OR conditions, we would get the
appropriate tupleB, but how does the NestedLoop know with which tuple(s) from A
it must be concatenated. We know for sure that the tupleB match with cor0[0] or
cor0[1] or cor0[2], but which one(s) exactly? Maybe I'm missing something, but
this information will not be available from NestedLoop perspective.
The only scenario that I can think of where this strategy could work is a
correlated SEMI (or ANTI) join, because only the left part is returned after
the first match (or no match at all) with the right part, and we do not care
which exact tuple from B matched. But in order to implement such strategy, we
would to inverse the correlated variable logic, and set it from right to left
(instead of left to right):
{code}
-- fetch the depts with at least one emp
Join (dept.id=emp.dptoId, type=SEMI)
Scan (dept)
Scan (emp)
==>
NestedLoop(blockSize=3, $cor0=emp)
Filter( OR( =(cor0[0].dptId, dept.id), =(cor0[1].dptId, dept.id),
=(cor0[2].dptId, dept.id) )
Scan(dept)
Scan(emp)
==>
NestedLoop(blockSize=3, $cor0=emp)
ElasticScan(table=dept, query="OR( =(cor0[0].dptId, dept.id),
=(cor0[1].dptId, dept.id), =(cor0[2].dptId, dept.id)" )
Scan(emp)
{code}
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Assignee: Khawla Mouhoubi
>Priority: Major
> Labels: performance
>
> Currently, Calcite provides a tuple-based nested loop join algorithm
> implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16810739#comment-16810739
]
Stamatis Zampetakis commented on CALCITE-2979:
--
Arrow format would be great and I would like to work on it in the future but is
not directly related to the problem that I am trying to solve right now. As
[~sereda] , correctly guessed Scan(B) is an external source which is not
necessarily in Arrow convention. I would like to match Filter + Scan(B) and
generate for example the following plan
{noformat}
NestedLoop(blockSize=3)
Scan(A)
ElasticScan(table=B, query="OR(>(cor0[0],B.id), >(cor0[1],B.id),
>(cor0[2],B.id)")
{noformat}
that way instead of sending one query to Elastic for each tuple in A, I divide
the number of queries to |A|/|BLK_SIZE|.
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Assignee: Stamatis Zampetakis
>Priority: Major
> Labels: performance
>
> Currently, Calcite provides a tuple-based nested loop join algorithm
> implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16810445#comment-16810445 ] Andrei Sereda commented on CALCITE-2979: [~julianhyde] agree that Arrow format will be more efficient but what to do when not all data is in memory ? I'm thinking about the case when Scan(B) (without Filter) involves fetching data from external source (eg. elasticsearch). Related discussion on [dev list|https://lists.apache.org/thread.html/bdd9f79c6d08b406881c1cfaabc9ba84369ca0e73010257252bb0e40@%3Cdev.calcite.apache.org%3E]. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Stamatis Zampetakis >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[ https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16810178#comment-16810178 ] Julian Hyde commented on CALCITE-2979: -- I think that enumerable convention sucks for high-performance. I would love to have a new convention that generates code to works on buffers of records in Arrow format. Then all operations, including nested loop join, would naturally work on batches of records. For many reasons, this is much more efficient - I would claim close to optimal - on modern hardware. > Add a block-based nested loop join algorithm > > > Key: CALCITE-2979 > URL: https://issues.apache.org/jira/browse/CALCITE-2979 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.19.0 >Reporter: Stamatis Zampetakis >Assignee: Stamatis Zampetakis >Priority: Major > Labels: performance > > Currently, Calcite provides a tuple-based nested loop join algorithm > implemented through EnumerableCorrelate and EnumerableDefaults.correlateJoin. > This means that for each tuple of the outer relation we probe (set variables) > in the inner relation. > The goal of this issue is to add new algorithm (or extend the correlateJoin > method) which first gathers blocks (batches) of tuples from the outer > relation and then probes the inner relation once per block. > There are cases (eg., indexes) where the inner relation can be accessed by > more than one value which can greatly improve the performance in particular > when the outer relation is big. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2979) Add a block-based nested loop join algorithm
[
https://issues.apache.org/jira/browse/CALCITE-2979?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16809884#comment-16809884
]
Stamatis Zampetakis commented on CALCITE-2979:
--
Implementation wise the first idea that comes to my mind is very similar to how
the current single value implementation works. Instead of creating a filter
with one correlated variable on the right side, we should create a filter with
either:
* BLK_SIZE correlated variables;
* a single correlated variable of ARRAY type and BLK_SIZE;
that are combined with an OR predicate with BLK_SIZE disjunctions.
For example, starting with the following pseudo-plan:
{noformat}
Join(A.id > B.id)
Scan(A)
Scan(B)
{noformat}
the rules should generate something like the plans below:
{noformat}
NestedLoop(blockSize=3)
Scan(A)
Filter(OR(>(cor0_0,B.id), >(cor0_1,B.id), >(cor0_2,B.id))
Scan(B)
{noformat}
or
{noformat}
NestedLoop(blockSize=3)
Scan(A)
Filter(OR(>(cor0[0],B.id), >(cor0[1],B.id), >(cor0[2],B.id))
Scan(B)
{noformat}
which the implementation of Correlate(blockSize=3) should take into account.
> Add a block-based nested loop join algorithm
>
>
> Key: CALCITE-2979
> URL: https://issues.apache.org/jira/browse/CALCITE-2979
> Project: Calcite
> Issue Type: Improvement
> Components: core
>Affects Versions: 1.19.0
>Reporter: Stamatis Zampetakis
>Priority: Major
> Labels: performance
>
> Currently Calcite provides a tuple-based nested loop join algorithm
> implmented through EnumerableCorrelate and EnumerableDefaults.correlateJoin.
> This means that for each tuple of the outer relation we probe (set variables)
> in the inner relation.
> The goal of this issue is to add new algorithm (or extend the correlateJoin
> method) which first gathers blocks (batches) of tuples from the outer
> relation and then probes the inner relation once per block.
> There are cases (eg., indexes) where the inner relation can be accessed by
> more than one value which can greatly improve the performance in particular
> when the outer relation is big.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
