BOJ의 채점 현황은 유저가 제출한 솔루션의 정보를 볼 수 있는 페이지입니다.

주소: https://www.acmicpc.net/status

검색도 지원합니다.

페이지에서 직접 선택/입력할 수 있는 항목은 다음과 같습니다.

1. 문제 번호
2. 아이디
3. 언어
4. 결과

다른 메뉴를 통해서 설정할 수 있는 항목은 대회, 문제집, 문제 출처, 학교/회사, 그룹 등이 있긴 하지만, 이번 글에서는 중요한 정보가 아니기 때문에, 생략하겠습니다.

유저의 솔루션을 담고 있는 테이블 solution은 아래와 같이 생겼습니다. (BOJ에서 사용하는 테이블은 아니고, 이번 포스팅을 위해 만든 테이블)

+---------------+------------+------+-----+---------+----------------+
| Field         | Type       | Null | Key | Default | Extra          |
+---------------+------------+------+-----+---------+----------------+
| solution_id   | int(11)    | NO   | PRI | NULL    | auto_increment |
| problem_id    | int(11)    | NO   | MUL | 0       |                |
| result        | tinyint(4) | NO   | MUL | 0       |                |
+---------------+------------+------+-----+---------+----------------+

result는 채점 결과를 담고 있으며, 0부터 13까지 총 14개의 값 중 하나입니다.

채점 현황의 첫 페이지를 조회하려면 아래와 같은 쿼리면 될 것 같습니다. 한 페이지에는 20개의 결과만 보여준다고 가정합니다.

SELECT * FROM `solution` WHERE 1 ORDER BY `solution_id` DESC LIMIT 20

채점 현황에서 페이지의 개수는 의미가 없습니다. 또, 몇 페이지에 무슨 정보가 있는지도 중요한 정보가 아닙니다.

따라서, 현재 페이지 첫 결과의 채점 번호를 이용해서 화면을 구성합니다.

페이지의 첫 채점 번호는 top, 마지막 채점 번호는 bottom이라고 하겠습니다.

현재 페이지의 다음 페이지를 조회하려면 어떻게 해야할까요?

현재 페이지에 보이는 채점 번호가 7951563 ~ 7951544 라고 한다면, 다음 페이지의 top은 7951543이 되어야 합니다.

따라서, 다음과 같은 쿼리를 이용해 다음 페이지를 조회할 수 있습니다.

SELECT * FROM `solution` WHERE `solution_id` <= 7951543 ORDER BY `solution_id` DESC LIMIT 20

하지만 검색이 적용되었다면, 다음 페이지의 top이 현재 페이지의 bottom - 1이 아닐 수도 있습니다.

결과가 4 (맞았습니다!) 인 것을 검색한다면, 다음과 같은 쿼리를 이용해야 합니다.

SELECT * FROM `solution` WHERE `result` = 4 ORDER BY `solution_id` DESC LIMIT 20

bottom이 7951655인 경우에 다음 페이지를 조회하는 쿼리는 아래와 같습니다.

SELECT * FROM `solution` WHERE `result` = 4 AND `solution_id` <= 7951654 ORDER BY `solution_id` DESC LIMIT 20

하지만, 다음 페이지의 top이 7951654가 아닐 수도 있기 때문에, 올바른 쿼리라고 할 수 없습니다.

올바른 다음 페이지의 top값을 구하기 위해서 현재 페이지의 쿼리를 수정했습니다.

SELECT * FROM `solution` WHERE `result` = 4 ORDER BY `solution_id` DESC LIMIT 21

LIMIT 20을 LIMIT 21로 수정해 마지막 결과는 화면에 보여주지 않고, 다음 페이지 링크를 만드는데 이용할 수 있습니다.

그런데…

사실 생각해보면 다음 페이지의 top 값은 그렇게 정확할 필요가 없습니다. 위에서 설명한 두 방법 모두 같은 결과를 보여주기 때문입니다.

LIMIT 21을 사용한 방법의 장점은 다음 페이지가 있는지 없는지를 알 수 있다는 장점이 있습니다. 만약, 다음 페이지 링크를 눌렀는데, 다음 페이지가 빈 결과라면 오류가 난 것인지, 진짜 결과가 없는 것인지 알 수 없습니다. 따라서, 다음 페이지의 top은 LIMIT 21의 마지막 값을 이용하는 것으로 했습니다.

이제 이전 페이지 링크를 만들어 봅시다.

이전 페이지의 top값은 어떻게 구해야 할까요?

가장 쉬운 방법은 다음 페이지의 주소에 prevtop을 추가하는 것 입니다. 어떤 페이지에 다음 페이지 링크를 통해서 왔다면, 이전 페이지의 주소를 만들 때, prevtop을 이용하는 방법이 있습니다.

