접두어 검색을위한 최적의 DB 쿼리

Question

접두어 범위 목록이며 모든 접두사가 같은 크기가 아닙니다. 다음은 몇 가지 예입니다.

low: 54661601 high: 54661679 "bin": a 
low: 526219100 high: 526219199 "bin": b 
low: 4305870404 high: 4305870404 "bin": c 

"bin"은 해당 접두사가있는 특정 값에 해당하는지 조회하고 싶습니다. 예를 들어, 값 5466160179125211은 "bin"a에 해당합니다. 오버랩의 경우 (그 중 일부만 있음) 가장 긴 접두어 또는 모든 접두사를 반환 할 수 있습니다.

최적의 알고리즘은 명확하게 bin 객체가 삽입 될 수있는 일종의 트리입니다. 트리의 각 연속 레벨은 더 많은 접두사를 나타냅니다.

질문은 다음과 같습니다. 데이터베이스에서이 질문을 (한 가지 쿼리로) 어떻게 구현합니까? 데이터 세트를 변경/추가하는 것은 허용됩니다. 무엇이 최고의 데이터 & 쿼리 디자인이 될 것이라고? mongo 또는 MySQL을 사용하는 것이 가장 좋습니다.

Answer 1

MySQL에서는 저장 프로 시저 (stored procedure)를 사용해야 할 수도 있습니다. 저장 프로 시저를 사용하면 값을 bin으로 호출 할 수 있습니다. 이 절차는 각 행에 대한 버킷 목록을 쿼리하고 산술 또는 문자열 연산을 수행하여 일치하는 버킷을 찾습니다. 고정 된 길이의 접두사를 사용하여 고정 된 수의 레이어로 배열하여이 디자인을 향상시킬 수 있습니다. 트리에 고정 된 깊이를 할당 할 수 있으며 각 레이어에는 테이블이 있습니다. 이러한 접근 방법 중 하나를 사용하면 나무와 같은 성능을 얻지 못할 것입니다.

좀 더 정교한 작업을 원하면 다른 플랫폼을 사용해야 할 것으로 생각됩니다. http://technet.microsoft.com/en-us/library/bb677173.aspx

의 PostgreSQL는 CIDR 데이터 형식이 있습니다

SQL Server는 계층 구조 데이터 유형이 있습니다. 나는 그것이 가지고있는 질의 지원 수준에 익숙하지 않다. 그러나 이론적으로 당신은 DB 내부에 라우팅 테이블을 만들어 버킷을 할당하기 위해 사용할 수있다 : http://www.postgresql.org/docs/7.4/static/datatype-net-types.html#DATATYPE-CIDR

Answer 2

"최적"은 다른 사람들에게 다른 것을 의미 할 수있다. . 당신이 varchars로 낮은 값과 높은 값을 저장하는 것과 같은 것을 할 수있는 것 같습니다. 그럼 당신이해야 할

select bin from datatable where '5466160179125211' between low and high 

이다 또는 당신이 테이블에 정수로 값을 유지하는 몇 가지 이유가 있다면, 당신은 쿼리의 캐스팅을 할 수 있습니다.

큰 데이터 세트로 인해 성능이 저하 될지 여부는 알 수 없습니다. 그리고 내가하고 싶은 것을 이해하기를 바랍니다.

Answer 3

페이튼! 당신은 정수로 모든 것을 유지해야하고, 그것을 단일 쿼리 작업 할 경우 :

이 작동합니다 :

select bin from datatable where 5466160179125211 between 
     low*pow(10, floor(log10(5466160179125211))-floor(log10(low))) 
    and ((high+1)*pow(10, floor(log10(5466160179125211))-floor(log10(high)))-1); 

를이 경우, (가장 낮은 번호 5466160100000000 사이에 검색 할 것 낮은 접두사 &과 찾을 숫자의 자릿수가 같은 낮은 번호) 및 546616799999999 (찾을 수만큼 동일한 자릿수 & 높은 접두사가있는 높은 번호). 높은 접두사가 낮은 접두사보다 많은 자릿수를 갖는 경우에도 여전히 작동해야합니다. 또한 이전 솔루션의 varchar 코드가 잘못된 결과를 줄 수있는 접두어의 길이보다 번호가 짧은 경우에도 작동해야합니다.

이 솔루션에서와 같이 쿼리에서 인라인 수학을 많이 사용하는 경우의 성능과 varchars를 사용하는 경우의 성능을 비교해보십시오.

편집 : 인덱스가없는 큰 테이블에서도 성능이 좋은 것으로 보입니다. varchars를 사용할 수있는 경우 낮은 열과 높은 열을 인덱싱하여 성능을 추가로 향상시킬 수 있습니다. 접두사 중 하나라도 초기 0이있는 경우 varchars를 사용하고 싶을 것입니다. 다음으로 VARCHAR 사용할 때 숫자가 접두사보다 짧은 경우에 허용하는 수정 : 당신이 당신의 접두사 범위에서 중복 수에 대한 온화한 가정을하면

