2007/08/14 00:33 http://blog.naver.com/jujac/20040528894
역인덱스 구조에서의 AND 검색의 속도 향상.
글쓴이:jinyedge
조회수:1094
요즘에 대용량 데이타베이스를 다루게 되었습니다. 쉽게 말하자면 웹문서 검색엔진입니다.
크롤러와 인덱서는 java로 만들었지만 인터페이스단에서는 php를 사용하고 데이타베이스로는 mysql을 사용합니다. 아래는 현재 개발중인 검색엔진의 현황입니다.
- 저장된 문서의 갯수: 61만개그리고 데이타베이스는 mysql 4.015 바이너리 버전을 사용하고 있습니다.
- 인덱싱된 단어의 갯수: 4500만개
- 데이타베이스 크기: 1기가 바이트
- cpu: p4 2.4
- ram: 512
- hdd: ide 7200
----------------------
데이타베이스의 테이블의 경우 크게 나누면 다음의 2개로 구성됩니다.
(실제로는 전체 용량의 감소과 검색 속도의 향상을 위해서 구조가 더 복잡하지만 여기서는 단순화해서 설명하겠습니다)
- kw_table: 각 웹문서로부터 뽑아낸 키워드가 저장되어 있는 테이블입니다. 일종의 역인덱스 파일이라고 할 수 있죠. 각 키워드는 자신이 속한 웹문서의 번호와 함께 저장되어 있습니다.
- html_table: 원래의 웹문서가 저장되어 있습니다.
----------------------
현재 이런 구조에서 단일어 검색의 경우는 보통 0.2초 이하에 결과가 나옵니다.
아마 지금보다 데이타가 더 많다고 해도 결과는 비슷하리라 생각합니다. 그런데 문제는 and 검색의 경우입니다.
현재 AND 검색의 경우는 보통 1초에서 5초까지 걸립니다. 물론 이것도 결과 갯수를 500개로 제한을 걸어둔 상태입니다. AND 검색의 경우는 다음의 두가지 방법을 시도해 봤습니다.
1) kw_table에서 교집합을 구하는 방법
- 예를 들어서 '게임 정보' 라는 검색어를 사용하여 검색을 하는 경우
먼저 kw_table에서 '게임'에 해당하는 웹문서의 번호를 구하고 다시 kw_table에서 '정보'에 해당하는 웹문서의 번호를 구한 다음 이것들의 교집합을 구하는 것입니다. 하나의 sql 문으로 표현하자면 다음과 같은 형식이 되겠죠.
select html_idx, count(*) cnt from kw_table where kw in('게임', '정보')그러나 이 경우는 일단 group by 에서 많은 부하가 걸리고 해당되는 row의 갯수를 구하기 위해서 모든 row를 가져와야 하는 문제가 있어서 포기했습니다.
group by html_idx having cnt = 2 limit 0, 15;
2) kw_table로부터 임시 테이블을 만들고 이것을 join하여 순차검색을 하는 방법
- 예를 들어서 '게임 정보' 라는 검색어를 사용할 경우
먼저 '게임'에 해당하는 웹문서 번호를 임시 테이블로 만들고 이것을 다시 html_table과 join을 한 다음 '정보'라는 키워드가 들어있는 row를 순차검색으로 뽑아 냅니다. 실제 sql 문은 다음과 같은 형태가 되겠죠.
create temporary table tmp(html_idx int) select html_idx from kw_table where kw = '게임';사실 현재는 이 방법을 사용하고 있습니다.
select * from html_table a, tmp b where a.html_idx = b.html_idx and kw like '%정보%';
순차검색을 하기는 하지만 mysql의 경우 게시판에서 내용검색을 한다고 해도 pc급 서버에서도 1만개 정도의 게시물은 1초 이하로 검색이 완료되기에 순차검색을 한다고 해도 별 무리는 없다고 봅니다.
현재는 처음 kw_table에서 가져오는 tmp 테이블의 데이타를 500개로 제한하고 있습니다.
그러니 현재로서는 최대 500개를 join하고 순차검색을 하는 형태입니다.
실제로 이 방식의 경우는 group by에 의한 교집합을 구하는 방식보다 빠르고 전체 row 갯수를 구하기 위해 일단 모든 row를 가져와야하는 불합리한 점도 없지만 임시 테이블 생성과 join에서 부하가 걸리더군요.
임시 테이블의 경우는 in-memory 테이블이 라서 부하가 걸리지 않으리라 생각했는데 의외로 시간을 소모하는 경우가 있더군요. 그리고 join의 경우는 대부분의 시간을 잡아먹는 속도저하의 주범이죠.
제 생각에는 join의 경우는 데이타의 분포형태와도 관련이 있는 것 같습니다.
아마 하드드라이브의 헤드가 움직이는 범위가 클 수록 join에서의 속도저하가 심해지지 않나 싶습니다.
그리고 and 검색에서 제한을 거는 것 자체에는 문제가 없다고 봅니다.
제가 알기로는 대부분의 검색엔진이 and 검색의 대상을 어떤 형태로든 제한을 하고 있습니다. 제가 생각하기에는 현재 사용하고 있는 방식으로도 제한의 갯수를 1만개까지 늘릴 수 있다면 아무런 문제가 없다고 봅니다.
하지만 현재 500개의 제한으로도 충분한 속도가 나오지 않기 때문에 고민 중이죠.
아무튼 여기까지가 제가 현재 검색엔진을 개발하면서 겪고 있는 문제점입니다.
----------------------
현재 제가 생각하는 해결 방식은 일단 하드를 scsi로 교체하여 하드드라이브를 읽는 속도를 높이는 것과 RAM을 늘리고 일부 테이블을 RAM에 올리는 것입니다.
모든 테이블을 램으로 올릴 수는 없겠지만 join시에 속도저하의 주범이 되는 테이블을 RAM으로 올리는 것은 가능합니다. 이것으로 속도를 상당한 정도로 향상시킬 수 있다고 생각은 합니다.
아무튼 현재 제가 생각하는 방식은 하드웨어의 성능을 높이는 방향입니다.
그러나 이외에 제가 생각해낸 데이타 구조나 쿼리의 방법이 완전히 틀린 것은 아닐까하는 생각도 하고 있습니다. 그래서 이런 경우에서 작업을 해보신 분들의 조언을 구합니다. 요즘 저의 생각은 다음의 4가지로 표현할 수 있습니다.
- 역인덱스 구조에서의 AND 검색시에 임시 테이블이나 join을 쓰지 않고 처리할 수 있는 방법이 있을까요?
- 만약 현재의 db구조를 유지한다면 어떤 형태로 쿼리를 구성하는 것이 최선일까요?
- mysql로는 무리가 있으니 다른 데이타베이스로 교체하는 것이 옳을까요?
- 아니면 데이타베이스를 사용하는 것 부터가 무리이니 차라리 파일 시스템으로 가야 할까요?
저와 비슷한 경험을 갖고 계신 분들이 계시다면 고견을 들려주시면 감사하겠습니다.
> navyism
저도 검색엔진에 참 관심이 많아 이것저것 해보았는데요...
캐시 테이블을 하나 만들고 그것을 잘 활용해보는 쪽으로 생각을 하고 있습니다.
그런데 이것도 검색대상이 자주 업데이트 되는 경우라면 그다지 좋은 방법은 아닐듯 싶고요...
대형 검색엔진들의 검색 알고리즘이 참으로 궁금하네요...
하드웨어로 카바하는 것도 아닐테고 말이죠....
의견을 드린다면 4번은 그다지 좋은 방법은 아닐것 같습니다^^;;
10/09 22:28:18 211.202.28.80
> 익명
이런... 그렇지 않습니다. 4번이 좋은 예 이지요.. 흠.. 검색엔진에 관심이 많으시다면 잘 아실텐데요.
뭐 어쨌든... 결론만 이야기 해서... 저희회사는 LDAP + Informix를 사용하여 개발을 했습니다.
뭐.... 쩝... 금방 바닥날 이야기 라서 솔직히 말하는거지만.. 전 보조 프로그래머 이고...
저희 수석 엔지니어 분 께서 전체적인 설계를 구현하셨는데.. 처음엔 LDAP 와 PostgreSQL 을 사용했습니다.
회사이름 이야기 하면 광고가 될테니.... 입사한지 이제 1달 되었습니다 ㅡㅡ;
지금 제가 하는 일은 팀장님의 지시로 lucene 를 열심히 보고 있습니다.
기본 구조에 대하여는 상당히 확실한 감을 잡을 수 있다고 해서 현재 열심히 공부 중 입니다.
http://jakarta.apache.org/lucene/docs/index.html 에서 보실 수 있습니다.
10/09 23:20:32 61.78.224.220
> 별거없음
lucene도 마찬가지지만, 데이터가 입력되는 시점에 인덱스를 단어단위로 생성하거나
글자 한개 단위로 생성하거나 하는 식으로 작성하고, 해당 index를 메모리로 올리면 끝입니다.
상당히 간단하죠?^^
10/09 23:52:04 211.49.30.51
> jinyedge
캐시의 경우는 mysql 4.0 버전의 경우 쿼리캐시가 지원되니 그것으로 충분하다고 생각합니다.
실제 단일어 검색이던 AND 검색이던 현재 일단 캐시에 저장이 되면 대부분 0.0x초가 나옵니다.
쿼리 캐시 사이즈만 맘껏 할당할 수 있다면 캐싱된 데이타가 많아질테고 리부팅하지 않는한 속도야 빠르겠죠.
실제로 사람들이 검색하는 검색어라는게 대부분 비슷하니 캐시의 적중률도 상당히 높고 말입니다
그리고 파일 시스템의 경우 빠르기는 하겠죠. 문제를 푸는 데에 보다 자유롭게 여러 방법을 사용할 수도 있고 말입니다.
단지 파일시스템을 db로 쓴다면 인터페이스 단에서 php 사용을 포기해야겠죠.
웹프로그램에서 직접 파일을 악세스하려면 c로 cgi를 구성하는 것이 좋겠죠.
아니면 파일시스템을 관리하는 서버를 하나 만들고 php에서 이쪽을 접속하던가 하는 방법이 있겠는데 이거야 mysql의 심플 버전을 만드는 것과 비슷하겠죠.
아무튼 파일시스템으로 가게 되면 여러가지 점에서 어려워집니다. 그래서 현재는 가급적이면 db를 사용하려고 하는 거죠.
물론 db를 사용하는 방식으로는 전혀 비전이 없다면 파일시스템을 심각하게 고려를 하는 수밖에 없겠지만...
10/09 23:52:12 218.147.245.143
> 별거없음
어려운건 없고, 검색조건에 대해 검색영역을 메모리에 올려둔 인덱스 테이블로 부터 받고, 그것을 쿼리에 조건으로 잡고, 추가 조건을 붙여서, 쿼리 생성 본데이터를 뺍니다.
10/09 23:54:24 211.49.30.51
> miplus
검색엔진에서는 DB 잘 사용하지 않습니다. 별도로 파일구조나 기타구조로 인덱싱하죠.
10/10 9:53:21 210.182.140.150
> luna
검색엔진은 데이터를 단어,형태소별로 파싱해서 인덱싱 합니다. 그리고 최적화된 자기만의 DB를 쓰죠..
10/10 13:01:04 203.251.146.109
> 찌뉘
luna님 의견에 한표.. 최적화된 자기만의 DB와 쿼리문장이 제일 좋은 해결책인것 같습니다.
10/10 13:21:39 202.33.246.18
> jinyedge
DB를 쓰던 뭐를 쓰던 검색엔진의 기본은 같습니다. 그리고 AND 검색의 경우도 결국 문제를 압축하면 - 역인덱스 구조라면 말입니다 - 교집합을 구하는 방식으로 가느냐 join을 하는 방식으로 가느냐일 겁니다.
파일시스템으로 간다고 해도 문제가 크게 달라지지는 않을 것입니다.
단지 어려움이 있다면 DB의 용량과 속도에서 오는 제약을 충족하려니 어려워지는거고 저희 같은 경우는 더욱 작은 용량으로 만들려고 하니깐 더 어려워지겠죠.
현재 저희는 용량의 컷트라인을 문서 100만개당 1G로 잡고 있습니다.
그런데 아무래도 AND 검색의 속도를 높이기 위해서는 인덱싱 파일이 하나 더 필요할 것 같아서 용량을 늘려 보기로 생각을 하고 있습니다. 용량을 좀 희생하고 속도를 높인다는 거죠.
아마 30% 가량 데이타베이스의 크기가 증가할 것 같습니다.
그리고 검색엔진 공부하시는 분들을 위해서 저도 문서 하나를 추천하겠습니다.
다음의 문서는 구글의 내부구조에 관해서 논하고 있는 문서입니다.
꼭 검색엔진을 만드려는 분들이 아니라도 대용량 데이타베이스에서의 검색에 관심이 있는 분들이라면 그런대로 유용할 것입니다.
http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm
10/10 13:45:46 218.147.245.143
> jinyedge
익명// 한가지만 물어보겠습니다. 귀사에서 개발한 검색엔진이 현재 저장하고 있는 문서의 갯수는 얼마나 됩니까?
아마 이 정도는 대외비라고 할 것까지는 없을 듯한데 알려 주시면 감사하겠습니다.
제가 생각하기에 informix로 가능하다면 mysql이라고 해서 안될 이유가 없을 것 같군요.
10/10 13:50:33 218.147.245.143
> 11
url 가르쳐 주실수 있나요..?
10/10 17:12:23 61.104.129.100
> 더마린
입력시 인덱싱 해서 별도의 구조로 메모리상에 올리고, 실 데이터는 db에 저장하는게 평균적으로 일정하고 높은 퍼포먼스에, 데이터의 증가와 관련없는 결과를 내올 수 있습니다.
10/10 17:15:09 211.232.135.86
> 더마린
안정성 측면은 얘기되어지고 있지 않은데, 데이터의 사이즈가 어느정도 되고, 1000만번에 한번 안깨지게 하는게 보통 일이 아닙니다.
이를 보장하기 위한 수단과 대용량을 염두해두어야 하는 상황이라면
실데이터는 dbms로 넘기는게 적절한 선택이 될 수 있다는 것도 고려하시기를..
10/10 17:18:16 211.232.135.86
> 전영규
대충 마무리 되는 것 같네요.
jinyedge 님, 저도 만들었던 검색엔진을 개선해서 제 아이디어를 실험해 보려 합니다.
일단 님의 생각과 저도 비슷한 생각을 하고 있습니다.
다만, 좀 더 최적화시키는 자잘한 생각을 더하고 있구요.. 아무래도, 획기적인 개선안은 힘들지 않을까 싶습니다.
링크하신 문서도 도움은 되는데, 님도 결정적 도움을 받지 못하셨듯, 일반 참고정도가 아닐까 싶습니다..
(읽어보려면 시간들어서 .. -_-; 번역기나 하나 구해야 겠습니다.)
님도 계획에 있겠지만, 더 중요한 건 형태소 분석이 아닐까 싶습니다.
다중검색에서 쿼리문을 최적화시키는 데는 형태소분석이 필수조건일 수도 있다는 생각입니다.
그래야 풀 인덱스를 타면서 좀더 빠른 결과를 낼 수 있으니까요..
형태소 분석에 대해 나름대로 연구하는 중이긴 한데, 잘 될지는 모르겠군요. 님은 어떤지 궁금합니다.
어느 대학 교수님이 공개했다는 라이브러리는 몇번 보긴 했는데, 라이센스문제도 있고 별로 효용성은 없어 보이더군요.
-- jeon.
10/10 19:42:43 221.153.4.21
> 익명
jinyedge// 문서의 수는 2003.10.10 20:45 현재 251,374,506 이네요...
10/10 20:48:57 61.78.224.220
> 별거없음
형태소분석이라... 상용검색엔진 직접 만들어보신 분은 아시겠지만,
한글이란 특성 때문에 단위를 형태소 단위로 인덱싱한다는 것 뿐이지, 형태소분석이라 할만한 특이점은 없습니다.
'형태소분석'이란 작업은 자연어검색을 위한 사전작업때 사람이 손으로 일일이 수행하는 것 말고는 형태소분석이란 것은 아예 존재하지 않습니다. 포공, 카이스트 출신의 자연어석박사분들께 물어보시길..
lucene을 뜯어보거나, 검색엔진 작업을 해보시면 아시겠지만 단위별(형태소든, 띄어쓰기단어든) 인덱싱(의미및 구조에 따른 인덱싱이 아닌, 일괄적용 알고리즘의 인덱싱입니다)이
검색엔진의 주된 모든 작업이고, 이후의 작업은 Tree쓰던, DB쓰던 별거없음..
file DB로 0.1초 빠르게 만들게 하기 위해 1-2개월씩 보내면 대략 낭패~
10/10 21:52:14 211.49.30.191
> 별거없음
검색엔진 만들고 싶은 사람은 다른거 필요없이 lucene을 한번 뜯어보면 아햏햏~
10/10 21:53:55 211.49.30.191
> 전영규
별거없음님, 경험이 많으신 것 같습니다 ^^
형태소분석에 대해서는 사실 용언분석까지는 아니고, 복합명사나 조사분리 정도로 된다고 보구요..
그것만으로도 데이타나 코드가 좀 필요하더군요 -_-; 일단 생각대로 구현해 보고...
lucence 는 소스가 너무 커서 일일히 볼 시간이 없습니다. -_-;
대충 봤는데, '속도' 보다는 '기능성' 에 치중한 것 같더군요. 그런데 .. 저는 속도에 더 관심이 많습니다.. ^^;
-- jeon.
10/11 0:06:56 221.153.4.21
> jinyedge
익명// 좋은 정보 감사합니다.
10/11 10:18:29 61.84.19.130
> jinyedge
11// 그다지 비밀이라고 할 것도 없죠. http://www.skouter.com 입니다.
10/11 10:19:35 61.84.19.130
> jinyedge
전영규// 처음에 개발초기에서는 형태소 분석을 저도 중요하다고 생각했습니다.
그러나 지금은 아닙니다. 그냥 -에, -의, -을, -를 등의 조사 처리만 하고 그외의 복합명사 같은 건 무시하려고 합니다.
기본적으로 형태소 분석의 프로그램적인 처리는 불가능하다는 게 제 입장입니다. 아래에서 강산에의 경우 무슨 차이가 있습니까?
1. 아름다운 우리 강산에 한 그루 나무를 심는다면..
2. 강산에 (가수) 프로필.
우리는 눈으로 보고 바로 차이를 알 수 있죠. 2개의 강산에는 서로 다른 겁니다.
그러나 프로그램적으로 이 차이를 알 수 있나요? 실제 형태소분석 기술을 자랑하는 모 검색엔진에서는 강산에라는 키워드로 검색하면 우리강산 좋은 강산 이라는 식의 웹페이지들만 잔뜩 나오죠.
이것은 기본적으로 검색을 하려는 사람이 입력하는 키워드를 지나치게 가공/변형하거나 웹문서의 인덱싱 과정에서 키워드들을 지나치게 가공/변형한 결과입니다. 이런식으로 인위적인 가공을 하게 되면 특정 상황에서만 좋은 결과를 얻게 마련입니다.
한가지 예를 더 들겠습니다. 우리가 인하대학교 웹사이트를 찾을 때 어떤 검색어를 입력하나요? 아마 다음의 검색어들이 가능할 겁니다.
• 인하, 인하대, 인하대학교, 인하 + 대학교
그럼 인하대학교라는 단어 하나에서 꼭 이 많은 걸 뽑아내야만 인하대학교를 위의 검색어로 검색할 수 있을까요?
저는 그렇지 않다고 생각합니다.
사람들이 인하대학교를 인하대라고 지칭하기도 한다면 즉 그 말이 실제로 쓰인다면 인하대로 검색을 해도 인하대학교 웹페이지를 찾을 수 있는 겁니다. 물론 여기에는 몇가지 전제조건이 붙기는 하지만 말입니다.
뭐.. 아무튼 지금은 형태소 분석에는 관심이 없습니다. 가능하다고 생각하지도 않고 가능한지 몰라도 별 필요는 없다는 게 제 입장입니다.
그냥 여기까지만 하도록 하겠습니다.
10/11 10:36:20 61.84.19.130
> 전영규
jinyedge님, 저와 생각이 다르시군요. ^^
-- jeon.
10/11 12:58:08 221.153.4.21
> 나그네
형태소 분석 같은 시도가 없다면 검색엔진은 단지 인덱스 생성기에 지나지 않을 것 같다는 생각이 드네요.
그 이상의 발전을 기대할 수 있을까요?
10/11 15:06:44 211.245.200.32
> jinyedge
나그네// 단지 인덱스 생성기라... 글쎄요... 검색엔진 생각보다 재밌는 부분이 많습니다.
한국 사람이 검색을 한다면 대부분 옥션을 입력하면 www.auction.co.kr 이 최상위에 나오기를 기대하고 mbc를 입력하면 www.imbc.com이 나오기를 기대하고 다음을 입력하면 www.daum.net 이 나오기를 기대하겠죠.
그런데 이렇게 나오게 한다는게 말처럼 쉽지가 않죠.
갖가지 랭킹조작을 하려는 시도가 난무하는 공간이 인터넷이죠.
다음의 예는 구글에서 옥션이라는 검색어를 입력하면 나오는 웹문서 중의 하나입니다.
---------------------------
이양 이양 이양 이양 이양 이양 이양 이양 이양 ...
... 최신주드한국뽀르노한국성인동영상홍콩아마추어변태섹 스벅스뮤직세이클
럽넷마블네이버다모임한미르엠파스엽기라이코스한게임스포츠조선크레이
지아케이드스포츠서울일간스포츠아이러브스쿨게임옥션바람의나라지오피
아 ...
---------------------------
이런 문서가 상위권에 나온다는 건 좀 문제가 있겠죠. 일차로 이 따위 문서로 랭킹 조작을 하는 사람이 문제가 있겠지만 말입니다.
그리고 인덱싱이 검색엔진의 전부는 아닙니다. 크롤러에서도 재밌는 문제는 많습니다.
예를 들자면 옥션의 경우 현재 야후, 한미르, 드림위즈, 천리안, 조선일보 등에 서브 도메인 형태로 들어가 있습니다.
사실은 동일한 사이트인데 이름만 다른 케이스죠. 이때 이 문서들을 모두 저장을 해야 할까요?
서브 도메인 10개면 중복 문서 10개라는 건데 이런 건 어떻게 처리해야 될까요?
만약 중복문서라고 저장을 안 하기로 했다면 무엇을 남겨야 할까요?
뭐.. 생각하기에는 www.auction.co.kr이 오리지날이니 이것만 남기자고 생각할 수도 있겠는데 이걸 프로그램으로는 어떻게 구분하나요?
먼저 저장된 걸 기준으로? 만약 auction.chol.com 이 먼저 저장되면 어떻게 하나요?
그럼 www.auction.co.kr은 저장이 안 될텐데... 뭐.. 이런 식의 문제가 끝도 없이 나타납니다.
그리고 이런 문제에 대해서 정책을 수립하고 실제 프로그래밍을 통해서 그 정책을 구현하는 게 검색엔진을 만드는 작업이겠죠.
또 이런 부분들이 제가 생각하는 검색엔진의 재밌는 부분이라는 거죠.
댓글 없음:
댓글 쓰기