Jins' Dev Inside

LIS는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다.

개인적으로 매력있게 느끼는점은 인간이 직관적으로 쉽게 찾을 수 있는 법을 논리적으로 찾기가 쉽지 않으며, 그를 위한 수학적 방법들에 있었다.

LIS 알고리즘은 주어진 수열 내에서 가장 긴 부분 수열을 찾아내는 알고리즘이다. 

가령 다음과 같은 수열이 주어져있을 때를 생각해보자.

위와 같이 주어진 수열에서, LIS 는 10, 20, 50, 90 또는 10, 20, 40, 60 등으로 구해낼 수 있으며 가장 긴 증가하는 부분 수열의 길이는 4라는 걸 직관적으로 구할 수 있다.

하지만, 알고리즘으로 옮기려고 한다면 이 직관을 표현하는 건 쉽지 않다. 

또한 우리는 구현에 있어서 매 Index에 대해 다른 전체 Index를 검색해야하는 어마어마한 시간 복잡도에 마주하게 된다.

이는 최적화 알고리즘 기법의 한종류인 Dynamic Programming 을 이용해도 마찬가지인데, DP로 구현할 시 알고리즘은 다음과 같다.

위의 알고리즘의 경우에도 역시 시간 복잡도는 O(N^2) 이 되고, N이 커질수록 부담스러운 알고리즘이 된다.

만약 N이 10000이 넘어간다면? 그때는 눈으로 보일만큼 성능에 영향을 주는 모듈이 되게 된다.

최장 부분 수열의 길이를 구하는 데 있어서 최적의 방법은 일반적으로 O(N logN) 알고리즘으로 알려져있고, Trace 배열을 정의해서 같은 시간복잡도에 최장 부분 수열까지도 알아낼 수 있다.

공부할 당시 최장 부분 수열의 길이를 구하는 부분은 간단했으나, 최장 부분 수열 자체를 O(N logN) 시간 안에 구하는게 쉽지 않았던 기억이 있어 정리해보았다.

최적화의 핵심은 Binary Search 이고, lis 라는 별도의 배열에 내용을 담는다. 과정은 다음과 같다.

먼저, 배열의 각 요소를 순회한다. 이때, 배열의 각 요소를 lis 배열에 담는데, lis 배열에는 작은 순서대로만 들어가야한다.

그를 위해서는, lis 배열의 가장 마지막 요소(우리는 lis 배열을 증가하는 순서로 담았기 때문에 lis 배열의 최댓값이다.)와 배열의 요소를 비교하면 된다.

만약 lis 배열의 최댓값보다 크다면, 해당 요소를 lis 배열의 마지막에 추가시켜주면 된다.

하지만, 다음 요소는 lis 배열의 마지막 요소보다 작다. 이 때 Binary Search 가 필요하다. 우리는 Binary Search 를 통해 

"정렬된" LIS 배열에서 arr 요소가 들어가야할 위치를 찾을 수 있다.

예시에서 이제 LIS 배열은 다음과 같이 변한다.

이런식으로, LIS 배열을 증가하는 부분수열로 만들어 놓으면 쉽게 최장 부분수열의 길이를 O(N logN) 시간복잡도로 구할 수 있다.

하지만, 이런 구현만으로는 어떤 요소가 최장 부분 수열을 구성하는지 알 수 없다. 

가령, 다음과 같이 배열의 마지막 요소가 첫번째 요소보다 작을 경우, 이 구현을 통해 수열 자체를 구하는건 불가능하다.

따라서, lis 배열을 채울때, 어떤 항목이 참조되는지 Reference 배열을 정의하여 요소들을 Tracing 하는 테크닉을 사용한다.

-- LiS 구현(C++) --

Trace 배열을 사용하면 위와 같이 LIS 알고리즘 사용 중 Refenrence를 저장하는 방식으로 최장 부분 수열의 추적도 가능하다.

Trace 배열에 저장된 인덱스를 끝에서부터 가져오면 최장부분순열 자체를 역순으로 구해낼 수 있다.

알고리즘의 시간복잡도는 O(N logN) 으로 DP 구현보다 효율적인 시간복잡도로 작동하게 된다.

이 방법 외에도 Segment Tree 등을 이용해 최적화된 구현이 가능하다.

MySQL은 조회(SELECT) 에 있어서 최고의 강점을 갖는 종류의 DB이지만, 경우에 따라 막대한 양의 Insert 를 수행해야할 때가 있다.

특히 API 에서 조회하는 DB에 배치 서버가 수시로 데이터를 갱신해주는 경우나, 막대한 양의 메시지 데이터를 처리하게 될 경우가 있는데, DB가 커질 수록, 단순 쿼리로만 작업하다가는 퍼포먼스에 있어 엄청난 디버프를 받게 된다.