이 방법은 hustoj를 기반으로 하는 온라인 저지 사이트 (Judgeon, CodeUp) 에서 사용하고 있습니다.

단점으로는 다음 페이지 링크를 통하지 않은 경우에 prevtop을 구할 수 없다는 것이 있습니다.

다른 방법은 bottom을 이용하는 것 입니다.

어떤 페이지의 top이 7951563 이고, bottom이 7951544라면, 이전 페이지의 bottom은 7951564이기 때문에, 쿼리를 다음과 같이 만들 수 있습니다.

SELECT * FROM `solution` WHERE `solution_id` >= 7951564 ORDER BY `solution_id` ASC LIMIT 20

그런데, 채점 현황은 채점 번호가 내림차순이 되어야 합니다. 따라서, 결과의 순서를 뒤집어주는 과정이 필요합니다.

이 방법은 POJ, Lavida에서 사용하고 있습니다.

주소에 top과 bottom이 동시에 있는 경우, 이전 페이지의 존재 여부를 확인할 수 없다는 단점이 있습니다.

이전 페이지의 top을 올바르게 구하기 위해서, 그냥 쿼리를 한 번 더 사용하기로 했습니다.

현재 페이지의 top이 7951654라면, 아래와 같은 쿼리로 이전 페이지의 top을 구할 수 있습니다.

SELECT * FROM `solution` WHERE `solution_id` > 7951654 ORDER BY `solution_id` ASC LIMIT 19,1

그런데, 이 쿼리는 이전 페이지 결과의 개수가 20개 미만인 경우에는 top을 구할 수 없기 때문에, LIMIT 19,1 대신 LIMIT 20을 사용하고, 마지막 채점 번호를 이용해 top을 구하기로 합시다.

정리해보면, 어떤 페이지의 top이 7951654 라면, 다음 두 방법으로 다음 페이지의 top과 이전 페이지의 top을 구할 수 있습니다

현재 페이지 및 다음 페이지의 top (21번째 채점 번호, 없으면 다음 페이지 없음)

SELECT * FROM `solution` WHERE `solution_id` <= 7951654 ORDER BY `solution_id` DESC LIMIT 21

이전 페이지의 top (마지막 채점 번호)

SELECT * FROM `solution` WHERE `solution_id` > 7951654 ORDER BY `solution_id` ASC LIMIT 20

이제, 쿼리를 수행하는데 걸리는 시간을 재보려고 합니다.

전체 제출이 약 8백만개인 경우에 임의의 top을 고르고, 두 쿼리를 수행하는데 걸리는 조사해봤습니다.

• top = 3456453
  • 현재 페이지 및 다음 페이지: 0.11초
  • 이전 페이지: 0.09초
• top = 2133432
  • 현재 페이지 및 다음 페이지: 0.08초
  • 이전 페이지: 0.08초
• top = 7777777
  • 현재 페이지 및 다음 페이지: 0.08초
  • 이전 페이지: 0.09초

이정도면 충분히 빠른 것 같습니다.

이번에는 결과가 4 (맞았습니다!) 인 것을 검색하는 경우 시간을 조사해봤습니다.

• top = 3456453
  • 현재 페이지 및 다음 페이지: 7.23초
  • 이전 페이지: 0.21초
• top = 2133432
  • 현재 페이지 및 다음 페이지: 6.01초
  • 이전 페이지: 0.09초
• top = 7777777
  • 현재 페이지 및 다음 페이지: 0.21초
  • 이전 페이지: 0.04초

쿼리 하나가 6~7초 정도가 걸리는 것은 매우 절망적입니다.

그런데, 현재 페이지 및 다음 페이지는 느린데, 왜 이전 페이지는 빠를까요?

EXPLAIN을 이용해 현재 페이지 및 다음 페이지 쿼리가 오래걸리는지 조사해봤습니다.

EXPLAIN SELECT * FROM `solution` WHERE `result` = '4' AND `solution_id` <= 3456453 ORDER BY `solution_id` DESC LIMIT 21;

+----+-------------+----------+------+---------------+------+---------+-------+---------+-------------+
| id | select_type | table    | type | possible_keys | key  | key_len | ref   | rows    | Extra       |
+----+-------------+----------+------+---------------+------+---------+-------+---------+-------------+
|  1 | SIMPLE      | solution | ref  | PRIMARY,res   | res  | 2       | const | 1462378 | Using where |
+----+-------------+----------+------+---------------+------+---------+-------+---------+-------------+

여기서 res는 result의 인덱스 이름입니다.

세상에 1462378개라니… 쿼리가 느릴 수 밖에 없네요.

이전 페이지 쿼리는 어떨까요?

