MergeQueue is slow for some query range sets #2358

Activity

1. lossyrob

   added this to the 1.2 milestone on Sep 7, 2017
2. metasim commented on Sep 8, 2017

   

   metasim

   on Sep 8, 2017

   Member

   More actions

   Do we need #2348 addressed first (or at least the tech stack decided on)?

   Per @mteldridge's comments, changing the line above to

   val compressedRanges = MergeQueue(r.sortBy(_._1)).toArray

   significantly improves performance in our use case.
3. mteldridge commented on Sep 8, 2017

   

   mteldridge

   on Sep 8, 2017

   Contributor

   More actions

   As @lossyrob mentioned in Gitter, the appropriate fix is to sort by start value in the MergeQueue.apply method prior to inserting the index ranges. The fix will then get picked up by all the modules that use the MergeQueue. Pre-sorting should allow one to do the merging in a single pass through the array. I would also consider replacing the array that backs MergeQueue with something that at least provides constant time insertion/deletion. This should make the complexity O(nlogn) instead of what it is now - O(n^2) or perhaps worse.
4. mteldridge commented on Sep 8, 2017

   

   mteldridge

   on Sep 8, 2017

   Contributor

   More actions

   Here is a candidate for a long-term fix. I get the same answer as the original for our big 1600+ polygon query. It needs some more rigorous testing and profiling though:

     object MergeQueue {
   
       def apply(ranges: TraversableOnce[(Long, Long)]): Seq[(Long, Long)] = {
   
         var merged: List[(Long, Long)] = Nil
         ranges.toSeq.sortBy(_._1).foreach(r => {
           merged = merged match {
             case a :: rest if (r._1 - 1 <= a._2) => (a._1, Math.max(a._2, r._2)) :: rest
             case _ => r :: merged
           }
         })
         merged.reverse
       }
     }

   Presorting allows a single pass through the data and greatly simplifies the logic. Should be O(nlogn).

   Issues:

   • Although the object is binary compatible, the underlying MergeQueue class is gone, which happens to be public, so I guess this is a breaking change.
   • Given that this causes a breaking change, I would then change the signature of the apply method to:

       def apply(ranges: SeqLike[(Long, Long)]): Seq[(Long, Long)]

   which would allow me to call sortBy directly on ranges

   • Needs rigorous testing since it ultimately would go into SFCurve, etc.

   If you don't want any breaking changes right now, I would suggest simply doing the presort in the current MergeQueue.apply method.
5. mteldridge commented on Sep 11, 2017

   

   mteldridge

   on Sep 11, 2017

   Contributor

   More actions

   It looks like Z2 and Z3 internally use on the MergeQueue class directly, so will not benefit from the pre-sort. The presort still helps significantly in the RDDReader classes. For now I would suggest simply adding @lossyrob's suggested fix as implemented here:

   mteldridge@dc7d737

   In the long term, one could look into something like this that includes updates to Z2 and Z3.

   mteldridge@51cf29f
6. mteldridge commented on Sep 13, 2017

   

   mteldridge

   on Sep 13, 2017

   Contributor

   More actions

   Also, here is a test that isolates the problem. The test will hang at the call to MergeQueue.apply
   https://github.com/locationtech/geotrellis/compare/master...mteldridge:merge-queue-test?expand=1
7. echeipesh commented on Oct 4, 2017

   

   echeipesh

   on Oct 4, 2017

   Contributor

   More actions

   Resolved by #2400
8. echeipesh

   closed this as completedon Oct 4, 2017