Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-8623

Decrease I/O pressure when merging high dimensional points

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 7.7, 8.0, 9.0
    • None
    • None
    • New

    Description

      Related with LUCENE-8619, after indexing 60 million shapes(~1.65 billion triangles) using LatLonShape, the index directory grew to a size of 265 GB when performing merging of different segments. After the processes were over the index size was 57 GB.

      As an example imagine we are merging several segments to a new segment of size 10GB (4 dimensions). The BKD tree merging logic will create the following files:

      1) Level 0: 4 copies of the data, each one sorted by one dimensions : 40GB

      2) Level 1: 6 copies of half of the data, left and right : 30GB

      3) Level 2: 6 copies of one quarter of the data, left and right : 15 GB

      4) Level 3: 6 more copies halving the previous level, left and right : 7.5 GB

      5) Level 4: 6 more copies halving the previous level, left and right : 3.75 GB

       

      and so on... So it requires around 100GB to merge that segment. 

      In this issue is proposed to delay the creation of sorted copies to when they are needed. It reduces the total size required to half of what it is needed now. 

       

       

       

      Attachments

        1. LUCENE-8623.patch
          12 kB
          Ignacio Vera
        2. LUCENE-8623.patch
          13 kB
          Ignacio Vera
        3. LUCENE-8623.patch
          14 kB
          Ignacio Vera
        4. LUCENE-8623.patch
          16 kB
          Ignacio Vera
        5. LatLonShape.png
          9 kB
          Ignacio Vera
        6. LatLonPoint.png
          8 kB
          Ignacio Vera
        7. Geo3D.png
          8 kB
          Ignacio Vera

        Activity

          ivera Ignacio Vera added a comment -

          Attached this new approach. I ran the GeoBenches with this new approach with the following results for indexing speed:

          Approach Index time (sec) Force merge time (sec) Index size (GB) Reader heap (MB)

                    ||Dev||Base||Diff ||Dev  ||Base  ||diff   ||Dev||Base||Diff||Dev||Base||Diff ||

          points 237.0s 229.9s 3% 0.0s 0.0s 0% 0.51 0.51 0% 1.72 1.72 0%
          geo3d 401.3s 402.4s -0% 0.0s 0.0s 0% 0.71 0.71 0% 1.75 1.75 0%
          shapes 664.6s 798.4s -17% 0.0s 0.0s 0% 1.28 1.28 0% 1.77 1.77 0%

           

          This approach slows down when having just two dimensions but just slightly.

           

          ivera Ignacio Vera added a comment - Attached this new approach. I ran the GeoBenches with this new approach with the following results for indexing speed: Approach Index time (sec) Force merge time (sec) Index size (GB) Reader heap (MB)           ||Dev||Base||Diff ||Dev  ||Base  ||diff   ||Dev||Base||Diff||Dev||Base||Diff || points 237.0s 229.9s 3% 0.0s 0.0s 0% 0.51 0.51 0% 1.72 1.72 0% geo3d 401.3s 402.4s -0% 0.0s 0.0s 0% 0.71 0.71 0% 1.75 1.75 0% shapes 664.6s 798.4s -17% 0.0s 0.0s 0% 1.28 1.28 0% 1.77 1.77 0%   This approach slows down when having just two dimensions but just slightly.  
          lucenesolrqa Lucene/Solr QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
                Prechecks
          -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.
                master Compile Tests
          +1 compile 0m 45s master passed
                Patch Compile Tests
          +1 compile 0m 20s the patch passed
          +1 javac 0m 20s the patch passed
          +1 Release audit (RAT) 0m 20s the patch passed
          +1 Check forbidden APIs 0m 20s the patch passed
          +1 Validate source patterns 0m 20s the patch passed
                Other Tests
          +1 unit 29m 11s core in the patch passed.
          34m 57s



          Subsystem Report/Notes
          JIRA Issue LUCENE-8623
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12953120/LUCENE-8623.patch
          Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns
          uname Linux lucene2-us-west.apache.org 4.4.0-112-generic #135-Ubuntu SMP Fri Jan 19 11:48:36 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
          Build tool ant
          Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh
          git revision master / 106d300
          ant version: Apache Ant(TM) version 1.9.6 compiled on July 20 2018
          Default Java 1.8.0_191
          Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/143/testReport/
          modules C: lucene/core U: lucene/core
          Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/143/console
          Powered by Apache Yetus 0.7.0 http://yetus.apache.org

          This message was automatically generated.

          lucenesolrqa Lucene/Solr QA added a comment - -1 overall Vote Subsystem Runtime Comment       Prechecks -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.       master Compile Tests +1 compile 0m 45s master passed       Patch Compile Tests +1 compile 0m 20s the patch passed +1 javac 0m 20s the patch passed +1 Release audit (RAT) 0m 20s the patch passed +1 Check forbidden APIs 0m 20s the patch passed +1 Validate source patterns 0m 20s the patch passed       Other Tests +1 unit 29m 11s core in the patch passed. 34m 57s Subsystem Report/Notes JIRA Issue LUCENE-8623 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12953120/LUCENE-8623.patch Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns uname Linux lucene2-us-west.apache.org 4.4.0-112-generic #135-Ubuntu SMP Fri Jan 19 11:48:36 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux Build tool ant Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh git revision master / 106d300 ant version: Apache Ant(TM) version 1.9.6 compiled on July 20 2018 Default Java 1.8.0_191 Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/143/testReport/ modules C: lucene/core U: lucene/core Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/143/console Powered by Apache Yetus 0.7.0 http://yetus.apache.org This message was automatically generated.
          ivera Ignacio Vera added a comment -

          Attach a new patch where I allow the offline sorter to sort only a subset of the input file and therefore I do not need to copy the data before sorting. This strategy make it faster, and even for 2 dimensions:

          Approach Index time (sec) Force merge time (sec) Index size (GB) Reader heap (MB)

                    ||Dev||Base||Diff ||Dev  ||Base  ||diff   ||Dev||Base||Diff||Dev||Base||Diff ||

          shapes 651.4s 847.0s -23% 0.0s 0.0s 0% 1.28 1.28 0% 1.77 1.77 0%
          points 235.7s 239.0s -1% 0.0s 0.0s 0% 0.51 0.51 0% 1.72 1.72 0%
          geo3d 384.8s 406.2s -5% 0.0s 0.0s 0% 0.71 0.71 0% 1.75 1.75 0%

           

          ivera Ignacio Vera added a comment - Attach a new patch where I allow the offline sorter to sort only a subset of the input file and therefore I do not need to copy the data before sorting. This strategy make it faster, and even for 2 dimensions: Approach Index time (sec) Force merge time (sec) Index size (GB) Reader heap (MB)           ||Dev||Base||Diff ||Dev  ||Base  ||diff   ||Dev||Base||Diff||Dev||Base||Diff || shapes 651.4s 847.0s -23% 0.0s 0.0s 0% 1.28 1.28 0% 1.77 1.77 0% points 235.7s 239.0s -1% 0.0s 0.0s 0% 0.51 0.51 0% 1.72 1.72 0% geo3d 384.8s 406.2s -5% 0.0s 0.0s 0% 0.71 0.71 0% 1.75 1.75 0%  
          lucenesolrqa Lucene/Solr QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
                Prechecks
          -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.
                master Compile Tests
          +1 compile 0m 29s master passed
                Patch Compile Tests
          +1 compile 0m 27s the patch passed
          +1 javac 0m 27s the patch passed
          +1 Release audit (RAT) 0m 27s the patch passed
          +1 Check forbidden APIs 0m 27s the patch passed
          +1 Validate source patterns 0m 27s the patch passed
                Other Tests
          -1 unit 14m 23s core in the patch failed.
          17m 25s



          Reason Tests
          Failed junit tests lucene.search.TestIntRangeFieldQueries



          Subsystem Report/Notes
          JIRA Issue LUCENE-8623
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12953244/LUCENE-8623.patch
          Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns
          uname Linux lucene1-us-west 4.4.0-137-generic #163~14.04.1-Ubuntu SMP Mon Sep 24 17:14:57 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
          Build tool ant
          Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh
          git revision master / 345a655
          ant version: Apache Ant(TM) version 1.9.3 compiled on July 24 2018
          Default Java 1.8.0_191
          unit https://builds.apache.org/job/PreCommit-LUCENE-Build/145/artifact/out/patch-unit-lucene_core.txt
          Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/145/testReport/
          modules C: lucene/core U: lucene/core
          Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/145/console
          Powered by Apache Yetus 0.7.0 http://yetus.apache.org

          This message was automatically generated.

          lucenesolrqa Lucene/Solr QA added a comment - -1 overall Vote Subsystem Runtime Comment       Prechecks -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.       master Compile Tests +1 compile 0m 29s master passed       Patch Compile Tests +1 compile 0m 27s the patch passed +1 javac 0m 27s the patch passed +1 Release audit (RAT) 0m 27s the patch passed +1 Check forbidden APIs 0m 27s the patch passed +1 Validate source patterns 0m 27s the patch passed       Other Tests -1 unit 14m 23s core in the patch failed. 17m 25s Reason Tests Failed junit tests lucene.search.TestIntRangeFieldQueries Subsystem Report/Notes JIRA Issue LUCENE-8623 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12953244/LUCENE-8623.patch Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns uname Linux lucene1-us-west 4.4.0-137-generic #163~14.04.1-Ubuntu SMP Mon Sep 24 17:14:57 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux Build tool ant Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh git revision master / 345a655 ant version: Apache Ant(TM) version 1.9.3 compiled on July 24 2018 Default Java 1.8.0_191 unit https://builds.apache.org/job/PreCommit-LUCENE-Build/145/artifact/out/patch-unit-lucene_core.txt Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/145/testReport/ modules C: lucene/core U: lucene/core Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/145/console Powered by Apache Yetus 0.7.0 http://yetus.apache.org This message was automatically generated.
          ivera Ignacio Vera added a comment -

          I have run the Geo benches and I have monitor the size of the index. The exercise have been done with the current approach and the approach proposed with this issue and plots are attached. Note that the indexing has been done with force merge at the end to show the behaviour when merging large segments.

          As shown in the plots, in all cases there is a significant reduction on the write amplification needed when merging segments. In addition there is a reduction on indexing time.

           

           

          ivera Ignacio Vera added a comment - I have run the Geo benches and I have monitor the size of the index. The exercise have been done with the current approach and the approach proposed with this issue and plots are attached. Note that the indexing has been done with force merge at the end to show the behaviour when merging large segments. As shown in the plots, in all cases there is a significant reduction on the write amplification needed when merging segments. In addition there is a reduction on indexing time.    
          jpountz Adrien Grand added a comment -

          Wow this is a significant reduction indeed.

          jpountz Adrien Grand added a comment - Wow this is a significant reduction indeed.
          lucenesolrqa Lucene/Solr QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
                Prechecks
          -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.
                master Compile Tests
          +1 compile 1m 39s master passed
                Patch Compile Tests
          +1 compile 1m 31s the patch passed
          +1 javac 1m 31s the patch passed
          +1 Release audit (RAT) 1m 31s the patch passed
          +1 Check forbidden APIs 1m 31s the patch passed
          +1 Validate source patterns 1m 31s the patch passed
                Other Tests
          +1 unit 29m 30s core in the patch passed.
          35m 30s



          Subsystem Report/Notes
          JIRA Issue LUCENE-8623
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12953955/LUCENE-8623.patch
          Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns
          uname Linux lucene2-us-west.apache.org 4.4.0-112-generic #135-Ubuntu SMP Fri Jan 19 11:48:36 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
          Build tool ant
          Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh
          git revision master / e015afa
          ant version: Apache Ant(TM) version 1.9.6 compiled on July 20 2018
          Default Java 1.8.0_191
          Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/148/testReport/
          modules C: lucene/core U: lucene/core
          Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/148/console
          Powered by Apache Yetus 0.7.0 http://yetus.apache.org

          This message was automatically generated.

          lucenesolrqa Lucene/Solr QA added a comment - -1 overall Vote Subsystem Runtime Comment       Prechecks -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.       master Compile Tests +1 compile 1m 39s master passed       Patch Compile Tests +1 compile 1m 31s the patch passed +1 javac 1m 31s the patch passed +1 Release audit (RAT) 1m 31s the patch passed +1 Check forbidden APIs 1m 31s the patch passed +1 Validate source patterns 1m 31s the patch passed       Other Tests +1 unit 29m 30s core in the patch passed. 35m 30s Subsystem Report/Notes JIRA Issue LUCENE-8623 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12953955/LUCENE-8623.patch Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns uname Linux lucene2-us-west.apache.org 4.4.0-112-generic #135-Ubuntu SMP Fri Jan 19 11:48:36 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux Build tool ant Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh git revision master / e015afa ant version: Apache Ant(TM) version 1.9.6 compiled on July 20 2018 Default Java 1.8.0_191 Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/148/testReport/ modules C: lucene/core U: lucene/core Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/148/console Powered by Apache Yetus 0.7.0 http://yetus.apache.org This message was automatically generated.
          ivera Ignacio Vera added a comment -

          New patch, just a bit of clean up. Now there are no changes to the offline sorter. 

          ivera Ignacio Vera added a comment - New patch, just a bit of clean up. Now there are no changes to the offline sorter. 
          lucenesolrqa Lucene/Solr QA added a comment -
          -1 overall



          Vote Subsystem Runtime Comment
                Prechecks
          -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.
                master Compile Tests
          +1 compile 0m 34s master passed
                Patch Compile Tests
          +1 compile 0m 28s the patch passed
          +1 javac 0m 28s the patch passed
          +1 Release audit (RAT) 0m 28s the patch passed
          +1 Check forbidden APIs 0m 29s the patch passed
          +1 Validate source patterns 0m 28s the patch passed
                Other Tests
          +1 unit 13m 25s core in the patch passed.
          16m 37s



          Subsystem Report/Notes
          JIRA Issue LUCENE-8623
          JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12954126/LUCENE-8623.patch
          Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns
          uname Linux lucene1-us-west 4.4.0-137-generic #163~14.04.1-Ubuntu SMP Mon Sep 24 17:14:57 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
          Build tool ant
          Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh
          git revision master / a37e2c6
          ant version: Apache Ant(TM) version 1.9.3 compiled on July 24 2018
          Default Java 1.8.0_191
          Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/149/testReport/
          modules C: lucene/core U: lucene/core
          Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/149/console
          Powered by Apache Yetus 0.7.0 http://yetus.apache.org

          This message was automatically generated.

          lucenesolrqa Lucene/Solr QA added a comment - -1 overall Vote Subsystem Runtime Comment       Prechecks -1 test4tests 0m 0s The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch.       master Compile Tests +1 compile 0m 34s master passed       Patch Compile Tests +1 compile 0m 28s the patch passed +1 javac 0m 28s the patch passed +1 Release audit (RAT) 0m 28s the patch passed +1 Check forbidden APIs 0m 29s the patch passed +1 Validate source patterns 0m 28s the patch passed       Other Tests +1 unit 13m 25s core in the patch passed. 16m 37s Subsystem Report/Notes JIRA Issue LUCENE-8623 JIRA Patch URL https://issues.apache.org/jira/secure/attachment/12954126/LUCENE-8623.patch Optional Tests compile javac unit ratsources checkforbiddenapis validatesourcepatterns uname Linux lucene1-us-west 4.4.0-137-generic #163~14.04.1-Ubuntu SMP Mon Sep 24 17:14:57 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux Build tool ant Personality /home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh git revision master / a37e2c6 ant version: Apache Ant(TM) version 1.9.3 compiled on July 24 2018 Default Java 1.8.0_191 Test Results https://builds.apache.org/job/PreCommit-LUCENE-Build/149/testReport/ modules C: lucene/core U: lucene/core Console output https://builds.apache.org/job/PreCommit-LUCENE-Build/149/console Powered by Apache Yetus 0.7.0 http://yetus.apache.org This message was automatically generated.
          jpountz Adrien Grand added a comment -

          +1 patch looks good.

          Given how much this helps I'm thinking we should look into handling merging more similarly to how we handle flushing by recursively partitioning around the median value of each dimension. It should be possible to implement something like an offline oal.util.RadixSelector.

          jpountz Adrien Grand added a comment - +1 patch looks good. Given how much this helps I'm thinking we should look into handling merging more similarly to how we handle flushing by recursively partitioning around the median value of each dimension. It should be possible to implement something like an offline oal.util.RadixSelector.

          Commit 8762b071bb04b2e391749e6a064966ecfe932862 in lucene-solr's branch refs/heads/master from Ignacio Vera
          [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=8762b07 ]

          LUCENE-8623: Decrease I/O pressure when merging high dimensional points

          jira-bot ASF subversion and git services added a comment - Commit 8762b071bb04b2e391749e6a064966ecfe932862 in lucene-solr's branch refs/heads/master from Ignacio Vera [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=8762b07 ] LUCENE-8623 : Decrease I/O pressure when merging high dimensional points

          Commit 74ee4ddf4eb7b6c7f60c3e1fb73da0427c0085ac in lucene-solr's branch refs/heads/branch_8x from Ignacio Vera
          [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=74ee4dd ]

          LUCENE-8623: Decrease I/O pressure when merging high dimensional points

          jira-bot ASF subversion and git services added a comment - Commit 74ee4ddf4eb7b6c7f60c3e1fb73da0427c0085ac in lucene-solr's branch refs/heads/branch_8x from Ignacio Vera [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=74ee4dd ] LUCENE-8623 : Decrease I/O pressure when merging high dimensional points

          Commit 35955b3891ed6621d5faa1c2c20ce0a333bc7b83 in lucene-solr's branch refs/heads/branch_7x from Ignacio Vera
          [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=35955b3 ]

          LUCENE-8623: Decrease I/O pressure when merging high dimensional points

          jira-bot ASF subversion and git services added a comment - Commit 35955b3891ed6621d5faa1c2c20ce0a333bc7b83 in lucene-solr's branch refs/heads/branch_7x from Ignacio Vera [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=35955b3 ] LUCENE-8623 : Decrease I/O pressure when merging high dimensional points
          tomoko Tomoko Uchida added a comment -

          This issue was moved to GitHub issue: #9669.

          tomoko Tomoko Uchida added a comment - This issue was moved to GitHub issue: #9669 .

          People

            ivera Ignacio Vera
            ivera Ignacio Vera
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: