MongoDB 6

Inverted Search Index

검색 엔진에서 주로 사용되는 Indexing 방식으로 key,value –> value,key 형태로 하는 패턴을 의미한다.

기본적으로 검색 로봇은특정 URL에 대해 해당 페이지에 나오는 정보를 parsing해서 value로 저장하지만, 사용자는 키워드 검색을 통해서 URL를 찾아낸다. 그렇기 때문에, value에 indexing을 통해 검색 엔진 최적화를 진행하므로써 사용자의 검색 요청에 대한 빠른 처리가 가능하다.

검색 로봇이 저장할때에는 아래와 같은 형태로 index을 설계하지만

일반 사용자들이 검색을 수행할 때에는 키워드에 대한 검색을 통해 url을 찾는다. 따라서 아래와 같은 index가 필요한 것이다.

Inverted Search Index 설계

inverted mapper

기존의 index에 대해서 inverted search index로 설계하기 위해서는 key,value에 대한 변환 작업이 필요하다. 각각의 value에 대해 key를 다시 mapping하는 map 함수는 아래와 같이 동작하게 된다.

map(k,v)=
for each value in v:
  emit(value,key)

("www.google.com",["search","engine","bigdata"]) -->
("search","www.google.com")
("engine","www.google.com")
("bigdata","www.google.com")

combined reducer

하나의 출력키에 대해 여러 중간값을 가지게 되므로, 이에 대한 list 형태의 final value로 취합하는 reduce 함수는 아래와 같이 동작한다.

reduce(k,vals)=
array=[]
for each val in vals:
  array.push(val.actor)
emit(k,array)

("movie",[("actor",:"actor1"),("actor",:"actor2"),("actor",:"actor3")]) --> ("movie": ["actor1","actor2","actor3"])

Mapping 과정

(url,value list)의 수많은 쌍에 대해서 여러 노드에 분산하여 mapping 과정을 실행한다.

전체 동작 과정

Inverted Search Index 구현

map

var map=function(){
    for(var i in this.movies){
        key={movie:this.movies[i]};
        value={actors:[this.actor]}
        emit(key,value)
    }
}

reduce

var reduce=function(key,vals){
  actor_list={actors:[]}
  for(var i in vals){
    actor_list.actors=vals[i].actors.concat(actor_list.actors)
  }
  return actor_list; 
}

map reduce 실행

//테스트 데이터 삽입
db.actors.insertMany([{actor:"Richard Gere",movies:["Pretty Woman","Runaway Bride","Chicago"]},{actor:"Julia Roberts", movies:["Pretty Woman","Runaway Bride","Erin Brokovich"]}]);

//map reduce 실행, map,reduce를 실행하고 결과를 pivot collection에 삽입
db.actors.mapReduce(map,reduce,"pivot")

//map reduce에 대한 실행 결과 확인
//db.pivot.find()

결과

//배우 기반의 indexing
Enterprise test> db.actors.find()
[
  {
    _id: ObjectId("63b3ac0bc7f7ae56b4b2a8af"),
    actor: 'Richard Gere',
    movies: [ 'Pretty Woman', 'Runaway Bride', 'Chicago' ]
  },
  {
    _id: ObjectId("63b3ac0bc7f7ae56b4b2a8b0"),
    actor: 'Julia Roberts',
    movies: [ 'Pretty Woman', 'Runaway Bride', 'Erin Brokovich' ]
  }
]

//영화 기반의 indexing
Enterprise test> db.pivot.find()
[
  { _id: { movie: 'Chicago' }, value: { actors: [ 'Richard Gere' ] } },
  {
    _id: { movie: 'Erin Brokovich' },
    value: { actors: [ 'Julia Roberts' ] }
  },
  {
    _id: { movie: 'Pretty Woman' },
    value: { actors: [ 'Richard Gere', 'Julia Roberts' ] }
  },
  {
    _id: { movie: 'Runaway Bride' },
    value: { actors: [ 'Richard Gere', 'Julia Roberts' ] }
  }
]

References

• 영상
  • youtube
• 문서
  • document