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] 인덱스 정리 및 팁
MySQL 인덱스에 관해 정리를 하였습니다. MySQL을 잘 알아서 정리를 한것이 아니라, 잘 알고 싶어서 정리한 것이라 오류가 있을수도 있습니다. 1. 인덱스란? 인덱스 == 정렬 인덱스는 결국 지정한 컬
jojoldu.tistory.com
불러오는 중입니다...
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
A Finite State Machine Implementation along with an integrated Spring Based Framework - GitHub - statefulj/statefulj: A Finite State Machine Implementation along with an integrated Spring Based Fra...
github.com
statefulj docs
StatefulJ FSM · StatefulJ
StatefulJ FSM The StatefulJ FSM is a lightweight Finite State Machine with support for Deterministic and Non-Determinstic Transitions. Stateful FSM is self-contained with minimal dependencies (just SLF4J for a logging facade). Installation Install Stateful
www.statefulj.io
참고자료
https://www.baeldung.com/java-finite-automata
'TIL' 카테고리의 다른 글
TIL) Airflow Xcom (0) | 2022.02.25 |
---|---|
TIL) EPSILON, 몽고 업데이트시 다른 컬럼 값 참조, 몽고 덤프 (0) | 2022.02.24 |
TIL) Webserver vs WAS, NGNIX vs Apache (0) | 2022.02.22 |
TIL) associate 시리즈 (0) | 2022.02.19 |
TIL) Enum, Memory Commit & OverCommit (0) | 2022.02.17 |