토큰 파서가 SQL을 MySQL이 이해 가능한 최소 단위로 잘라내고, 문법 유효성을 검증한다.
전처리기가 컬럼명, 테이블명 등이 존재하는지 확인하고, 접근 권한이 있는지 검증한다.
<aside> 💡
(3-4) 과정은 SQL 파싱(Parsing)이라고 한다.
MySQL Server의 ‘SQL 파서’ 모듈로 처리한다.
해당 단계에서 SQL 파스 트리가 만들어진다.
MySQL Server가 실제로 쿼리를 실행할 때는 SQL 문장이 아니라 SQL 파스 트리를 사용해서 쿼리를 실행한다. </aside>
5. 옵티마이저가 사용자가 전달한 SQL문을 어떻게 실행해야 효율적일지 결정한다. (최적화 및 실행 계획 수립 단계)
<aside> 💡
*옵티마이저(Optimizer)란?
:쿼리를 최적으로 실행하기 위해 각 테이블의 데이터가 어떤 분포로 저장돼 있는지를 참조하고, 데이터를 기반으로 최적의 실행 계획을 수립해주는 것. DBMS의 두뇌
[상세]
파스트리를 참조해서 다음의 내용을 처리한다.
불필요한 조건 제거 및 복잡한 연산 단순화
여러 테이블의 조인이 있는 경우, 어떤 순서로 테이블을 읽을지 결정
각 테이블에 사용된 조건과 인덱스 통계 정보를 이용해 사용할 인덱스를 결정
가져온 레코드들을 임시 테이블에 넣고 다시 한번 가공해야 하는지 결정
등등
[옵티마이저가 실행 계획을 수립하는 2가지 방법]
규칙기반 최적화 방법: 옵티마이저에 내장된 우선순위에 따라서 실행 계획을 수립하는 방법이다.
비용 기반 최적화: SQL을 처리하는 다양한 방법을 마련해두고, 각 방법의 비용과 테이블 통계 정보를 토대로 실행 계획을 수립하는 방법이다. </aside>
6. 수립된 계획대로 스토리지 엔진에서 레코드를 읽어오도록 요청하고, MySQL 엔진에서는 스토리지 엔진으로 받은 레코드를 조인하거나 정렬하는 작업을 수행한다.MySQL 엔진
클라이언트 접속과 SQL 요청을 처리한다. 이는 쿼리 파서, 전처리기, 옵티마이저, 실행 엔진 등으로 이루어져 있다. 여기서 중요한 옵티마이저는 요청 SQL문을 최적화해서 실행시키기 위해 실행 계획을 짠다.
MySQL스토리지 엔진
데이터를 실제로 디스크에 저장하거나, 디스크에 저장된 데이터를 가져오는 역할을 한다. 즉 MySQL 엔진의 옵티마이저가 짠 SQL 실행 계획에 따라 스토리지 엔진을 적절히 호출해서 쿼리를 실행한다. 여기서 스토리지 엔진을 호출할 때 사용하는 것을 Handler API라고 하고, 실제로 이 Handler API를 구현해서 플러그인으로 스토리지 엔진을 커스텀하고 추가할 수 있다. </aside>
7. 결과를 반환한다.
8. 백그라운드 스레드에서 커밋되었으나 디스크에 반영되지 않은 내용을 디스크에 접근하여 일괄 처리한다.
MySql 파싱의 목적이 뭔가요?
→ 클라이언트로부터 전달된 SQL문을 기계가 이해할 수 있는 내부 구조로 변환하고, 그 과정에서 문법적 의미적 오류를 가려내기 위함
alter table 테이블이름 add 필드이름 필드 타입; alter table 테이블이름 drop 필드이름; alter table 테이블이름 modify column 필드이름 필드타입;
DROP: 데이터베이스와 테이블 삭제. 데이터 및 테이블 전체를 삭제함
drop database 데이터베이스이름; drop table 테이블이름;
TRUNCATE: 데이터베이스와 테이블 삭제. 생성 초기 상태 처럼 컬럼값만 남김
truncate database 데이터베이스이름; truncate table 테이블이름;
🍑 DCL; Data Control Language
: 데이터의 사용 권한 관리
GRANT: 사용자 또는 ROLE에 대해 권한을 부여할 수 있음
grant [객체권한명] (컬럼) on [객체명] to { 유저명 | 롤명 | public } [with grant option]; //ex) grant select, insert on mp to scott with grant option;
REVOKE: 사용자 또는 ROLE에 부여한 권한을 회수할 수 있음
revoke {권한명 [, 권한명...] all} on [객체명] from { 유저명 [, 유저명...] | 롤명 | public } [cascade constraints]; //ex) revoke select, insert on emp from scott [cascade constraints];
DML이 뭔가요?
🌽 DML; Data Manipulation Language
: 테이블에 데이터를 검색, 삽입, 수정, 삭제하는데 사용함
INSERT: 테이블에 새로운 row를 추가할 수 있음
insert into 테이블이름(필드이름1, 필드이름2, ...) values(데이터값1, 데이터값2, ...); insert into 테이블이름 values(데이터값1, 데이터값2, ...);
SELECT: 테이블의 row를 선택할 수 있음
UPDATE: 테이블의 row의 내용을 수정할 수 있음
update 테이블이름 set 필드이름1=데이터값1, 필드이름2=데이터값2, ... where 필드이름=데이터값;
DELETE: 테이블의 row를 삭제할 수 있음
delete from 테이블이름 where 필드이름=데이터값;
DML과 DDL의 차이는 뭔가요?
→DDL은 테이블을 관리하는 명령어
→DML은 테이블의 데이터를 관리하는 명령어
Join이 뭔가요?
두 테이블을 하나로 합치기 위해 데이터베이스가 제공하는 기능
JOIN은 ON키워드를 통해 기준이 되는 컬럼을 선택해 2개의 테이블을 합쳐줌
JOIN을 할 때는, 적어도 하나의 컬럼을 서로 공유하고 있어야함
테이블에 외래 키가 설정돼 있으면 해당 컬럼을 통해 JOIN가능
❗ 다만 JOIN을 하기위해 외래키를 설정하는게 항상 좋은 선택이 아닐 수 있음
외래키 설정시, 데이터 무결성을 확인하는 추가 연산이 발생함
무결성을 지켜야 하기 때문에, 상황에 따라 개발하는데 불편할 수 도 있음
⇒ 항상 테이블에 모든 제약조건을 걸어야 하는건 아니고, 프로젝트 상황에 따라 효율적인 제약조건 적용필요
-코어가 여러개인 시스템의 경우, 각 코어가 서로 다른 프로세스를 동시에 독립적으로 실행시킴
-코어가 하나인 시스템에서도, 운영체제가 프로세스 간 컨텍스트 스위칭을 매우 빠르게 수행함으로써 여러 프로세스가 동시에 실행되는 것처럼 동작시킴
멀티 프로세싱의 한계
하나의 프로세스는 동시에 여러 작업을 수행하지 못한다. → 여러 프로세스를 생성해 문제를 해결할 수 있으나, 프로세스가 많아지면 관리나 자원 소모 측면에서 여러 단점이 발생함
프로세스 간 컨텍스트 스위칭이 무겁다. → 컨텍스트 스위칭 작업은 무겁고 비용이 큼 → 프로세스에서 다른 프로세스로 전환할 때 CPU에서 컨텍스트 스위칭이 발생함.
프로세스 간 데이터 공유가 어렵다. = IPC를 사용해야함 → 데이터 공유는 언제 필요한건가? ex1) 웹 서버 구조, 프론트 요청을 처리하는 프로세스와 DB에 직접 접근하여 결과를 가공하는 백엔드 프로세스 간 데이터를 공유해야 하는 상황 ex2) 멀티프로세싱 워커(pool), 대용량 데이터를 병렬 처리하기 위해 여러 워커 프로세스를 띄워놓고, 각 워커가 처리한 결과를 모아 최종 결과를 만들어야 하는 상황 → 각 프로세스는 독립적인 (가상) 메모리 공간을 사용하기 때문에, 서로 다른 프로세스 간 데이터 공유가 까다로움
왜 까다로운가? : 운영 체제는 한 프로세스가 비정상 종료되거나 엉뚱한 메모리에 접근을 해도 다른 프로세스의 메모리에 직접적인 피해를 주지 않아야함. 때문에 각 프로세스는 독립적인 메모리 공간을 사용하고, “다른 프로세스 메모리를 막 읽거나 쓰는 행위”를 금지함.
그렇다면 프로세스 간 데이터 공유는 어떻게? : 반드시 운영체제가 제공하는 별도의 통로 IPC를 거쳐야함. IPC(Inter-Process Communication)
위와 같은 문제를 해결하기 위해 등장한 것 ⇒ 스레드 (Thread)
스레드(Thread): 한 프로세스 내에서 여러 작업을 동시에 실행하게 해줌
하나의 프로세스 내에 여러 스레드를 보유할 수 있다. ⇒ 멀티 스레딩
각 스레드 당 작업 하나가 할당된다.
요즘 CPU의 실행 단위는 스레드 단위이다.
과거에는 프로세스 단위가 CPU의 실행 단위였다.
컨텍스트 스위칭이 가볍다.
스레드는 같은 프로세스 내에서 메모리 영역(Heap)을 공유함.
따라서 프로세스 간 스위칭 보다 훨씬 가볍다.
다만 모든걸 공유하는건 아님
각 쓰레드는 Stack, 포인터, 프로그램 카운터 등을 고유하게 가지면서 자신의 실행 상태를 유지한다.
from collections import deque
import copy
def solution(name):
answer = float("inf")
name = list(name)
origin=['A']*len(name)
now = 0
controll=0
controll+=min(ord(name[now])-ord('A'), ord('Z')-ord(name[now])+1)#min(ord(name[now])-65, 90-ord(name[now])+1)
origin[now]=name[now]
q=deque([])
q.append((now, controll, origin))
while q:
now, controll, origin =q.popleft()
if origin == name:
answer=min(answer, controll)
continue
check=0
rcontroll = controll
rnow=now
while check<1:
# 오른쪽으로 가는 경우,
rnow=rnow+1
if rnow>=len(name):
rnow=0
# 값을 바꿀 필요가 있는 경우
if origin[rnow]!=name[rnow]:
if 0<=rnow<len(name):
check=1
rcontroll+=min(ord(name[rnow])-65, 90-ord(name[rnow])+1)+1
break
#q.append((nnow, controll+1, origin))
# 값을 바꿀 필요가 없는 경우
else:
rcontroll+=1
check = 0
lcontroll = controll
lnow=now
while check<1:
# 왼쪽으로 가는 경우,
lnow = lnow -1
if lnow<0:
lnow=len(name)-1
# 값을 바꿀 필요가 있는 경우
if origin[lnow]!=name[lnow]:
if 0<=lnow<len(name) :
check = 1
lcontroll+=min(ord(name[lnow])-65, 90-ord(name[lnow])+1)+1
break
else:
lcontroll+=1
originl=origin[:]
originr=origin[:]
originl[lnow]=name[lnow]
q.append((lnow, lcontroll, originl))
originr[rnow]=name[rnow]
q.append((rnow, rcontroll, originr))
return answer
일단 이 문제는 그리디 문제이긴 한데, 그리디 하지 않다.
from collections import deque
import copy
def solution(name):
answer = float("inf")
name = list(name)
origin=['A']*len(name)
now = 0
controll=0
controll+=min(ord(name[now])-65, 90-ord(name[now])+1)
origin[now]=name[now]
q=deque([])
q.append((now, controll, origin))
while q:
# print('!', now, controll, origin)
now, controll, origin =q.popleft()
if origin == name:
answer=min(answer, controll)
#print('answer', answer)
continue
check=0
rcontroll = controll
rnow=now
while check<1:
# 오른쪽으로 가는 경우,
rnow=rnow+1
if rnow>=len(name):
rnow=0
# 값을 바꿀 필요가 있는 경우
if origin[rnow]!=name[rnow]:
if 0<=rnow<len(name):
check=1
# print('now controll', controll, 'plus', min(ord(name[nnow])-65, 90-ord(name[nnow])))
rcontroll+=min(ord(name[rnow])-65, 90-ord(name[rnow])+1)+1
#origin[rnow]=name[rnow]
break
#q.append((nnow, controll+1, origin))
# 값을 바꿀 필요가 없는 경우
else:
rcontroll+=1
check = 0
lcontroll = controll
lnow=now
# print('lnow1',lnow)
while check<1:
# 왼쪽으로 가는 경우,
lnow = lnow -1
if lnow<0:
lnow=len(name)-1
# 값을 바꿀 필요가 있는 경우
if origin[lnow]!=name[lnow]:
if 0<=lnow<len(name) :
check = 1
# print('now controll', controll, 'plus', min(ord(name[nnow])-65, 90-ord(name[nnow])))
lcontroll+=min(ord(name[lnow])-65, 90-ord(name[lnow])+1)+1
#origin[lnow]=name[lnow]
break
#q.append((nnow, controll+1, origin))
else:
lcontroll+=1
# print('lnow2',lnow)
#print('lcontroll, rcontroll:', lcontroll-controll, rcontroll-controll, ',', lcontroll, rcontroll,'controll', controll)
if lcontroll<rcontroll:
#print('hi', origin)
origin[lnow]=name[lnow]
#print('hi2', origin, 'lcontroll',lcontroll)
q.append((lnow, lcontroll, copy.deepcopy(origin)))
elif lcontroll>rcontroll:
#print('hi', origin)
origin[rnow]=name[rnow]
#print('hi2', origin, 'lcontroll',lcontroll)
q.append((rnow, rcontroll, copy.deepcopy(origin)))
else:
originl=copy.deepcopy(origin)
originr=copy.deepcopy(origin)
originl[lnow]=name[lnow]
q.append((lnow, lcontroll, copy.deepcopy(originl)))
originr[rnow]=name[rnow]
q.append((rnow, rcontroll, copy.deepcopy(originr)))
# print(controll)
return answer
이렇게 작성한 코드에서
이런식으로 도저히 넘어가질 않았음.
그런데 내가 하루종일 찾은 테스트케이스는 모두 통과되는 상태임.
이건 진짜 근본적인 문제가 하나 있다 싶었다.
내가 이 문제를 풀기위해 사용한 핵심 로직은
"지금 당장 더 싼 쪽(왼쪽 vs. 오른쪽)만 골라서 다른 쪽은 아예 버린다" (만약 두쪽 다 값이 같으면 둘다 살려줌)
이였고, 오히려 그리디한 그리디 분기(pruning) 로직임.
그런데 이게 문제를 해결할 수 없는 결정적인 오류였음.
이렇게 하면, 현재 상황에서 비용이 더 큰 쪽 경로를 전혀 탐색하지 않는데, 이 경우에서 만약 나중에 더 긴 A 구간이 나와버리면, “한 번에 건너뛰어서” 전체 이동 횟수를 줄여 줄 수도 있는 상황을 전부 잘라 버림.
결과적으로, 단편적인 부분에서 싸 보인다고 더 비싼 쪽 경로를 잘라 버리는 순간, 전역 최적해를 놓치게 되는거임;
현실 세계에서 병목은 병의 목 부분이 좁아 액체가 병에서 천천히 나오는 것을 비유한 것이다. 병의 몸통은 넓어 많은 양의 액체를 담을 수 있지만, 목이 좁아져 한 번에 흐를 수 있는 양이 제한되는 것처럼 컴퓨터 시스템에서도 병목현상이 발생하면 처리 능력이 낮아지고 제한된다.
컴퓨터 시스템에서 병목현상은 시스템의 처리 속도를 제한하거나 성능 저하를 유발하는가장 느린 부분을 뜻한다.
이 현상은 시스템의 여러 구성 요소 중 특정 부분이 다른 부분에 비해 처리 속도가 느려 전체 시스템의 성능에 부정적인 영향을 미칠 때 발생한다.
병목현상의 예시
현실세계에서의 병목 현상
고속도로에서 모든 차선이 잘 흐르다가 톨게이트에서 줄을 서서 기다리는 상황에서 줄이 늘어나는 톨게이트가 병목임.
서버에서의 병목현상:
DB 부하:서버 요청이 많아져 DB 조회나 쓰기 작업이 느려지면, 전체 시스템 속도가 느려짐.
API 지연:하나의 API가 처리 속도가 느리면, 다른 API 요청들도 대기하게 되어 응답 시간이 길어짐.
네트워크에서의 병목현상:
데이터가 네트워크를 통해 전달될 때, 특정 라우터나 네트워크 장치의 처리 용량이 한계에 도달하면 병목이 발생함.
개발 프로세스에서의 병목현상:
팀의 특정 작업이 완료되지 않아 다른 작업들이 지연되는 상황.
예시: 백엔드 API 개발이 늦어져 프론트엔드 개발이 멈춰 있는 경우.
병목현상의 원인
하드웨어 문제:
CPU, 메모리, 디스크, 네트워크 등 자원의 제한
예: DB 서버의 CPU가 과부하 상태일 경우
소프트웨어 문제:
비효율적인 코드, 잘못된 알고리즘, 동시성 문제 등
예: 불필요한 중복 요청이나 반복 계산
설계 문제:
시스템 설계 단계에서 특정 구성 요소에 부하가 몰리도록 설계된 경우
예시: 모든 요청이 한 곳으로 집중되는 단일 장애점(Single Point of Failure)
병목현상을 해결하는 방법
분석 및 모니터링:
성능 테스트 도구(JMeter, Locust)를 사용하여 병목 구간을 찾아냄
서버 로깅, APM(Application Performance Monitoring) 도구를 활용함
heapq는 heapq연산을 수행하고 나서 자체적으로 정렬을 할 때, 남은 리스트 전체를 정렬하는 것이 아니라, 필요한 최소한의 연산만 한다.
결과적으로 해당 heapq에서 최소값만을 맨 앞에 놓는다.
이런식으로 heapq는 항상 첫 번째 값이 최소값이 되도록 관리한다. 해당 과정은이진 트리의 형태를 유지하면서, 최소한의 요소 이동만으로 이루어지기 때문에 효율적이다.
이것이 최소힙의 구조이다.
heapq 사용예시:
import heapq
n, m = map(int, input().split())
tmp = list(map(int, input().split()))
heapq.heapify(tmp)
for i in range(m):
# 최소값 두 개 꺼내기
smallest1 = heapq.heappop(tmp)
smallest2 = heapq.heappop(tmp)
# 두 값을 합친 후 다시 삽입
summ = smallest1 + smallest2
heapq.heappush(tmp, summ)
heapq.heappush(tmp, summ)
print(sum(tmp))