다음과 같이 id, date_time의 필드를 가진 테이블이 있다 하자.
(예시의 자료 개수는 1000개이며, 직접 입력하고 싶다면 date_time.txt파일을 참고)
인덱스(index)는 id 필드에만 적용되어 있고, date_time 필드에는 없는 상황.
만일 테이블의 크기가 매우 클 경우, 쿼리에 조건을 다음과 같이 date_time 으로 걸면 질의시간이 상당히 오래 걸리게 된다.
SELECT * FROM date_table WHERE date_time>='2018-01-15' and date_time<'2018-02-15';
특정 date_time에 해당하는 id 를 찾을 수 있다면 다음과 같이 바꾸어 질의할 수 있다.
SELECT * FROM date_table WHERE id>='229' and id<'793';
id 에는 인덱스가 있으므로 시간이 매우 단축될 것이다.
인덱스가 없는 필드의 값으로 인덱스가 있는 필드의 값을 알아내는 코드를 작성해 보자.
일단 PHP틀을 만들고
<?php $conn = mysqli_connect("localhost", "root", "123456789"); mysqli_select_db($conn, "test"); ?> <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php ?> </body> </html>
해당 테이블의 가장 큰 id 를 변수로 저장하자.
우리는 바이너리 서치 Binary Search 라는 전략을 사용할 것인데,
쉽게 말하면 주어진 자료를 계속 반으로 나누며 원하는 값을 찾는 방법이다.
(이미지 출처: wikipedia)
가장 큰 id 값의 절반에서 시작해야 하므로, 일단 다음과 같이 가장 큰 id 값을 $max 에 저장한다.
$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php $query = 'SELECT max(id) FROM date_table'; $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $max = $row[0]; ?> </body> </html>
이어서 우리가 찾고자 하는 날짜도 $date 에 설정해 놓고, 최소값 $min 도 1로 놓자.
$min = 1;
$date = '2018-01-15';
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php $query = 'SELECT max(id) FROM date_table'; $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $max = $row[0]; $min = 1; $date = '2018-01-15'; ?> </body> </html>
이제 프로세스는 다음과 같다.
일단 최소값과 최대값의 평균으로 ID를 추측한다.
만일 추측한 아이디에 해당하는 날짜가, 우리가 설정해 놓은 $date 보다 크다면
$date에 해당하는 아이디는 왼쪽 절반에 있을 것이다.
이제 이전에 추측한 ID를 최대값(Max)으로 세팅하고, 다시 최소값과 최대값의 평균으로 ID를 추측한다.
만일 추측한 아이디에 해당하는 날짜가, 우리가 설정해 놓은 $date 보다 작다면
$date에 해당하는 아이디는, 이번에는 오른쪽에 있을 것이다.
이전에 추측한 ID는 최소값(Min)이 되고, 새롭게 ID를 추측한다.
이와 같은 과정을 반복하면 되겠다.
일단 $id 를 최소값과 최대값의 평균으로 설정한다.
$id = round(($min+$max)/2);
id 는 정수여야하므로 결과를 round()에 넣어 반올림해 주었다.
이제 $id 로 쿼리를 돌려 나온 날짜를 파악한다.
$query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$row[1] = substr($row[1], 0, 10);
date_time 필드에서 시간은 필요 없으므로, substr() 을 이용해 왼쪽부터 10글자까지 잘라주었다.
만일 이렇게 나온 날짜가 $date보다 크다면 $id 는 $max가 되고, 새로운 $id는 $min과 $max의 평균으로 정의된다.
if($row[1]>$date){
$max = $id;
$id = round(($min+$max)/2);
}
만일 $row[1] 이 $date보다 작다면 $id 는 $min이 되고, 새로운 $id는 $min과 $max의 평균으로 정의된다.
else if($row[1]<$date){
$min = $id;
$id = round(($min+$max)/2);
}
여기까지 코드를 보면 다음과 같다.
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php $query = 'SELECT max(id) FROM date_table'; $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $max = $row[0]; $min = 1; $date = '2018-01-15'; $id = round(($min+$max)/2); $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id); $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $row[1] = substr($row[1], 0, 10); if($row[1]>$date){ $max = $id; $id = round(($min+$max)/2); } else if($row[1]<$date){ $min = $id; $id = round(($min+$max)/2); } ?> </body> </html>
이제 날짜를 구하고 (크면/작으면)을 판단하는 부분을 반복문 안에 넣어 원하는 결과를 얻을 때까지 반복해야 한다.
$row[1]이 $date보다 크지도 작지도 않으면 반복을 멈추도록 하면 되겠다.
$end라는 변수를 생성해 다음과 같이 while()문을 만든다.
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php $query = 'SELECT max(id) FROM date_table'; $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $max = $row[0]; $min = 1; $date = '2018-01-15'; $id = round(($min+$max)/2); $end = 0; while($end == 0){ $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id); $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $row[1] = substr($row[1], 0, 10); if($row[1]>$date){ $max = $id; $id = round(($min+$max)/2); } else if($row[1]<$date){ $min = $id; $id = round(($min+$max)/2); } else { $end = 1; } } ?> </body> </html>
$end = 0;
으로 설정해 놓고
while($end == 0){
으로 반복문을 돌린다.
원하는 조건이 만족될 경우
else {
$end = 1;
}
으로 탈출하게 될 것이다.
이것만으로는 결과가 나오지 않으므로 while 문 바깥에 echo로 결과를 출력한다.
echo $id;
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php $query = 'SELECT max(id) FROM date_table'; $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $max = $row[0]; $min = 1; $date = '2018-01-15'; $id = round(($min+$max)/2); $end = 0; while($end == 0){ $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id); $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $row[1] = substr($row[1], 0, 10); if($row[1]>$date){ $max = $id; $id = round(($min+$max)/2); } else if($row[1]<$date){ $min = $id; $id = round(($min+$max)/2); } else { $end = 1; } } echo $id; ?> </body> </html>
완성이다. 실행시켜보자.
결과가 나오고 있다. id 251번에 해당하는 날짜는 2018-01-15일 것이다.
좋지만, 우리는 2018-01-15에 해당하는 첫 번째 아이디를 찾고 싶으므로
다시 Binary Search를 한번 더 돌려야 한다.
아까와 완전히 동일한 구조에, 다음 부분만 달라지면 되겠다.
$id 에 해당하는 날짜가 $date 와 같을 경우 해당 값을 $max로 설정
$id 에 해당하는 날짜가 $date 와 다를 경우 해당 값을 $min으로 설정
그러면 Binary Search 는 날짜가 달라지는 경계 지점까지 수렴해 들어갈 것이다.
코드는 다음과 같다.
$end = 0;
while($end == 0){
$query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$row[1] = substr($row[1], 0, 10);
if($row[1]==$date){
$max = $id;
$id = round(($min+$max)/2);
} else {
$min = $id;
$id = round(($min+$max)/2);
}
if($max==$min+1){
$end = 1;
}
}
앞선 반복문과 동일한 구조다. 언급한대로 (크면/작으면) 대신 (같으면/다르면)을 판단하도록 하고,
수렴한 결과 $max 가 $min 과 1 차이 나면 반복문을 종료하도록 한다.
여기까지 코드를 다시 실행시켜보자.
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php $query = 'SELECT max(id) FROM date_table'; $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $max = $row[0]; $min = 1; $date = '2018-01-15'; $id = round(($min+$max)/2); $end = 0; while($end == 0){ $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id); $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $row[1] = substr($row[1], 0, 10); if($row[1]>$date){ $max = $id; $id = round(($min+$max)/2); } else if($row[1]<$date){ $min = $id; $id = round(($min+$max)/2); } else { $end = 1; } } $end = 0; while($end == 0){ $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id); $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $row[1] = substr($row[1], 0, 10); if($row[1]==$date){ $max = $id; $id = round(($min+$max)/2); } else { $min = $id; $id = round(($min+$max)/2); } if($max==$min+1){ $end = 1; } } echo $id; ?> </body> </html>
결과는 다음과 같다.
2018-01-15가 처음 등장하는 id는 229번이다.
허전하다면 while문 안쪽에 id를 찾아가는 과정을 보여주도록 echo문을 넣어도 좋다.
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <?php $query = 'SELECT max(id) FROM date_table'; $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $max = $row[0]; $min = 1; $date = '2018-01-15'; $id = round(($min+$max)/2); $end = 0; while($end == 0){ echo $id,"<BR>"; $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id); $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $row[1] = substr($row[1], 0, 10); if($row[1]>$date){ $max = $id; $id = round(($min+$max)/2); } else if($row[1]<$date){ $min = $id; $id = round(($min+$max)/2); } else { $end = 1; } } $end = 0; while($end == 0){ echo $id,"<BR>"; $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id); $result = mysqli_query($conn, $query); $row = mysqli_fetch_row($result); $row[1] = substr($row[1], 0, 10); if($row[1]==$date){ $max = $id; $id = round(($min+$max)/2); } else { $min = $id; $id = round(($min+$max)/2); } if($max==$min+1){ $end=1; } } echo $id; ?> </body> </html>
결과는 다음과 같다.
251이 두 번 나타나는 것으로 보아
첫 Binary Search로 2018-01-15에 해당하는 아이디는 단 두 번 만에 찾고,
두 번째 Binary Search로 2018-01-15에 해당하는 첫 번째 아이디를 찾아가는 것을 볼 수 있다.
조금 더 찾기 힘든 날짜로 설정해 보자.
$date = '2018-02-28' 로 실행하면 다음과 같다.
첫 Binary Search 는 7번 만에 993에서 확신하고, 이후로 범위를 좁히는 것을 볼 수 있다.
'PHP' 카테고리의 다른 글
[PHP] $i++ 과 ++$i 의 차이 (0) | 2018.06.21 |
---|---|
[PHP] 에러메시지 Undefined offset 의미 (0) | 2018.06.20 |
[PHP] 회원들의 재구매율 알아보기(4) - 완성 (0) | 2017.10.13 |
[PHP] 회원들의 재구매율 알아보기(3) - 날짜 계산하기 strtotime() (0) | 2017.09.26 |
[PHP] 회원들의 재구매율 알아보기(2) - 두 배열 비교하기 in_array() (0) | 2017.09.25 |
[PHP] 회원들의 재구매율 알아보기(1) - MySQL 컬럼(열)을 배열로 만들기 (0) | 2017.09.24 |
[PHP] mysqli_fetch_row, assoc, array 의 차이 (4) | 2017.09.20 |
[PHP] DB에서 특정 행들만 가져오기(8) - DB 에서 열 이름 가져오기 (0) | 2017.09.19 |
[PHP] DB에서 특정 행들만 가져오기(7) - DB에서 가져온 정보 출력하기 mysqli_fetch_row() (0) | 2017.09.18 |
[PHP] DB에서 특정 행들만 가져오기(6) - 쿼리 작성하기 mysqli_query() (0) | 2017.09.17 |
댓글