대량의 데이터를 삽입하는 것을 Bulk Inserting 이라 하며, 이를 위한 다음과 같은 튜닝 기술들 정도는 숙지해두도록 하자.

(1) 여러 개의 Insert 구문 수행시 Values 리스트를 다중으로 사용하는 것이 성능을 향상시킬 수 있다. 

정말 효과 제대로 본 방법인데, 다수의 동일한 Insert query에 대해서 다음과 같이 최적화가 가능하다.

Insert into T values(a, b, c)

Insert into T values(d, e, f)

위와 같이 쿼리를 날린다고 할때, 이를 다음과 같이 바꾼다.

Insert into T values(a, b, c), (d, e, f) ...

이렇게 되면 성능이 기하급수적으로 향상되며, 이는 JDBC 혹은 클라이언트 등의 연결 설정에서 RewriteBatchedStatements=true 와 같은 속성을 주어 자동으로 최적화시킬 수 있다.

(물론 설정의 경우 실수의 우려도 있고, 개발자가 한눈에 파악하기 쉽지 않기 때문에 협업 시에는 코드 레벨에서 처리하는게 더 좋다.)

또한 이 쿼리 튜닝을 사용할 때에는 비어있지 않은 Table에 Insert 시 my.cnf 파일 내에 있는 bulk_insert_buffer_size를 변경하여 속도 개선이 가능하다. 

(수정 방법은 /etc/mysql/my.cnf 파일을 열어서 [mysqld] 항목 아래에 bulk_insert_buffer_size=256M 과 같이 설정해주면 된다.)

(2) 여러 클라이언트에서 Insert 시 Insert Delayed 를 통해 속도 개선이 가능하다. 이 구문을 이용하면 수행 응답이 큐에 적재되고 테이블이 사용되지 않을 때 삽입한다. 

실시간으로 서비스 중인 경우에 빛을 발하는 성능 향상 법이다.

(3) 파일 스트림으로부터 대량의 데이터를 삽입 시 Load Data Local Infile 구문을 이용해서 필드 구문자로 정리된 File을 MySQL DB로 Redirection 시킬 수 있다. 

각각에 대한 Insert 구문 수행보다 빠른 퍼포먼스를 보인다.

 (ex) Delimeter가 "|" 이고 라인 개행 단위로 레코드가 기록되어 있을 때,

LOAD DATA LOCAL INFILE '경로' [REPLACE | IGNORE] INTO TABLE 테이블명 FIELDS TERMINATED BY '|' LINES TERMINATED BY '\n';

단, 이 경우 5.5 이상 버전에서는 LOCAL을 꼭 붙여야 에러가 나지 않으며, 이를 이용하기 위해 설정 옵션에 [mysql] 아래에 local-infile을, [mysqld] 아래에 local-infile을 추가해주어야 한다.

(4) Index가 많이 사용된 테이블에 대량으로 Insert 시 Index를 비활성화한 후 수행하는 것이 좋다. 

매 Row 마다 계산 후 삽입하는 것보다 전체 키를 비활성화하고 데이터 입력이 종료되고 다시 키를 활성화시키는 것이 빠른 수행을 할 수 있다.

ALTER TABLE 테이블 DISABLE KEYS;

Insert 구문 수행

ALTER TABLE 테이블 ENABLE KEYS;

여기서 Key 란 INDEX 뿐 아니라 FOREIGN KEY 참조도 포함한다. 실제로 Bulk Inserting 이 중요하다면, 체크를 꺼두는 것이 성능 향상에 큰 도움이 된다.

물론 이 경우 단점은, API 로직상 에러가 발생하여 문제가 될 수 있는 데이터가 삽입될 시, 실시간으로 정합성 체크가 불가능하다. 데이터를 신뢰할 경우에만 수행해야 한다.

(5) 트랜잭션을 지원하는 테이블의 경우, Start Transaction과 Commit을, 지원하지 않는 테이블의 경우 테이블 잠금을 실행하면 성능이 향상된다. 

(이유는 버퍼 플러시가 매번 수행되지 않고 작업이 끝난 후 수행되기 때문이다.)

(6) Buffer Size 의 조절을 통해 성능 향상이 가능하다.

테이블에 Insert 시 Index가 정렬되어 들어온다는 보장이 없기 때문에 이는 B트리 구조화시 추가적인 I/O를 수반한다. 

디스크에 데이터를 읽고 쓰고 하는 부가적인 동작이 레코드가 많아질수록, Buffer 크기를 넘어설수록 많이 수반되기 때문이다. 

