쿼리문을 부정으로 표현하면 왜 인덱스를 활용하지 못하는 걸까?

 

 

 

 

우리가 쿼리문을 날릴 때 부정문을 긍정문으로 바꿔서 쿼리문을 작성해야 인덱스를 활용할 수 있어서 더욱 효율적으로 탐색할 수 있다고 한다. 왜 그런걸까? 쿼리문을 긍정문으로 작성했을 때와 부정문으로 작성했을 때의 차이점은 무엇이길래 인덱스를 활용하거나 활용하지 못하는 것일까? 일단, 우리는 2가지 개념을 짚고 가야한다. 바로 탐색방법과 인덱스이다.

1. 탐색방법

탐색에는 2가지 방법이 있다. 

 

바로 순차탐색과 이진탐색이 있다. 순차탐색은 처음부터 끝까지 순서대로 확인하는 것이다.

다음으로는 이진탐색이 있다. 이진탐색은 찾고자하는 값과 현재 위치의 값을 비교하여 탐색하는 범위를 좁혀나가는 효율적인 탐색방식이다.

간단하게 말하자면 찾고자하는 값과 현재 값을 비교하여 필요한 범위의 영역만 탐색하는 방식이다.

밑에는 자바로 순차탐색과 이진탐색의 테스트 코드를 작성했다.

 

@DisplayName("탐색 방식에 대해 공부하는 테스트 클래스")
public class StudyForSearch {
    int[] arr = new int[10];
    int target = -1;

    @BeforeEach
    void setUp() {
        // fill elements in array
        for (int i=0; i<10; i++) {
            arr[i] = (i+1);
        }

        // shuffle the array
        for (int i=0; i<100; i++) {
            int randomIndex = (int)(Math.random()*10);
            int tmp = arr[0];
            arr[0] = arr[randomIndex];
            arr[randomIndex] = tmp;
        }

    }


    @DisplayName("순차탐색 방식")
    @ParameterizedTest(name = "{index}. {displayName} (찾고자하는 값의 인덱스는 {0}입니다.")
    @ValueSource(ints = {0, 2, 6, 7, 8})
    void linearSearchTest(int targetIndex) {
        target = arr[targetIndex];

        boolean ok = false;
        // linear search, O(n)
        for (int i=0; i<arr.length; i++) {
            if (arr[i] == target) {
                ok = true;
                break;
            }
        }

        // if i found the target, it's true otherwise false;
        assertTrue(ok);
    }

    @DisplayName("이진탐색 방식")
    @ParameterizedTest(name = "{index}. {displayName} (찾고자하는 값의 인덱스는 {0}입니다.")
    @ValueSource(ints = {0, 2, 6, 7, 8})
    void binarySearchTest(int targetIndex) {
        target = arr[targetIndex];
        // before using binary search, sorting the array
        Arrays.sort(arr);

        boolean ok = false;

        // binary search, O(logN)
        int left = 0, right = arr.length-1;
        while (left < right) {
            int mid = (left + right)/2;
            // if i found target
            if (arr[mid] == target) {
                ok = true;
                break;
            }
            // if the element which is on mid is greater than the target, search only the left part
            else if (arr[mid] > target) {
                right = mid-1;
            }
            // if the element which is on mid is smaller than the target, search only the right part
            else {
                left = mid+1;
            }
        }

        // if i found the target, it's true otherwise false
        assertTrue(ok);
    }

}

 

 

 

순차탐색의 경우 시간복잡도는 O(N)이고 이진탐색의 경우 시간복잡도는 O(logN)이다.

 

2. 인덱스

두번째로는 인덱스이다. 오라클에서 인덱스는 B * tree로 구현되어있다.B * tree는 balanced binary search tree(bst)이다.

https://its-all-about-oracle.blogspot.com/2015/03/types-of-b-tree-indexes-in-oracle.html

Types of B-Tree Indexes In Oracle

 

B * tree는 이진트리의 일종이다. 이진트리의 장점은 정렬하기 쉽고 효율적인 탐색을 할 수 있다.

왜냐하면 이진트리의 저장 형식에 따라 값이 이미 정렬된 형태로 저장되어 있다.더욱 상세히 얘기하면 현재 위치의 노드값에서 자신보다 작은 값은 왼쪽 서브트리에 저장되고 큰 값은 오른쪽 서브트리에 저장된다. 그래서 이진탐색을 통해 효율적인 탐색을 할 수 있어서 탐색에 유리한 자료구조이다.

 

결국에는 우리가 쿼리를 날릴 때 SQL 옵티마이저에 의해 효율적인 탐색 경로가 결정되는데, 이때 인덱스를 이용하는 경우

내부적으로 이진 탐색을 하여 효율적으로 탐색할 수 있는 것이다.

 

3. 결론 

그러면, 쿼리문을 부정문으로 작성했을 때 왜 인덱스를 활용하지 못하는 것일까? 그 이유는 바로 불명확한 탐색 대상이기 때문이다.

우리가 이진탐색을 할 때는 데이터가 정렬이 되어 있어야하고 탐색 대상이 존재해야한다. 하지만 부정으로 쿼리문을 날리면 탐색 대상이 불명확하여 이진탐색을 할 수 없어서 순차탐색을 하여 인덱스를 활용하지 못하는 문제가 발생한다. 따라서 이러한 문제를 해결하기 위해 부정문을 긍정문으로 바꾸어서 명확한 탐색 대상을 알려주고 NOT EXSITS()를 활용하여 원래 찾고자 하는 결과를 가져오면된다.

 

예를 들어서, 사원 테이블이 있고 거기서 직책이 사원이 아닌 직책을 가져오려면 크게 2가지 쿼리를 작성할 수 있다.

하지만 성능을 고려한다면 2번째 쿼리문처럼 부정을 긍정으로 바꾸고 NOT EXISTS를 활용하는 것이 좋다

-- 1. 부정문으로 작성
select id, title, name from s_emp where title <> '사원';

-- 2. 부정을 긍정문으로 작성
select e.id, e.title, e.name from s_emp e where not exists(select 'x' from s_emp where e.title = '사원');

 

결론적으로, 부정문으로 쿼리문을 날릴경우 찾고자하는 대상이 명확하지 않아서 인덱스를 활용하지 못하고 순차탐색을 하기 때문에

긍정문으로 명확한 대상을 탐색하게끔 만들어주고 NOT EXSITS를 통해서 원래 찾고자하는 결과를 가져온다.