TIL) 인덱스, DFA

1. 인덱스

인덱스란 메모리에  { 특정 컬럼 :  주소 } 를 기록해놓은 목차이다.

이 목차를 조회하면 주소를 통해 데이터의 위치를 빠르게 찾을 수 있다.

=> select 가 빠르다.

 

인덱스는 하나의 테이블에 대해 저장되는 또 하나의 정보라 할 수 있다.

 

인덱스는 B-Tree 방식으로 저장하고 빠르게 조회할 수 있다.

• Root 노드 -> Branch 노드들 -> 리프 노드 의 구조이다.
• { 컬럼 : 주소 } 의 정보는 리프 노드에 저장되어 있다.
• Root 노드, Branch 노드는 리프 노드를 빠르게 찾아가기 위해 적절히 나눠져 있다.

 

이런 목차가 있다면 Select 구문이 빠르다.

반면 Update, Delete, Insert 동작은 느려지게 된다.

데이터가 추가되면, 그 데이터도 인덱스에 추가시켜야 된다. B-Tree 구조의 인덱스에 적절히 데이터를 끼워넣어야 하는데, 구간으로 나눠진 Branch 노드 중 해당하는 노드부터 하위 모든 Branch 노드와 Leaf 노드에 영향을 준다.

그리고, InnoDB 는 디스크에 데이터를 페이지라는 단위로 저장한다. 한 페이지에는 16KB 의 크기만 저장될 수 있다.
따라서 DML 명령어는 이 인덱스 트리의 구조를 페이지 상태에 따라 바꾸는 작업을 해야한다.
이 때문에 인덱스의 갯수가 많아질 수록 DML 문의 속도가 느려진다는 것.

 

[인덱스 구성 팁]

• 인덱스는 3-4개가 적절하다.
  • 인덱스는 메모리에 저장된다고 했다. 과도하게 많은 인덱스는 공간을 많이 차지한다.
  • 과도하게 많은 인덱스는 실행계획을 짤 때 잘못된 인덱스를 선택하게할 수 있다.
  • DML시 성능이 저하된다.
• Cadinality 가 높은 컬럼을 인덱스로 잡는다. (= 주민등록번호는 카티널리티가 높다.)
• 복합 인덱스의 경우 순서에 영향을 받는다.
  • 카티널리티가 높은 컬럼 > 낮은 컬럼 순으로 인덱스를 선언하는게 더 빠르다.
• select 문을 짜고, explain 을 걸어 실행계획을 보면 filter 라는 컬럼에서 인덱스 사용률을 볼 수 있다. 이 수치가 높으면 인덱스를 많이 사용하므로 빠르다고 판단할 수 있다.
  • 복합 인덱스에서 선언된 모든 인덱스를 사용하지 않아도 인덱스를 타긴 한다. (filter 률이 낮긴 하지만)
  • 복합 인덱스 선언중 첫번째 인덱스를 조회 조건에 포함하지 않으면 인덱스를 사용하지 못한다.
  • 복합 인덱스 중 하나를 범위 조회 조건(between, >, <, like ..) 로 사용하면 그 키 다음으로 선언된 키들은 인덱스를 타지 못한다.
• OR 연산은 인덱스를 타긴 하지만 OR 자체가 테이블 Full Scan 을 발생시키기 쉽기에 주의해야 한다.
• 조회조건에서 인덱스에 다른 연산을 하면 인덱스를 타지 못한다.
  • ex) WHERE year * 12 > 500 에서 year 에 인덱스가 있어도 인덱스를 타지 못한다.
  • 반면 WHERE year > 500 / 12 는 인덱스를 탄다.

https://jojoldu.tistory.com/243

[mysql] 인덱스 정리 및 팁

https://beelee.tistory.com/37

불러오는 중입니다...

 

 

 

 

2. DFA

Deterministic Finite Automata : 결정적 유한 상태기계

쉽게 말하면, 다음 상태가 정해져 있는 흐름을 말한다.

 

DFA 를 코드상에서 어떻게 나타낼 것인가?

 

코드상에 필요한 경우가 뭐가 있을까.