+----+-------------+----------+------+---------------+------+---------+-------+---------+------------------------------------+
| id | select_type | table    | type | possible_keys | key  | key_len | ref   | rows    | Extra                              |
+----+-------------+----------+------+---------------+------+---------+-------+---------+------------------------------------+
|  1 | SIMPLE      | solution | ref  | PRIMARY,res   | res  | 2       | const | 3635748 | Using index condition; Using where |
+----+-------------+----------+------+---------------+------+---------+-------+---------+------------------------------------+

이전 페이지는 어떤 값보다 큰 것 중에 오름차순으로 20개를 고르는 쿼리라 인덱스를 이용해 빠르게 검색할 수 있습니다.

하지만, 현재 페이지 및 다음 페이지는 작거나 같은 값 중에서 채점 번호 순으로 내림차순으로 21개를 고르는 쿼리이기 때문에 인덱스를 사용하지 못합니다.

BOJ는 MySQL 5.6을 사용하고 있습니다. 인덱스와 관련된 MySQL 메뉴얼을 보면, 분명 index_col_name에 DESC를 입력할 수 있습니다. 하지만, 하단의 내용을 보면 이런 내용이 있습니다.

An index_col_name specification can end with ASC or DESC. These keywords are permitted for future extensions for specifying ascending or descending index value storage. Currently, they are parsed but ignored; index values are always stored in ascending order.

안타깝게도 현재 버전에서 인덱스는 항상 오름차순으로 저장된다고 합니다. MySQL 8.0은 내림차순 인덱스를 지원하지만, 아직 나오지도 않은 버전입니다. 또한, RDS에서 지원하지도 않습니다.

어쩔 수 없이 다른 방법을 생각해봐야 합니다.

첫 번째로 생각한 방법은 내림차순 인덱스를 지원하는 Oracle을 사용하는 것입니다. 하지만, 너무 할 일이 많아지고, RDS 비용도 두 배 증가하기 때문에 이 방법은 스킵하겠습니다.

두 번째로 생각한 방법은 solution_desc라는 테이블을 만들고, solution 테이블과 동일한 결과를 갖지만, 제출 번호 (solution_id)만 음수로 저장하는 것입니다.

이건 너무 복잡하고 번거로운 방법입니다.

BOJ에서 선택한 방법은 DB의 구조를 변경하는 것 입니다. solution_desc를 추가하고, 항상 solution_id의 음수값을 저장하는 것입니다.

+---------------+------------+------+-----+---------+----------------+
| Field         | Type       | Null | Key | Default | Extra          |
+---------------+------------+------+-----+---------+----------------+
| solution_id   | int(11)    | NO   | PRI | NULL    | auto_increment |
| problem_id    | int(11)    | NO   | MUL | 0       |                |
| result        | tinyint(4) | NO   | MUL | 0       |                |
| solution_desc | int(11)    | NO   | MUL | 0       |                |
+---------------+------------+------+-----+---------+----------------+

이제 쿼리를 변경해야 합니다.

현재 페이지 및 다음 페이지의 top (21번째 채점 번호, 없으면 다음 페이지 없음)

SELECT * FROM `solution` WHERE `solution_desc` >= -7951654 ORDER BY `solution_desc` ASC LIMIT 21

이전 페이지의 top (마지막 채점 번호)

SELECT * FROM `solution` WHERE `solution_id` > 7951654 ORDER BY `solution_id` ASC LIMIT 20

두 쿼리 모두 ASC를 사용하기 때문에, 속도가 빠를 것으로 예상됩니다.

이제, 각 쿼리가 걸리는 시간을 재봅시다.

• top = 3456453
  • 현재 페이지 및 다음 페이지: 7.23초 → 0.12초
  • 이전 페이지: 0.21초
• top = 2133432
  • 현재 페이지 및 다음 페이지: 6.01초 → 0.05초
  • 이전 페이지: 0.09초
• top = 7777777
  • 현재 페이지 및 다음 페이지: 0.21초 → 0.05초
  • 이전 페이지: 0.04초

채점 현황의 속도가 매우 빨라졌습니다.

마지막으로 다른 방법이나 더 좋은 방법, 또는 더 개선할 점이 있으면 댓글로 달아주세요.

P.S. 내림차순이 귀찮을 때, 정수에 -1을 곱해서 오름차순으로 사용하는 방법은 알고리즘 문제를 풀 때 자주 사용하는 방법입니다.

대표적으로 C++에서 std::priority_queue는 큰 값이 먼저 나오기 때문에, 최소값부터 나오게 하려면 -1을 곱해서 큐에 넣고, 큐에서 뺀 다음에 -1을 곱해서 사용할 수 있습니다. 물론, 이 방법은 큐에 넣어야하는 정수의 범위가 int범위라면 사용할 수 없습니다. 이유는 -2147483648에 -1을 곱하면 -2147483648이기 때문입니다.