select * from datatable2 where '5466' between low and high 
    and length('5466') >= length(high); 

Answer 4

, 무엇을 할 수 있습니다 당신 MongoDB 또는 MySQL을 사용하여 최적으로 사용하고 싶습니다. 아래의 답에서 MongoDB를 설명 하겠지만이 대답을 MySQL로 이식하는 것은 쉽습니다.

먼저 문제를 조금 수정 해 보겠습니다. "접두어 범위"를 매칭하는 것에 대해 이야기 할 때, 나는 당신이 실제로 말하고있는 것은 사전 식 주문 (직관적으로 이것은 문자열의 자연 알파벳 순서 임)에서 올바른 범위를 찾는 것이라고 믿습니다. 예를 들어, 접두사가 54661601 ~ 54661679와 일치하는 숫자 세트는 문자열로 쓰여졌을 때 사전 식으로 "54661601"보다 크거나 같지만 사전 식으로 "54661680"보다 작은 숫자 세트입니다. 따라서 가장 먼저해야 할 일은 모두 의 범위를 1로 늘려서 범위를 지정하는 것입니다. 이렇게하면이 방법으로 쿼리를 표현할 수 있습니다.

{low: "54661601", high: "54661680", bin: "a"} 
{low: "526219100", high: "526219200", bin: "b"} 
{low: "4305870404", high: "4305870405", bin: "c"} 

지금 문제가되고처럼 몽고에서 문서가 보일 것입니다 : 양식 [낮은, 높은)의 1 차원 간격의 세트가 지정되면, 우리는 신속하게 (이 간격을 찾을 수있는 방법 s)에 주어진 점이 있습니까? 이를 수행하는 가장 쉬운 방법은 낮은 또는 높은 필드의 색인을 사용하는 것입니다. 높음 필드를 사용합니다. mongo 쉘에서 :

db.coll.ensureIndex({high : 1}) 

이제는 간격이 전혀 겹치지 않는다고 가정 해 봅시다. 이 경우 주어진 쿼리 포인트 "x"에 대해 "x"를 포함 할 수있는 유일한 간격은 이 고 값이 "x"보다 큰 값입니다. 따라서 해당 문서를 쿼리하여 값이 0 일 때 값이 "x"보다 작은 지 여부를 확인할 수 있습니다.

이

db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(1).forEach(
     function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
) 

대신 전혀 중복되지 않는 간격을 가정 지금의 가정, 당신은 모든 간격 미만 K와 겹치는 것을 가정가있는 ​​경우 예를 들어,이, 일치하는 간격을 인쇄합니다 이웃 한 간격 (나는 의 어떤 값이인지 알지 못한다. 이 경우, 당신은, 위의 "제한"에 K 1을 대체 할 수있는 즉

db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(k).forEach(
     function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
) 

무엇이 알고리즘의 실행 시간을입니까?인덱스는 B 나무를 사용하여 저장되므로, 데이터 세트의 N 간격이있을 경우,이 O을 얻어 다음 높은 값, O (K가 최초로 일치하는 문서를 조회 할 시간 (N 로그)) 시간이 다음 k 문서를 반복 할 때 총 O (로그 n + k) 시간이됩니다. k이 상수이거나 실제로 O보다 작 으면 (로그 n)이 점은 점근 적으로 최적입니다 (표준 계산 모델에 있음, 외부 메모리 전송 횟수 또는 기타 정보는 계산하지 않음) .

균열이있는 유일한 경우는 k이 큰 경우입니다. 예를 들어 큰 간격에 거의 모든 다른 간격이있는 경우입니다. 이 경우 실행 시간은 O (n)입니다. 데이터가 이와 같이 구조화 된 경우 다른 방법을 사용하는 것이 좋습니다. 한 가지 방법은 당신의 낮은 및 높은 값이 X 및 Y 좌표를 성문화와, 몽고의 "2D"인덱싱을 사용하는 것입니다. 그러면 검색어는 x-y 평면의 특정 지역에있는 지점을 쿼리하는 것과 일치합니다. 비록 2d 인덱싱의 현재 구현에서는 최악의 경우가 여전히 O (n)이지만 이것은 실제로 잘 수행 될 수 있습니다.

는 O 달성 이론적 결과 개수가 K 의 모든 값에 대한 성능 (N 로그)이있다. 우선 순위 검색 트리, 세그먼트 트리, 간격 트리 등의 이름을 사용합니다. 그러나 이들은 사용자가 직접 구현해야하는 특수 용도의 데이터 구조입니다. 내가 아는 한, 현재 널리 사용되는 데이터베이스는 없습니다.