Uploaded image for project: 'Hive'
  1. Hive
  2. HIVE-11638

ExprNodeDesc hashMap accidentally degrades into O(N) instead of O(1)

Log workAgile BoardRank to TopRank to BottomVotersWatch issueWatchersCreate sub-taskConvert to sub-taskMoveLinkCloneLabelsUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 0.14.0, 1.0.1, 1.1.1, 1.2.1, 1.3.0, 2.0.0
    • Fix Version/s: 1.3.0, 2.0.0
    • Component/s: Logical Optimizer
    • Labels:
    • Release Note:
      Use fastest hashmap implementation of ExprNodeDesc lookups

      Description

      Due to the absence of ExprNodeDesc::equals() & the presence of a hashCode(), any code which computes a Set or HashMap of identical objects ends up with a skewed hashmap which degrades column lookups from O(1) to O(N) during optimizer passes.

      So, several hundred references to a single column desc will be stored in a single hashbucket, but since they default to Object::equals(), they are not equal to each other.

      Finalize the equals() method, so that the approach from HIVE-10215 carries over safely.

        Attachments

        1. HIVE-11638.1.patch
          3 kB
          Gopal Vijayaraghavan

        Issue Links

          Activity

          $i18n.getText('security.level.explanation', $currentSelection) Viewable by All Users
          Cancel

            People

            • Assignee:
              gopalv Gopal Vijayaraghavan Assign to me
              Reporter:
              gopalv Gopal Vijayaraghavan

              Dates

              • Created:
                Updated:
                Resolved:

                Issue deployment