• 예를 들면, json 의 경우는 처음에는 { 가 있어야 하고, 다음에는 " 그다음은 문자. 그다음은 " 그다음은 : 이렇게 현재의 상태와 현재의 상태에서 넘어갈 수 있는 정해진 다음 상태가 있다.
• 또는, 상품 결제 로직에서 결제대기 -> 결제중 -> 결제완료 같은 경우 현재 상태와 다음 상태는 정해져 있고, 건너뛰거나 뒤로 이동하는 상태는 없다. (뭐 취소가 없다는 가정 하에 .. )

 

DFA 를 코드로 짜면 크게 세가지 객체가 있다.

• 기계 (Entity) : 상태를 가지는 객체
• 상태
• 전이 규칙

 

예시 코드를 짜보자.

{ "key" : "value" } 형태의 값인가를 체크하는 DFA 이다.

(출처 : https://www.baeldung.com/java-finite-automata)

 

 

[전이 규칙]

먼저 전이 규칙이다.

전이 규칙은 하나의 어디에서 어디로 갈 수 있다를 나타내는 객체이다.

interface Transition {
    fun isPossible(c: CharSequence): Boolean
    fun nextState(): State
}

• isPossible() : 지금 사용해야 하는 규칙이 이 규칙이 맞는가
• nextState() : 다음 상태를 리턴. isPossible() 즉 이 규칙을 사용하는게 맞다면 불리는 함수.

 

구현체

class MyTransition(
    private val rule: String,
    private val next: State
) : Transition {

    override fun isPossible(c: CharSequence): Boolean =
        this.rule.equals(c.toString(), ignoreCase = true)

    override fun nextState(): State =
        this.next
}

rule 은 전이 규칙을 나타낸다. 

rule = "{" 이라면 { 일 때 사용하는 전이인가를 판단하기 위해 사용하며,

{ 이라면 이 MyTransition 객체를 사용해서 다음 전이 상태인 next 라는 State 객체를 리턴받는다.

 

 

[State]

상태를 나타내는 객체이다.

interface State {
    fun transit(c: CharSequence): State
    fun with(tr: Transition): State
    fun isFinal(): Boolean
}

구현체

class MyState(
    private val transitions: MutableList<Transition>,
    private val isFinal: Boolean = false
) : State {

    constructor(): this(false)
    constructor(isFinal: Boolean) : this(transitions = mutableListOf<Transition>(), isFinal = isFinal)

	// 들어온 문자가 현재 이동가능한 transition 쌍이 있는지 확인 후 다음 상태 반환.
    override fun transit(c: CharSequence): State =
        transitions.filter { it.isPossible(c) }
            .map { it.nextState() }
            .firstOrNull() ?: throw IllegalArgumentException("Input not accepted: $c")

    override fun with(tr: Transition): State {
        this.transitions.add(tr)
        return this
    }

    override fun isFinal(): Boolean {
        return isFinal
    }
}

 

전이 규칙의 리스트를 가지고 있다.

전이 규칙의 리스트를 가지고 있다는 것은 현재 상태와 다음 상태의 쌍을 가지고 있다는 것이다.

Transition 이라는 것은 결국 rule, next 의 쌍이기 때문이다.

 

그리고 유한 상태기계이기 떄문에 마지막임을 나타내는 isFinal 필드가 있다.

 

• transit() : 현재 상태의 정해진 다음 상태를 반환한다.
• with() : 상태의 규칙(Transition) 을 셋팅한다.
• isFinal() : 마지막 상태 여부를 반환한다.

 

 

[FiniteStateMachine]

interface FiniteStateMachine {
    fun switchState(c: CharSequence): FiniteStateMachine
    fun canStop(): Boolean
}

class MyFiniteStateMachine(
    private val current: State
) : FiniteStateMachine {

    override fun switchState(c: CharSequence): FiniteStateMachine =
        MyFiniteStateMachine(this.current.transit(c))

    override fun canStop(): Boolean =
        this.current.isFinal()
}

상태를 가지는 기계 객체이다.

• switchState() : 기계의 상태를 변경
• canStop() : 기계의 현재 상태가 isFinal 인지 확인한다.

 

 

 

 

 

이제 문자열을 받는 머신을 만들어 보자.

private fun buildJsonStateMachine(): FiniteStateMachine {
    val first: State = MyState()
    val second: State = MyState()
    var third: State = MyState()
    val fouMyh: State = MyState()
    val fifth: State = MyState()
    var sixth: State = MyState()
    val seventh: State = MyState()
    val eighth: State = MyState(true)
    first.with(MyTransition("{", second))
    second.with(MyTransition("\"", third))

    // 키-벨류가 들어가는 자리에서 문자가 들어오면 다음 상태도 a-z 문자인 third, sixth 이다.
    // 세번째, 여섯번째 상태는 현재 상태가 a-z 문자라면 다음 상태도 그대로 남아있게 한다.
    // 반대로 말하면, 현재 상태가 a-z 문자인 상태라면, 다음 상태도 a-z 문자일 수 밖에 없다.
    for (i in 0..25) {
        if (i < 10) {
            third = third.with(MyTransition(i.toChar().toString(), third))
            sixth = sixth.with(MyTransition(i.toChar().toString(), sixth))
        }
        third = third.with(MyTransition(('a'.toInt() + i).toChar().toString(), third))
        sixth = sixth.with(MyTransition(('a'.toInt() + i).toChar().toString(), sixth))
    }
    
    // 반면 세번째가 a-z 문자가 아니라 " 은 다음 상태는 fouMyh 밖에 없다.
    third.with(MyTransition("\"", fouMyh))
    fouMyh.with(MyTransition(":", fifth))
    fifth.with(MyTransition("\"", sixth))
    // 여섯째가 a-z 문자가 아니라 " 은 다음 상태는 fouMyh 밖에 없다.
    sixth.with(MyTransition("\"", seventh))
    
    // 일곱번째가 , 라면 다음 키-벨류 쌍을 받는 second 상태가 다음 상태.
    seventh.with(MyTransition(",", second))
    // } 라면 끝을 나타내는 마지막상태임을 나타내는 eighth 로 간다.
    seventh.with(MyTransition("}", eighth))
    return MyFiniteStateMachine(first)
}

// 추가적으로, 세번째 여섯번째에는 a-z, " 이외에는 예외가 발생한다.
// 이는 문자열이 정의된 유한 상태기계이외에는 전이할 수 없음을 의미한다.

 

 

 

 

테스트다.

    val json = "{\"kkey\":\"value\"}"
    var machine: FiniteStateMachine = buildJsonStateMachine()
    for (element in json) {
        machine = machine.switchState(element.toString())
    }

    println(machine.canStop())

위 코드는 true 를 반환한다. 상태기계의 처음부터 끝까지 결정된 상태로 움직였다.

 

반면 아래는 예외를 발생시킨다.

    val json = "{kkey\":\"value\"}"
    var machine: FiniteStateMachine = buildJsonStateMachine()
    for (element in json) {
        machine = machine.switchState(element.toString())
    }

    println(machine.canStop())

첫번째 { 의 다음 상태는 " 인 Transition 밖에 없어서 기계가 " 상태로 전이했더니,

두번째 문자열은 " 가 아닌 k 가 들어왔다.

k 에 대한 다음 전이를 두번째 전이에서 찾을 수 없어서 예외가 발생한다.

 

결국 이는 처음과 끝까지 결정된 상태를 어기는 것에 validation 처리가 되었다고 할 수 있다.

 

 

 

간단한 DFA 는 위와 같이 짜거나 여러가지 방법이 있겠지만,

복잡한 일을 해야 한다면 라이브러리를 사용하는 방법도 있다.

 

엔티티의 상태를 제한하기에 좋은 라이브러리로 statefulJ 라는 것이 있다.

 

statefulj github

https://github.com/statefulj/statefulj

GitHub - statefulj/statefulj: A Finite State Machine Implementation along with an integrated Spring Based Framework

 

statefulj docs

http://www.statefulj.io/fsm/

StatefulJ FSM · StatefulJ

 

 

 

 

 

참고자료

https://www.baeldung.com/java-finite-automata