[jira] [Commented] (KYLIN-4810) TrieDictionary is not correctly build

["ASF GitHub Bot (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/KYLIN-4810?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17229844#comment-17229844 ] 

ASF GitHub Bot commented on KYLIN-4810:
---------------------------------------

zhengshengjun opened a new pull request #1477:
URL: https://github.com/apache/kylin/pull/1477


   ## Proposed changes
   
   Fix the problem of dictionary build error when encountering large values,  related issue link: https://issues.apache.org/jira/browse/KYLIN-4810
   
   ## Types of changes
   
   What types of changes does your code introduce to Kylin?
   _Put an `x` in the boxes that apply_
   
   - [x] Bugfix (non-breaking change which fixes an issue)
   - [ ] New feature (non-breaking change which adds functionality)
   - [ ] Breaking change (fix or feature that would cause existing functionality to not work as expected)
   - [ ] Documentation Update (if none of the other choices apply)
   
   ## Checklist
   
   _Put an `x` in the boxes that apply. You can also fill these out after creating the PR. If you're unsure about any of them, don't hesitate to ask. We're here to help! This is simply a reminder of what we are going to look for before merging your code._
   
   - [x] I have create an issue on [Kylin's jira](https://issues.apache.org/jira/browse/KYLIN), and have described the bug/feature there in detail
   - [ ] Commit messages in my PR start with the related jira ID, like "KYLIN-0000 Make Kylin project open-source"
   - [x] Compiling and unit tests pass locally with my changes
   - [ ] I have added tests that prove my fix is effective or that my feature works
   - [ ] If this change need a document change, I will prepare another pr against the `document` branch
   - [ ] Any dependent changes have been merged
   
   ## Further comments
   
   If this is a relatively large or complex change, kick off the discussion at user@kylin or dev@kylin by explaining why you chose the solution you did and what alternatives you considered, etc...
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


> TrieDictionary is not correctly build
> -------------------------------------
>
>                 Key: KYLIN-4810
>                 URL: https://issues.apache.org/jira/browse/KYLIN-4810
>             Project: Kylin
>          Issue Type: Bug
>          Components: Job Engine
>    Affects Versions: v2.3.2
>            Reporter: ShengJun Zheng
>            Priority: Critical
>             Fix For: Future
>
>
> Hi, recently, I've met a problem in our product environment: Segments failed to merge because TrieDictionaryForest was disordered
> {code:java}
> java.lang.IllegalStateException: Invalid input data. Unordered data cannot be split into multi trees
>     at org.apache.kylin.dict.TrieDictionaryForestBuilder.addValue(TrieDictionaryForestBuilder.java:92)
>     at org.apache.kylin.dict.TrieDictionaryForestBuilder.addValue(TrieDictionaryForestBuilder.java:78)
>     at org.apache.kylin.dict.DictionaryGenerator$StringTrieDictForestBuilder.addValue(DictionaryGenerator.java:214)
>     at org.apache.kylin.dict.DictionaryGenerator.buildDictionary(DictionaryGenerator.java:81)
>     at org.apache.kylin.dict.DictionaryGenerator.buildDictionary(DictionaryGenerator.java:65)
>     at org.apache.kylin.dict.DictionaryGenerator.mergeDictionaries(DictionaryGenerator.java:106)
> {code}
> After some analysis, we found out when there is large values in a dict-encoded column, iterating over a single TrieDictionaryTree will get unordered data.
>  
>  Digging into the source code,  the root cause is as described: 
>  # Kylin will split a TrieTree Node into two parts when a single nodes's value length is more than 255 bytes
>  # Then, these tow parts of value will be added to build the TrieTree. In fact the splitted two parts should not be used as new values to add to the TrieTree.
>  # Step 2 will cause the TrieDictionaryTree build more leave nodes，and the extra leaf nodes will be 'end-value' of dictionary tree;
>  # It has no impact to the correctness of the dict tree itself, except for adding some additional nodes .
>  # But If you spit a UTF-8 word, you will get unordered data when iterating over the tree ( Something todo with Java UTF-8  String Serialize/Deserialize implementations. Please Refer to JDK sun.nio.cs.UTF_8.class)
> How to re-produce ? Run test code :
> {code:java}
> TrieDictionaryForestBuilder builder = new TrieDictionaryForestBuilder(new StringBytesConverter());
> String longUrl = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx你好~~~";
> builder.addValue(longUrl);
> TrieDictionaryForest<String> dict = builder.build();
> TrieDictionaryForestBuilder mergeBuild = new TrieDictionaryForestBuilder(new StringBytesConverter());
> for (int i = dict.getMinId(); i <= dict.getMaxId(); i++) {
>     String str = dict.getValueFromId(i);
>     System.out.println("add value into merge tree");
>     mergeBuild.addValue(str);
> }
> The log output of this test code is:
> add value into merge tree
> add value into merge tree
> 16:59:36 [main] INFO org.apache.kylin.dict.TrieDictionaryForestBuilder.addValue(TrieDictionaryForestBuilder.java:127) values not in ascending order, previous 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\xEF\xBF\xBD', current 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\xE4\xBD\xA0\xE5\xA5\xBD~~~'
> {code}
> We can see from the test code's output：
>  # We only add 1 value but the tire dictionary tree turn out to have 2 end vlaues
>  # Iterating over the TrieDictionary Tree got unordered data
> We address this problem by
>  # classify values which is a whole column value, which is splitted value,
>  # not mark splitted value as end-value of a TrieTree Node.
> I wonder if there is something wrong, thanks.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)