asterixdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yingyi Bu <buyin...@gmail.com>
Subject Re: [jira] [Commented] (ASTERIXDB-1249) Self index join chooses wrong probe/index branch
Date Mon, 11 Jan 2016 05:16:36 GMT
>> the role reversal happens locally in later iterations of the hash join,
right, based on the relative sizes of on-disk hash partitions?
That's right.

>>I think the key thing that we need to be consistent about is which is the
"basic" outer and inner
>> - which in the case of a parallel hash join would be which is the
initial build dataset and which is the initial probe dataset.
Got it!
Thanks!

Best,
Yingyi


On Sun, Jan 10, 2016 at 3:59 PM, Mike Carey <dtabass@gmail.com> wrote:

> Just to be (or get) clear - the role reversal happens locally in later
> iterations of the hash join, right, based on the relative sizes of on-disk
> hash partitions?  I think the key thing that we need to be consistent about
> is which is the "basic" outer and inner - which in the case of a parallel
> hash join would be which is the initial build dataset and which is the
> initial probe dataset.
>
>
> On 1/8/16 9:08 AM, Yingyi Bu wrote:
>
>> In left-outer hash join, if the the probe branch is locally clustered (or
>> sorted) by a column superset of the join key,
>> the output will still be locally clustered.
>> Inner hash join couldn't maintain that because of the "role reversal"
>> optimization in the runtime.
>>
>> Best,
>> Yingyi
>>
>> On Thu, Jan 7, 2016 at 10:07 PM, Taewoo Kim <wangsaeu@gmail.com> wrote:
>>
>> Interesting. Can you be more specific?
>>>
>>> Best,
>>> Taewoo
>>>
>>> On Thu, Jan 7, 2016 at 6:36 PM, Yingyi Bu <buyingyi@gmail.com> wrote:
>>>
>>> Sorry, to be more precise:
>>>> Left-outer hash join cannot preserve all local data properties for its
>>>> probe branch (because spilling can happen) but can preserve (or
>>>>
>>> downgrade)
>>>
>>>> some when certain conditions meet.
>>>>
>>>> On Thu, Jan 7, 2016 at 6:28 PM, Yingyi Bu <buyingyi@gmail.com> wrote:
>>>>
>>>> In the logical/physical query plan, I think it is statically
>>>>>
>>>> determined.
>>>
>>>> However, that doesn't mean the execution is faithful to that
>>>>>
>>>> probe/build
>>>
>>>> decision because we have the "role reversal" optimization for inner
>>>>>
>>>> hash
>>>
>>>> joins:-)
>>>>> (That's also why our inner hash join cannot maintain any local data
>>>>> property from its probe branch, but left-outer hash can preserve that.)
>>>>>
>>>>> Best,
>>>>> Yingyi
>>>>>
>>>>>
>>>>> On Thu, Jan 7, 2016 at 5:34 PM, Mike Carey <dtabass@gmail.com>
wrote:
>>>>>
>>>>> Also, do we (separately want to make sure that our hash join behavior
>>>>>>
>>>>> is
>>>
>>>> comparable - i.e., that the initial build/probe decision is statically
>>>>>> determined from the query?  (I think we do want that, and I think
it
>>>>>>
>>>>> is
>>>
>>>> in
>>>>
>>>>> fact that way - but I'm not 100% sure, as its been awhile since that
>>>>>>
>>>>> was
>>>
>>>> discussed, and it's not in-cache for me. :-))
>>>>>>
>>>>>>
>>>>>> On 1/7/16 3:22 PM, Taewoo Kim wrote:
>>>>>>
>>>>>> Thanks Yingyi. Yes. If there is an equality condition and if we can't
>>>>>>> transform a join into an index-nested loop join, then a hybrid
hash
>>>>>>>
>>>>>> join
>>>>
>>>>> will be used.
>>>>>>>
>>>>>>> Best,
>>>>>>> Taewoo
>>>>>>>
>>>>>>> On Thu, Jan 7, 2016 at 3:14 PM, Yingyi Bu <buyingyi@gmail.com>
>>>>>>>
>>>>>> wrote:
>>>
>>>> +1!
>>>>>>>
>>>>>>>> 3. We only try to use applicable indexes from the inner branch.
So,
>>>>>>>>>
>>>>>>>> if
>>>>
>>>>> there are no applicable indexes from the inner branch, we abort
>>>>>>>>>> transforming a join into an index-nested-loop join.
>>>>>>>>>>
>>>>>>>>>> "index-nested-loop join" -> "hybrid hash join"?
>>>>>>>>>
>>>>>>>> Thanks!
>>>>>>>>
>>>>>>>> Yingyi
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Thu, Jan 7, 2016 at 3:01 PM, Taewoo Kim <wangsaeu@gmail.com>
>>>>>>>>
>>>>>>> wrote:
>>>>
>>>>> Hello dev,
>>>>>>>>
>>>>>>>>> Regarding this issue (ASTERIXDB-1249), I would like to
make an
>>>>>>>>> index-join
>>>>>>>>> hint clarification. Let's start with an example query
other than a
>>>>>>>>> self-join query in this issue.
>>>>>>>>>
>>>>>>>>> for $c in dataset('Customers')
>>>>>>>>>
>>>>>>>>> for $o in dataset('Orders')
>>>>>>>>>
>>>>>>>>> where $c.cid /*+ indexnl */ = $o.cid
>>>>>>>>>
>>>>>>>>> order by $c.cid, $o.oid
>>>>>>>>>
>>>>>>>>> return {"cid":$c.cid, "oid": $o.oid}
>>>>>>>>>
>>>>>>>>> Right now, in the master branch, the first dataset (e.g.,
>>>>>>>>>
>>>>>>>> Customers)
>>>
>>>> becomes the outer branch and the second dataset (e.g., Orders)
>>>>>>>>>
>>>>>>>> becomes
>>>>
>>>>> the
>>>>>>>>
>>>>>>>> inner branch. And, when the optimizer tries to honor the
given
>>>>>>>>>
>>>>>>>> indexnl
>>>>
>>>>> hint
>>>>>>>>
>>>>>>>> (transforming a join into an index-nested-loop join), if
there are
>>>>>>>>> applicable indexes from the inner branch (e.g., Orders),
then it is
>>>>>>>>> going
>>>>>>>>> to use one of those indexes. If there are no applicable
indexes
>>>>>>>>>
>>>>>>>> from
>>>
>>>> the
>>>>>>>>> inner branch, it tries to use indexes from the outer
branch (e.g.,
>>>>>>>>> Customers). We are going to change the last part; we
will not use
>>>>>>>>> indexes
>>>>>>>>> from the outer branch. So, the following are refined
rules for
>>>>>>>>>
>>>>>>>>> transforming
>>>>>>>>
>>>>>>>> a join into an index-nested-loop join.
>>>>>>>>>
>>>>>>>>> 1. The first dataset in a join (the first parameter of
the given
>>>>>>>>>
>>>>>>>> join)
>>>>
>>>>> becomes the outer branch.
>>>>>>>>> 2. The second dataset in a join (the second parameter
of the given
>>>>>>>>> join)
>>>>>>>>> becomes the inner branch.
>>>>>>>>> 3. We only try to use applicable indexes from the inner
branch. So,
>>>>>>>>>
>>>>>>>> if
>>>>
>>>>> there are no applicable indexes from the inner branch, we abort
>>>>>>>>> transforming a join into an index-nested-loop join.
>>>>>>>>> 4. Variable order in the given join predicate is not
important. It
>>>>>>>>>
>>>>>>>> can
>>>>
>>>>> be
>>>>>>>>> either outer.fieldA = inner.fieldB or inner.fieldB =
outer.fieldA.
>>>>>>>>>
>>>>>>>>> So, for the left-outer join and inner join altogether,
the left
>>>>>>>>>
>>>>>>>> subtree
>>>>
>>>>> is
>>>>>>>>
>>>>>>>> the probing side and the right subtree is the index side.
So, this
>>>>>>>>>
>>>>>>>> can
>>>>
>>>>> be
>>>>>>>>> applied to the self-join case, too just like the following
query in
>>>>>>>>> this
>>>>>>>>> issue. In the following query, $t1 becomes the outer
and $t2
>>>>>>>>>
>>>>>>>> becomes
>>>
>>>> the
>>>>>>>>> inner.
>>>>>>>>>
>>>>>>>>> for $t1 in dataset('TweetMessages')
>>>>>>>>>
>>>>>>>>> for $t2 in dataset('TweetMessages')
>>>>>>>>>
>>>>>>>>> let $c := $t1.countA + 20
>>>>>>>>>
>>>>>>>>> where $c /* +indexnl */= $t2.countB
>>>>>>>>>
>>>>>>>>> order by $t2.tweetid
>>>>>>>>>
>>>>>>>>> return {"tweetid2": $t2.tweetid, "count2":$t2.countB};
>>>>>>>>>
>>>>>>>>> Thank you. Any opinion would be appreciated before I
finalize this
>>>>>>>>>
>>>>>>>> fix.
>>>>
>>>>> Best,
>>>>>>>>> Taewoo
>>>>>>>>>
>>>>>>>>> ---------- Forwarded message ----------
>>>>>>>>> From: Yingyi Bu (JIRA) <jira@apache.org>
>>>>>>>>> Date: Wed, Jan 6, 2016 at 10:23 AM
>>>>>>>>> Subject: [jira] [Commented] (ASTERIXDB-1249) Self index
join
>>>>>>>>>
>>>>>>>> chooses
>>>
>>>> wrong
>>>>>>>>
>>>>>>>> probe/index branch
>>>>>>>>> To: notifications@asterixdb.incubator.apache.org
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>       [
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>> https://issues.apache.org/jira/browse/ASTERIXDB-1249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15085992#comment-15085992
>>>
>>>> ]
>>>>>>>>>
>>>>>>>>> Yingyi Bu commented on ASTERIXDB-1249:
>>>>>>>>> --------------------------------------
>>>>>>>>>
>>>>>>>>> That's right. Basically in AcessMethod implementations,
e.g.:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>> https://github.com/apache/incubator-asterixdb/blob/master/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/RTreeAccessMethod.java#L124
>>>
>>>> Choosing probe/index branch is only based on dataset names, instead
>>>>>>>>>
>>>>>>>> of
>>>>
>>>>> being based on the join condition.
>>>>>>>>>
>>>>>>>>> Self index join chooses wrong probe/index branch
>>>>>>>>>
>>>>>>>>>> ------------------------------------------------
>>>>>>>>>>
>>>>>>>>>>                   Key: ASTERIXDB-1249
>>>>>>>>>>                   URL:
>>>>>>>>>>
>>>>>>>>>> https://issues.apache.org/jira/browse/ASTERIXDB-1249
>>>>>>>>>
>>>>>>>>>               Project: Apache AsterixDB
>>>>>>>>>>            Issue Type: Bug
>>>>>>>>>>            Components: Optimizer
>>>>>>>>>>              Reporter: Yingyi Bu
>>>>>>>>>>              Assignee: Taewoo Kim
>>>>>>>>>>
>>>>>>>>>> DDLs:
>>>>>>>>>> {noformat}
>>>>>>>>>> drop dataverse test if exists;
>>>>>>>>>> create dataverse test;
>>>>>>>>>> use dataverse test;
>>>>>>>>>> create type TwitterUserType as closed {
>>>>>>>>>>       screen-name: string,
>>>>>>>>>>       lang: string,
>>>>>>>>>>       friends-count: int64,
>>>>>>>>>>       statuses-count: int64,
>>>>>>>>>>       name: string,
>>>>>>>>>>       followers-count: int64
>>>>>>>>>> }
>>>>>>>>>> create type TweetMessageType as closed {
>>>>>>>>>>       tweetid: int64,
>>>>>>>>>>           user: TwitterUserType,
>>>>>>>>>>           sender-location: point,
>>>>>>>>>>       send-time: datetime,
>>>>>>>>>>           referred-topics: {{ string }},
>>>>>>>>>>       message-text: string,
>>>>>>>>>>       countA: int64,
>>>>>>>>>>       countB: int64
>>>>>>>>>> }
>>>>>>>>>> create dataset TweetMessages(TweetMessageType)
>>>>>>>>>> primary key tweetid;
>>>>>>>>>> create index twmSndLocIx on TweetMessages(sender-location)
type
>>>>>>>>>>
>>>>>>>>> rtree;
>>>>
>>>>> create index msgCountAIx on TweetMessages(countA) type btree;
>>>>>>>>>> create index msgCountBIx on TweetMessages(countB)
type btree;
>>>>>>>>>> create index msgTextIx on TweetMessages(message-text)
type
>>>>>>>>>>
>>>>>>>>> keyword;
>>>
>>>> {noformat}
>>>>>>>>>> Query:
>>>>>>>>>> {noformat}
>>>>>>>>>> for $t1 in dataset('TweetMessages')
>>>>>>>>>> for $t2 in dataset('TweetMessages')
>>>>>>>>>> let $n :=  create-circle($t1.sender-location, 0.5)
>>>>>>>>>> where spatial-intersect($t2.sender-location, $n)
>>>>>>>>>> order by $t2.tweetid
>>>>>>>>>> return {"tweetid2":$t2.tweetid, "loc2":$t2.sender-location};
>>>>>>>>>> {noformat}
>>>>>>>>>> Optimized plan:
>>>>>>>>>> {noformat}
>>>>>>>>>> distribute result [%0->$$10]
>>>>>>>>>> -- DISTRIBUTE_RESULT  |PARTITIONED|
>>>>>>>>>>     exchange
>>>>>>>>>>     -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
>>>>>>>>>>       project ([$$10])
>>>>>>>>>>       -- STREAM_PROJECT  |PARTITIONED|
>>>>>>>>>>         assign [$$10] <- [function-call:
>>>>>>>>>>
>>>>>>>>>> asterix:closed-record-constructor,
>>>>>>>>> Args:[AString: {tweetid2}, %0->$$15, AString: {loc2},
%0->$$13]]
>>>>>>>>>
>>>>>>>>>         -- ASSIGN  |PARTITIONED|
>>>>>>>>>>           exchange
>>>>>>>>>>           -- SORT_MERGE_EXCHANGE [$$15(ASC) ]  |PARTITIONED|
>>>>>>>>>>             order (ASC, %0->$$15)
>>>>>>>>>>             -- STABLE_SORT [$$15(ASC)]  |PARTITIONED|
>>>>>>>>>>               exchange
>>>>>>>>>>               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
>>>>>>>>>>                 project ([$$13, $$15])
>>>>>>>>>>                 -- STREAM_PROJECT  |PARTITIONED|
>>>>>>>>>>                   select (function-call:
>>>>>>>>>> asterix:spatial-intersect,
>>>>>>>>>>
>>>>>>>>>> Args:[%0->$$13, function-call: asterix:create-circle,
>>>>>>>>>
>>>>>>>>> Args:[function-call:
>>>>>>>>
>>>>>>>> asterix:field-access-by-index, Args:[%0->$$0, AInt32:
{2}],
>>>>>>>>>
>>>>>>>> ADouble:
>>>
>>>> {0.5}]])
>>>>>>>>>
>>>>>>>>>                   -- STREAM_SELECT  |PARTITIONED|
>>>>>>>>>>                     project ([$$0, $$13, $$15])
>>>>>>>>>>                     -- STREAM_PROJECT  |PARTITIONED|
>>>>>>>>>>                       exchange
>>>>>>>>>>                       -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
>>>>>>>>>>                         unnest-map [$$14, $$0] <-
function-call:
>>>>>>>>>>
>>>>>>>>>> asterix:index-search, Args:[AString: {TweetMessages},
AInt32: {0},
>>>>>>>>>
>>>>>>>>> AString:
>>>>>>>>
>>>>>>>> {test}, AString: {TweetMessages}, ABoolean: {true}, ABoolean:
>>>>>>>>>
>>>>>>>> {false},
>>>>
>>>>> ABoolean: {false}, AInt32: {1}, %0->$$27, AInt32: {1}, %0->$$27,
>>>>>>>>>
>>>>>>>> TRUE,
>>>>
>>>>> TRUE, TRUE]
>>>>>>>>>
>>>>>>>>>                         -- BTREE_SEARCH  |PARTITIONED|
>>>>>>>>>>                           exchange
>>>>>>>>>>                           -- ONE_TO_ONE_EXCHANGE
 |PARTITIONED|
>>>>>>>>>>                             order (ASC, %0->$$27)
>>>>>>>>>>                             -- STABLE_SORT [$$27(ASC)]
>>>>>>>>>>
>>>>>>>>> |PARTITIONED|
>>>
>>>>                               exchange
>>>>>>>>>>                               -- ONE_TO_ONE_EXCHANGE
>>>>>>>>>> |PARTITIONED|
>>>>>>>>>>                                 project ([$$27, $$13,
$$15])
>>>>>>>>>>                                 -- STREAM_PROJECT
 |PARTITIONED|
>>>>>>>>>>                                   exchange
>>>>>>>>>>                                   -- ONE_TO_ONE_EXCHANGE
>>>>>>>>>>
>>>>>>>>> |PARTITIONED|
>>>>
>>>>>                                     unnest-map [$$23, $$24, $$25,
>>>>>>>>>>
>>>>>>>>> $$26,
>>>>
>>>>> $$27] <- function-call: asterix:index-search, Args:[AString:
>>>>>>>>>
>>>>>>>>> {twmSndLocIx},
>>>>>>>>
>>>>>>>> AInt32: {1}, AString: {test}, AString: {TweetMessages}, ABoolean:
>>>>>>>>> {true},
>>>>>>>>> ABoolean: {false}, ABoolean: {true}, AInt32: {4}, %0->$$19,
>>>>>>>>>
>>>>>>>> %0->$$20,
>>>
>>>> %0->$$21, %0->$$22]
>>>>>>>>>
>>>>>>>>>                                     -- RTREE_SEARCH 
|PARTITIONED|
>>>>>>>>>>                                       exchange
>>>>>>>>>>                                       -- BROADCAST_EXCHANGE
>>>>>>>>>>
>>>>>>>>>> |PARTITIONED|
>>>>>>>>>                                         assign [$$19,
$$20, $$21,
>>>>>>>>>
>>>>>>>> $$22]
>>>>
>>>>> <-
>>>>>>>>> [function-call: asterix:create-mbr, Args:[%0->$$13,
AInt32: {2},
>>>>>>>>> AInt32:
>>>>>>>>> {0}], function-call: asterix:create-mbr, Args:[%0->$$13,
AInt32:
>>>>>>>>>
>>>>>>>> {2},
>>>
>>>> AInt32: {1}], function-call: asterix:create-mbr, Args:[%0->$$13,
>>>>>>>>> AInt32:
>>>>>>>>> {2}, AInt32: {2}], function-call: asterix:create-mbr,
>>>>>>>>>
>>>>>>>> Args:[%0->$$13,
>>>
>>>> AInt32: {2}, AInt32: {3}]]
>>>>>>>>>
>>>>>>>>>                                         -- ASSIGN  |PARTITIONED|
>>>>>>>>>>                                           project
([$$13, $$15])
>>>>>>>>>>                                           -- STREAM_PROJECT
>>>>>>>>>>
>>>>>>>>>> |PARTITIONED|
>>>>>>>>>                                             assign [$$13]
<-
>>>>>>>>> [function-call: asterix:field-access-by-index, Args:[%0->$$1,
>>>>>>>>>
>>>>>>>> AInt32:
>>>
>>>> {2}]]
>>>>>>>>
>>>>>>>>                                             -- ASSIGN  |PARTITIONED|
>>>>>>>>>
>>>>>>>>>>                                               exchange
>>>>>>>>>>                                               --
>>>>>>>>>>
>>>>>>>>> ONE_TO_ONE_EXCHANGE
>>>
>>>> |PARTITIONED|
>>>>>>>>>
>>>>>>>>>                                                 data-scan
>>>>>>>>>>
>>>>>>>>> []<-[$$15,
>>>
>>>> $$1]
>>>>>>>>>>
>>>>>>>>>> <- test:TweetMessages
>>>>>>>>>
>>>>>>>>>                                                 -- DATASOURCE_SCAN
>>>>>>>>>>
>>>>>>>>>> |PARTITIONED|
>>>>>>>>>
>>>>>>>>>                                                   exchange
>>>>>>>>>>                                                 
 --
>>>>>>>>>> ONE_TO_ONE_EXCHANGE
>>>>>>>>>>
>>>>>>>>>> |PARTITIONED|
>>>>>>>>>
>>>>>>>>> empty-tuple-source
>>>>
>>>>>                                                     --
>>>>>>>>>> EMPTY_TUPLE_SOURCE
>>>>>>>>>>
>>>>>>>>>> |PARTITIONED|
>>>>>>>>>
>>>>>>>>> {noformat}
>>>>>>>>>> The optimized plan is incorrect --- the index search
doesn't use
>>>>>>>>>>
>>>>>>>>> the
>>>
>>>> right join condition and hence the result is different from
>>>>>>>>>
>>>>>>>> expected.
>>>
>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> This message was sent by Atlassian JIRA
>>>>>>>>> (v6.3.4#6332)
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message