이를 막기 위해서 InnoDB의 경우 Buffer Size를 크게 잡는다면 이 만큼의 메모리를 추가로 캐싱용 버퍼풀을 위해 사용하는 대신 디스크 I/O의 비용을 높은 비율로 줄일 수 있다. 

잔여 메모리의 50~80% 만큼 조절하는 게 정석이며 그 이상으로 조절 시 오히려 하드디스크를 가상 메모리로 쓰기 위한 스와핑 작업이 발생하기 때문에 성능이 저하된다고 알려져있다. 

(실제로 이부분은 범위 내라면, 조절하는 만큼 성능이 향상된다. 바꾸기 위해서는 my.cnf 설정 내에서 [mysql] 하위 항목으로 innodb_buffer_pool_size=1024M 과 같이 입력하면 된다.)

버퍼 풀 메모리가 충분히 큰 양으로 할당되어 있다면 innodb는 in-memory 데이터베이스처럼 동작한다. 

Access를 위한 select 데이터 뿐 아니라, Insert 및 Update 작업에도 도움이 되는 캐싱을 하기 때문에 적절하 조정하여 사용하는 것이 핵심이다.

버퍼 풀 메모리는 내부적으로 LRU 알고리즘을 사용하는 리스트의 형태로 자세한 내용은 http://dev.mysql.com 레퍼런스를 참조한다.

 EXPLAIN 은 어느정도 수준있는 DB를 다루는 개발자라면 꼭 알아야할 정도로 중요한 MySQL 의 쿼리문이다.

 실제로 많은 데이터베이스 관련 서적들에서도 최적화를 위한 선행 단계로 추천하고 있을 만큼 MySQL 의 강력하고 효과적인 쿼리문이다.

 EXPLAIN 키워드는 MySQL 에게 쿼리문의 실행 계획을 물어보는 키워드이다.

 Explain 구문을 이용해서 SQL Query를 수행하기 전에 데이터를 어떻게 가져올 건지에 대한 시스템의 실행계획을 받아볼 수 있다.

주로 쿼리 퍼포먼스 측정을 위해 Explain 을 많이 사용하지만 매 쿼리를 코드에 삽입할 때 테스트해보는 습관을 들이는 것이 좋다.

 SELECT 구문에서 explain 을 사용하는 방법은 단순히 키워드 앞에 붙여주기만 하면 된다. 단 SELECT 구문이 아닐 경우에는 INSERT, UPDATE, DELETE 등의 구문을 SELECT로 재구성시켜줘야 한다.

(ex) EXPLAIN select * from members

      UPDATE name from members where member_id = ‘1’

       EXPLAIN SELECT name from members (UPDATE 후)

 EXPLAIN 에서 각 칼럼은 다음과 같은 의미를 갖는다.

Select_type – 간단한 쿼리인지 복잡한 쿼리인지를 나타낸다.

Table – 어떤 테이블에 접근하는지를 나타낸다. 복잡한 쿼리문에서도 어떤 테이블에 실질적으로 접근하는지를 알 수 있다.

Type – 조인 방식이자, 테이블에서 해당 레코드를 어떻게 찾아가는지를 나타내며 퍼포먼스 측정에 있어서 중요한 지표이다. 

(ALL-풀스캔, INDEX-유사 풀스캔, RANGE-제한된 인덱스 스캔, REF-부분적인 값에 매칭되는 부분만 검사, EQ_REF-단 하나의 

값만 참조하는 경우, CONST-쿼리 일부를 상수로 대채시켜서 찾음. SYSTEM-무조건 하나의 열만을 갖는 테이블)

Possible Key- 해당 조회문에서 MySQL이 선택한 인덱스를 나타낸다.

Key – MySQL이 실제로 사용할 키를 나타낸다. 

Key len – 인덱스 필드가 가질 수 있는 최대길이

Ref – 키 칼럼의 인덱스를 찾기 위해 선행 테이블의 어떤 칼럼이 사용되었는지

Row – 원하는 행을 찾기 위해 읽어야 하는 예측 Row 카운트

Extra – 각종 조건문이 사용되는지 여부를 나타낸다.

 특히 많은 종류의 웹서비스가 SELECT 에 대한 처리를 주로 하는 경우가 많다.(SELECT 가 주가 아닌 데이터라면 MySQL 을 사용하지 않을것이다.) 

가령 Key 로 잡히지 않은 Column 을 조건으로 SELECT 쿼리를 수행하는 경우, 특히 유저 DB라면, FULL SCAN 이 발생해 막대한 비용이 들게 된다...

 이런 참사를 개발시에 눈치챌 수도 있지만, 본인이 DB 구조를 잘 모르거나 구조가 매우 복잡한 레거시 프로젝트에 투입된 상황이라면, EXPLAIN 의 생활화는 큰 도움이 될 것이다.