NumericField&NumericRangeQuery 원리 분석

NumericField 와 NumericRange Query 는 Lucene 입 니 다.
수치 형 구간 조회 에 대한 최적화 방안.논술 을 전개 하 다
NumericField
Numberic Ranage Query
의 실현 원리 이전에 Lucene 범위 조회 의 실현 과 개념 에 대해 박문 인 을 참고 할 수 있다.
Lucene 2.9 부터 디지털 범위 에 대한 지원 을 제공 합 니 다.그러나 이 검색 을 사용 하려 면 NumericField 추가 도 메 인 을 사용 해 야 합 니 다.Lucene 원생 API:Java 코드 를 사용 해 야 합 니 다.
  • document.add(newNumericField(name).setIntValue(value));

  • 또는 NumericTokenStream 추가 필드 사용:자바 코드
  • Fieldfield=newField(name,newNumericTokenStream(precisionStep).setIntValue(value));
  • field.setOmitNorms(true);
  • field.setOmitTermFreqAndPositions(true);
  • document.add(field);

  • Solr 프레임 워 크 에 사용 하려 면 schema.xml:자바 코드 를 정의 해 야 합 니 다.
    <fieldType  name=“long” class=“solr.TrieLongField” precisionStep=“8″
    mitNorms=“true” positionIncrementGap=“0″/>
    <fieldType  name=“int” class=“solr.TrieIntField” precisionStep=“4″
    mitNorms=“true” positionIncrementGap=“0″/>
    solr                schema.xml  filedType   field,

    그래서 trieField 로 정의 되면 field 를 구성 할 때 TrieField 류 의 createField()방법 을 사용 합 니 다.
    자바 코드
    public Fieldable createField(SchemaField field, String externalVal, float boost) {
      boolean indexed = field.indexed();
      boolean stored = field.stored();
    
      if (!indexed && !stored) {
        if (log.isTraceEnabled())
          log.trace(“Ignoring unindexed/unstored field: ” + field);
        return null;
      }
        //  NumericField
      final NumericField f = new NumericField(field.getName(), precisionStep, stored ? Field.Store.YES :
    Field.Store.NO, indexed);
      switch (type) {//    field   set     
        case INTEGER:
          f.setIntValue(Integer.parseInt(externalVal));
          break;
        case FLOAT:
          f.setFloatValue(Float.parseFloat(externalVal));
          break;
        case LONG:
          f.setLongValue(Long.parseLong(externalVal));
          break;
        case DOUBLE:
          f.setDoubleValue(Double.parseDouble(externalVal));
          break;
        case DATE:
          f.setLongValue(dateField.parseMath(null, externalVal).getTime());
          break;
        default:
          throw new SolrException(SolrException.ErrorCode.SERVER_ERROR, “Unknown type for trie field: ” + type);
      }
    
      f.setOmitNorms(field.omitNorms());
      f.setIndexOptions(getIndexOptions(field, externalVal));
      f.setBoost(boost);
      return f;
    }

    Field 를 구성 한 후 docment.add()를 거 친 후 Wirter.updateDocument()를 거 쳐 Lucene 구조 색인 절 차 를 거 쳐 Doc 를
    색인 으로 바꾸다.그 중에서 DocInverter PerField.processFields()의 과정 은 이 도 메 인 에서 만 든 단어 규칙 을 도 메 인 값 으로 하 는 것 입 니 다.
    term 로 나 누 어 CharTermAttribute 를 통 해 consumer 대상 에 게 다음 단계 의 색인 구축 절 차 를 진행 합 니 다.
    그 중에서 가장 중요 한 부분 은 NumericField.tokenStreamValue()방법 입 니 다.
    자바 코드
    public TokenStream tokenStreamValue()   {
       if (!isIndexed())
         return null;
       if (numericTS == null) {
         // lazy init the TokenStream as it is heavy to instantiate (attributes,…),
         // if not needed (stored field loading)
         numericTS = new NumericTokenStream(precisionStep);
         // initialize value in TokenStream
         if (fieldsData != null) {
           assert type != null;
           final Number val = (Number) fieldsData;
           switch (type) {
             case INT:
               numericTS.setIntValue(val.intValue()); break;
             case LONG:
               numericTS.setLongValue(val.longValue()); break;
             case FLOAT:
               numericTS.setFloatValue(val.floatValue()); break;
             case DOUBLE:
               numericTS.setDoubleValue(val.doubleValue()); break;
             default:
               assert false : “Should never get here”;
           }
         }
       }
       return numericTS;
     }

    NumericTokenStreamstream=field.tokenStreamValue();실행 이 끝 난 후에 TokenStream 으로 돌아 갑 니 다.TokenStream 은 Lucene 에서 도 메 인 값 에 대해 단 어 를 나 누 는 핵심 클래스 를 결정 합 니 다.그 중에서 increment Token()방법 은 단 어 를 나 누 는 관건 적 인 방법 입 니 다.고 개 를 돌려 Numeric TokenStream 의 이 방법 을 살 펴 보 겠 습 니 다.
    자바 코드
    public boolean incrementToken() {
       if (valSize == 0)
         throw new IllegalStateException(“call set???Value() before usage”);
       if (shift >= valSize)
         return false;
    
       clearAttributes();//  termAttr
       /**
        *NumericTokenStream value      ,
        *  Lucene Token       
        *                 ,
        *               
        */
       final char[] buffer;
       switch (valSize) {
         case 64://     TermBuffer,           
          //  ternAtt’s buffer   
           buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_LONG);
            //longToPrefixCoded      Long  value           termAtt.buffer 
           termAtt.setTermLength(NumericUtils.longToPrefixCoded(value, shift, buffer));
           break;
    
         case 32:
           buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_INT);
           termAtt.setTermLength(NumericUtils.intToPrefixCoded((int) value, shift, buffer));
           break;
    
         default:
           // should not happen
           throw new IllegalArgumentException(“valSize must be 32 or 64″);
       }
    
       typeAtt.setType((shift == 0) ? TOKEN_TYPE_FULL_PREC : TOKEN_TYPE_LOWER_PREC);
       posIncrAtt.setPositionIncrement((shift == 0) ? 1 : 0);
       shift += precisionStep;
       return true;
     }

    다음은 NumericUtils 가 어떻게 수치 형 을 문자열 로 바 꾸 는 지 살 펴 보 겠 습 니 다.
    자바 코드
    public static int longToPrefixCoded(final long val, final int shift, final char[] buffer) {
      if (shift>63 || shift<0)
        throw new IllegalArgumentException(“Illegal shift value, must be 0..63″);
      //shift   0; valSize = 64;   (63 - shift) / 7 + 1     Token buffer   
      int nChars = (63-shift)/7 + 1, len = nChars+1;
      //buffer[0] = 0×20+0;
      buffer[0] = (char)(SHIFT_START_LONG + shift);
      long sortableBits = val ^ 0x8000000000000000L;
      sortableBits >>>= shift;
      while (nChars>=1) {
        // Store 7 bits per character for good efficiency when UTF-8 encoding.
        // The whole number is right-justified so that lucene can prefix-encode
        // the terms more efficiently.
        //       uft-8   
        buffer[nChars--] = (char)(sortableBits & 0x7f);
        sortableBits >>>= 7;
      }
      return len;
    }

    incrementToken 과 NumericUtils.longToPrefixcoded()를 결합 하면 다음 절차 에 따라 처 리 됩 니 다.(1)longToPrefixcoded()에 들 어가 면 shift 가 초기 에 0 이 되면;valSize=64;(63㎡Cshift)/7+1 에 따라 현재 Token 의 buffer 길 이 를 계산 합 니 다(2)buffer[0]에 저 장 된 것 은 32+shift(3)sortableBits=value^0x80000000000000L,sortableBits>>=shift(오른쪽 이동 shift 비트)(4)교체 buffer[buffer.size-1->1]각 값 은 buffer[n]=(char)(sortableBits&0x7f),sortableBits>>=7 입 니 다.sortableBits 를 7 자리(5)에서 longToPrefixcoded()로 왼쪽으로 이동 시 키 고 TermAttribute 의 termBuffer 를 buffer 로 설정 하 며 buffer Length 등 속성(6)shift+=precision Step 가 shift>=valSize(64,long 을 예 로 들 면)를 설정 하고 false 로 돌아 가면 절 분 된 char 과정 을 종료 합 니 다.그렇지 않 으 면 절차 에 들 어 갑 니 다(1).그래서 우 리 는 value=2048 로precision Step=8 예 를 들 어 인 코딩 을 거 친 TOKENSTREAM 흐름 은 다음 과 같 습 니 다.
    자바 코드
    [ 32 1 0 0 0 0 0 0 0 16 0 ]
    [ 40 64 0 0 0 0 0 0 8 ]
    [ 48 32 0 0 0 0 0 0 ]
    [ 56 16 0 0 0 0 0 ]
    [ 64 8 0 0 0 0 ]
    [ 72 4 0 0 0 ]
    [ 80 2 0 0 ]
    [ 88 1 0 ]

    즉,2048 의 Long 형 수 치 는 Numeric TokenStream 에 의 해 8 개의 length 가 다른 문자열 로 자 른 것 이다.precision Step 의 역할 을 표시 하기 위해 value=2048,precision Step=4 를 사용 하여 어떤 상황 이 발생 하 는 지 알 아 보 겠 습 니 다.
    자바 코드
    [ 32 1 0 0 0 0 0 0 0 16 0 ]
    [ 36 8 0 0 0 0 0 0 1 0 ]
    [ 40 64 0 0 0 0 0 0 8 ]
    [ 44 4 0 0 0 0 0 0 0 ]
    [ 48 32 0 0 0 0 0 0 ]
    [ 52 2 0 0 0 0 0 0 ]
    [ 56 16 0 0 0 0 0 ]
    [ 60 1 0 0 0 0 0 ]
    [ 64 8 0 0 0 0 ]
    [ 68 64 0 0 0 ]
    [ 72 4 0 0 0 ]
    [ 76 32 0 0 ]
    [ 80 2 0 0 ]
    [ 84 16 0 ]
    [ 88 1 0 ]
    [ 92 8 ]

    precision Step 가 작 을 수록'자 르 기'된 문자열 이 많 음 이 분명 하 다.precision Step 가 작 을 수록 value 가'절단'되 는 term 가 많아 집 니 다.즉,색인 부피 가 커진다 는 것 입 니 다.'자 르 기'로 분 류 된 term 이 많 을 수록 Numeric RangeQuery 에서 세분 화 된 동네 에 존재 할 가능성 도 높 아 지고 조회 횟수 도 적 을 수록 성능 도 좋다.그러나 이것 은 절대적 인 것 이 아니다.일반적으로 검색 속도 가 떨 어 지 는 것 은 index 에서 term 를 검색 하 는 열 거 를 더 많이 하기 때문에 이상 적 인 precision Step 는 자신의 테스트 에 따라 만 얻 을 수 있다.또한 범위 조회 없 이 sort 만 진행 하면 precision Step=Integer.MAXVALUE。이렇게 하면 하나의 term 만 생 성 되 어 색인 부 피 를 늘 리 지 않 을 것 이다.NumericRangeQuery 는 MultiTermQuery 이기 때문에 Lucene 의 검색 절 차 를 따 릅 니 다.Query 트 리->rewrite->weight 트 리->Scorer 트 리 입 니 다.이 상세 한 절 차 는 필자 의 또 다른 블 로그 인'TermRangeQuery 소스 코드 해석'글 을 보십시오.query rewrite 과정:
    자바 코드
    Query result = new ConstantScoreQuery(new MultiTermQueryWrapperFilter(query));
               result.setBoost(query.getBoost());
               return result;

    weight 트 리 구축:
    자바 코드
    public Weight createWeight(Searcher searcher) {
       return new ConstantScoreQuery.ConstantWeight(searcher);
     }

    scorer 트 리 구축:
    자바 코드
    public Scorer scorer(IndexReader reader, boolean scoreDocsInOrder, boolean topScorer) throws IOException {
         return new ConstantScorer(similarity, reader, this);
       }

    상기 과정 후,전체 구간 필터 DocIdSet 는 MultiTermQuery Wrapper Filter 의 getDocIdSet 방법 으로 구간 조회 필터 링 을 진행 합 니 다.
    자바 코드
    public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
      final TermEnum enumerator = query.getEnum(reader);////  NumericRangeQuery Term   
      try {
        // if current term in enum is null, the enum is empty -> shortcut
        if (enumerator.term() == null)
          return DocIdSet.EMPTY_DOCIDSET;
        // else fill into a OpenBitSet
        final OpenBitSet bitSet = new OpenBitSet(reader.maxDoc());//      Term      
        new TermGenerator() {
          public void handleDoc(int doc) {
            bitSet.set(doc);
          }
        }.generate(reader, enumerator);
        return bitSet;
      } finally {
        enumerator.close();
      }
    }

    최종 적 으로 구간 조회 조건 을 만족 시 키 는 docId 는 OpenBitSet 에 채 워 집 니 다.가장 중요 한 부분 은 Numeric RangeQuery 에서 조건 을 만족 시 키 는 Term 매 거 진 을 어떻게 얻 는 지 볼 수 있 습 니 다.즉,위의 코드 finalTermEnumenumerator=query.getEnum(reader)부분 입 니 다.
    자바 코드
    protected FilteredTermEnum getEnum(final IndexReader reader) throws IOException {
      return new NumericRangeTermEnum(reader);
    }

    Numeric RangeTermEnum 의 구조 함수 의 핵심 코드 부분 을 계속 보 세 요:
    자바 코드
    switch (valSize) {
         case 64: {
           // lower
           long minBound = Long.MIN_VALUE;
           if (min instanceof Long) {
             minBound = min.longValue();
           } else if (min instanceof Double) {
             minBound = NumericUtils.doubleToSortableLong(min.doubleValue());
           }
           if (!minInclusive && min != null) {
             if (minBound == Long.MAX_VALUE) break;
             minBound++;
           }
    
           // upper
           long maxBound = Long.MAX_VALUE;
           if (max instanceof Long) {
             maxBound = max.longValue();
           } else if (max instanceof Double) {
             maxBound = NumericUtils.doubleToSortableLong(max.doubleValue());
           }
           if (!maxInclusive && max != null) {
             if (maxBound == Long.MIN_VALUE) break;
             maxBound�C;
           }
           //                 
           NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() {
             //@Override
             public final void addRange(String minPrefixCoded, String maxPrefixCoded) {
               rangeBounds.add(minPrefixCoded);
               rangeBounds.add(maxPrefixCoded);
             }
           }, precisionStep, minBound, maxBound);
           break;
         }

    이 부분의 관건 적 인 코드 는 하나의 조회 범위 구간 을 몇 개의 작은 조회 구간 으로 분해 하 는 것 이다.예 를 들 어 구간[1,12340]은 최종 적 으로 다음 과 같이 분 해 될 것 이다.
    자바 코드
    (1) low [ 32 1 0 0 0 0 0 0 0 0 1 ]      high  [ 32 1 0 0 0 0 0 0 0 0 15 ]
    (2) low [ 32 1 0 0 0 0 0 0 0 96 48 ]  high  [ 32 1 0 0 0 0 0 0 0 96 52 ]
    (3) low [ 36 8 0 0 0 0 0 0 0 1 ]         high  [ 36 8 0 0 0 0 0 0 0 15 ]
    (4) low [ 36 8 0 0 0 0 0 0 6 0 ]         high  [ 36 8 0 0 0 0 0 0 6 2 ]
    (5) low [ 40 64 0 0 0 0 0 0 1 ]          high  [ 40 64 0 0 0 0 0 0 15 ]
    (6) low [ 44 4 0 0 0 0 0 0 1 ]            high  [ 44 4 0 0 0 0 0 0 2 ]

    여섯 개의 동네 에서 Numeric RangeTermEnum 매 거 진 은 next()방법 에 따라 term 이 이 구간 에 있 는 지 여 부 를 판단 합 니 다.만약 에 있 으 면 특정한 currentTerm 과 current UpperBound(현재 하위 high 구간 의 값)문자열 이 더 클 때 까지 계속 옮 겨 다 닐 수 있 습 니 다.다음 키 구간 에 들 어가 비교 할 수 있다 고 생각 합 니 다.주요 코드 논 리 는 다음 과 같 습 니 다.
    자바 코드
    public boolean next() throws IOException {
          // if a current term exists, the actual enum is initialized:
          // try change to next term, if no such term exists, fall-through
          if (currentTerm != null) {
            assert actualEnum != null;
            if (actualEnum.next()) {
              currentTerm = actualEnum.term();
              if (termCompare(currentTerm))
                return true;
            }
          }
    
          // if all above fails, we go forward to the next enum,
          // if one is available
          currentTerm = null;
          while (rangeBounds.size() >= 2) {
            assert rangeBounds.size() % 2 == 0;
            // close the current enum and read next bounds
            if (actualEnum != null) {
              actualEnum.close();
              actualEnum = null;
            }
            final String lowerBound = rangeBounds.removeFirst();
            this.currentUpperBound = rangeBounds.removeFirst();
            // create a new enum
            actualEnum = reader.terms(termTemplate.createTerm(lowerBound));
            currentTerm = actualEnum.term();
            if (currentTerm != null && termCompare(currentTerm))
              return true;
            // clear the current term for next iteration
            currentTerm = null;
          }
    
          // no more sub-range enums available
          assert rangeBounds.size() == 0 && currentTerm == null;
          return false;
        }

    다음은 구간 비교 의 논리 적 순 서 를 예 로 들 어 현재 색인 에 1024 와 123412 개의 값 이 있다 고 가정 하고 precision Step=4,조회 범 위 는[1,12340]이다.1024 색인 에 저 장 된 저장 구 조 는 다음 과 같 습 니 다.
    자바 코드
    1   [ 32 1 0 0 0 0 0 0 0 8 0 ]
    2   [ 36 8 0 0 0 0 0 0 0 64 ]
    3   [ 40 64 0 0 0 0 0 0 4 ]
    4   [ 44 4 0 0 0 0 0 0 0 ]
    5   [ 48 32 0 0 0 0 0 0 ]
    6   [ 52 2 0 0 0 0 0 0 ]
    7   [ 56 16 0 0 0 0 0 ]
    8   [ 60 1 0 0 0 0 0 ]
    9   [ 64 8 0 0 0 0 ]
    10 [ 68 64 0 0 0 ]
    11 [ 72 4 0 0 0 ]
    12 [ 76 32 0 0 ]
    13 [ 80 2 0 0 ]
    14 [ 84 16 0 ]
    15 [ 88 1 0 ]
    16 [ 92 8 ]

    비고:low[1](대표:[3210000001])
    high[1](대표:[32100000015])
    1024[1](대표:[321000000080]),기타 순서대로 유추
    처음으로 low[1]-high[1]를 조회 한 결과 1024[1]-1024[16]가 이 구간 에 없 으 면 low[2]㎡Chigh[2]에 들 어가 비교 한 것 으로 나 타 났 다.
    2 차 검색 low[2]㎡Chigh[2],1024[1]-1024[16]모두 이 구간 에 없 으 면 low[3]㎡Chigh[3]에 들 어가 비교
    세 번 째 검색 low[3]㎡Chigh[3],1024[1]-1024[16]모두 이 구간 에 없 으 면 low[4]㎡Chigh[4]에 들 어가 비교
    4 차 검색 low[4]㎡Chigh[4],1024[1]-1024[16]모두 이 구간 에 없 으 면 low[5]㎡Chigh[5]에 들 어가 비교
    다섯 번 째 로 low[5]㎡Chigh[5]를 조회 한 결과 1024[3]가 이 구간 에 있 는 것 을 발견 하면 1024 이 값 이[1,12340]구간 에 있 음 을 나타 내 고 이 term 에 대응 하 는 docId 를 OpenBitSet 에 넣는다.
    다음은 12341 색인 에 저 장 된 구조 입 니 다.
    자바 코드
    1 [ 32 1 0 0 0 0 0 0 0 96 53 ]
    2 [ 36 8 0 0 0 0 0 0 6 3 ]
    3 [ 40 64 0 0 0 0 0 0 48 ]
    4 [ 44 4 0 0 0 0 0 0 3 ]
    5 [ 48 32 0 0 0 0 0 0 ]
    6 [ 52 2 0 0 0 0 0 0 ]
    7 [ 56 16 0 0 0 0 0 ]
    8 [ 60 1 0 0 0 0 0 ]
    9 [ 64 8 0 0 0 0 ]
    10 [ 68 64 0 0 0 ]
    11 [ 72 4 0 0 0 ]
    12 [ 76 32 0 0 ]
    13 [ 80 2 0 0 ]
    14 [ 84 16 0 ]
    15 [ 88 1 0 ]
    16 [ 92 8 ]

    위의 분석 규칙 에 따라:
    low[1]㎡Chigh[1]를 처음 조회 한 결과 12341[1]-12341[1]-12341[16]이 해당 구간 에 없 으 면 low[2]㎡Chigh[2]에 들 어가 비교 한 것 으로 나 타 났 다.
    2 차 검색 low[2]㎡Chigh[2],12341[1]-12341[16]모두 이 구간 에 없 으 면 low[3]㎡Chigh[3]에 들 어가 비교
    세 번 째 검색 low[3]㎡Chigh[3],12341[1]-12341[16]모두 이 구간 에 없 으 면 low[4]㎡Chigh[4]에 들 어가 비교
    4 차 검색 low[4]㎡Chigh[4],12341[1]-12341[16]모두 이 구간 에 없 으 면 low[5]㎡Chigh[5]에 들 어가 비교
    다섯 번 째 검색 low[5]㎡Chigh[5],12341[1]-12341[16]모두 이 구간 에 없 으 면 low[6]㎡Chigh[6]에 들 어가 비교
    여섯 번 째 로 low[6]㎡Chigh[6]를 조회 한 결과 12341[1]-12341[16]이 구간 에 없 는 것 을 발 견 했 습 니 다.next()방법 은 false 로 돌아 갑 니 다.
    또한 알 아야 할 것 은 매번 하위 구간 조회 에서 새로운 term 매 거 진 을 다시 찾 는 것 입 니 다.
    자바 코드
    actualEnum = reader.terms(termTemplate.createTerm(lowerBound));

    그렇다면 1024 의 경우 매번 1024[1]부터 재 비교 할 필요 가 없다 는 것 이다.1024[2-n]의 한 가장 가 까 운 하위 구간 의 term 값 을 비교 하면 비교 횟수 가 크게 줄 어 들 것 이다.
    TermRangeQuery 와 의 장점:
    (1)수치 형 범위 조회 지원
    (2)하위 구역 간 을 사용 하여 term 매 거 진 횟수 를 줄 이 고 성능 을 크게 향상 시킨다.
    단점:
    (1)수치 분할 여러 term 저장,색인 부피 증대
    (2)범위 조회 의 성능 손실 을 완전히 근절 하지 못 하고 범위 비교,매 거 진 누적 등 성능 손실 이 있다.
    요약:
    NumericRangeQuery 는 구간 조회 의 성능 을 향상 시 킬 수 있 으 나 구간 조회 에 따 른 성능 손실 을 완전히 차단 할 수 는 없습니다.구간 조회 에 따 른 성능 소 모 를 완전히 제거 하려 면 구간 필터 방식 만 사용 할 수 있 습 니 다.docId 와 rangeUid 를 배열 로 메모리 에 저장 합 니 다.그 다음 에 다른 조회 조건 을 만족 시 키 는 docId 를 확보 하 는 동시에 이 구간 의 배열 범위 내 에서 최종 적 으로 조건 을 만족 시 키 는 docId 라 고 생각 합 니 다.그렇지 않 으 면 이 docId 를 걸 러 냅 니 다.이런 디자인 만 이 구간 에 따 른 성능 손실 을 완전히 소모 할 수 있다.따라서 Numeric RangeQuery 는 데이터 양 이 많 지 않 고 조회 구간 이 크 지 않 은 상황 에서 범위 조회 의 최 우선 방안 으로 문제 가 없다.

    좋은 웹페이지 즐겨찾기