접근

바로 이전 게시글에서 풀었던 경로 찾기 문제와 매우 유사하다. 여행 동선을 체크할 때 중간에 여러 도시를 지나가도 되고 동일한 도시를 여러 번 방문해도 된다는 얘기는, 결국 A > B 도시로 이동 가능한 경로가 있는가만 확인하면 된다. 어차피 양방향 그래프이기 때문에 나는 스택에 저장해두고 뒤쪽 도시부터 반대 방향으로 확인했다. 

처음에 75%에서 틀렸다는 결과가 나왔는데, 질문 게시판에서 반례를 찾았다. 여행 계획이 A > A, 즉 같은 도시로 이동할 수도 있는거다. 문제에서 연결 정보를 입력받을 때에는 같은 도시에 대한 정보는 포함되어 있지 않으므로 이 부분이 누락됐던 것 같다. 그래서 if(i == j) graph[i][j] = 1 조건을 추가해주었다. 

 

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] graph = new int[n+1][n+1];
        
        for(int i = 1;i <= n;i++){
            st = new StringTokenizer(br.readLine());
            
            for(int j = 1;j <= n;j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                if(i == j) graph[i][j] = 1;
            }
        }

        // 여행 계획
        st = new StringTokenizer(br.readLine());
        Queue<Integer> q = new LinkedList();
        while(st.hasMoreTokens()){
            int cur = Integer.parseInt(st.nextToken());
            q.add(cur);
        }

        // 플로이드 워셜 알고리즘
        solve(graph, n);

        // 결과 출력
        Boolean possible = true;
        int cur = q.poll();
        while(!q.isEmpty()){
            int next = q.poll();
            
            if(graph[cur][next] == 0){
                possible = false;
                break;
            }
            cur = next;
        }

        String answer = possible ? "YES" : "NO";
        System.out.println(answer);
    }

    static void solve(int[][] graph, int n){
        for(int k = 1;k <= n;k++){
            for(int i = 1;i <= n;i++){
                for(int j = 1;j <= n;j++){
                    if(graph[i][k] == 0 || graph[k][j] == 0) continue;  // 양수 길이 없음
                    graph[i][j] = 1;                    
                }
            }
        }
    }
}

'Algorithm' 카테고리의 다른 글

[백준] 5430: AC JAVA  (0) 2025.05.18
[백준] 1092: 배 JAVA  (0) 2025.03.02
[백준] 11403: 경로 찾기 JAVA  (0) 2025.02.28
[백준] 9084: 동전 JAVA  (0) 2025.02.14
[백준] 12865: 평범한 배낭 JAVA  (0) 2025.02.13

접근

1. 우선 그래프 문제이므로, 어떤 형태로 저장할지를 결정해야 한다. 이중 ArrayList로 할지, 아니면 단순 이차원 배열로 할지. 이는 사용하는 알고리즘과 문제에서 주어지는 N의 범위에 따라 다르다. 우선 N의 범위는 100 이하로 매우 작기 때문에 단순 배열로 저장해도 된다. 

2. 그래프 중에서 어떤 알고리즘으로 풀 것인가? 문제를 읽어보면 모든 노드 → 모든 노드로 가는 경로를 찾아야한다. 즉, 플로이드 워셜 알고리즘이 적절하다. 그렇기 때문에 간선 정보는 더더욱 배열로 저장해야 한다는 소리가 된다. 

 

위와 같이 생각하고 처음에 코드를 짰는데, 테스트 케이스와 결과가 다르게 나왔었다. 알고보니 3중 for문에서 k, i, j 순이 아니라 i, j, k순서로 했었다. 그런 자세한 부분까지 기억하고 있는 것은 아니라서 오히려 잘못된 부분을 찾기가 더 어려웠던 것 같다. 

 

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];
        
        for(int i = 0;i < n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j < n;j++)
                graph[i][j] = Integer.parseInt(st.nextToken());
        }

        // 플로이드 워셜 알고리즘
        solve(graph, n);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                sb.append(graph[i][j]).append(" ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }

    static void solve(int[][] graph, int n){
        for(int k = 0;k < n;k++){
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    if(graph[i][k] == 0 || graph[k][j] == 0) continue;  // 양수 길이 없음
                    graph[i][j] = 1;                    
                }
            }
        }
    }
}

'Algorithm' 카테고리의 다른 글

[백준] 1092: 배 JAVA  (0) 2025.03.02
[백준] 1976: 여행 가자 JAVA  (0) 2025.03.01
[백준] 9084: 동전 JAVA  (0) 2025.02.14
[백준] 12865: 평범한 배낭 JAVA  (0) 2025.02.13
[백준] 13904: 과제 JAVA  (0) 2023.03.20

회사에 다니면서 내가 뭘 했는지 상세히 기록을 안해두면 나중에 다 휘발되는 것 같아서, 소소한 거라도 (오히려 소소한 것일수록 더더욱) 트러블 슈팅이나 새로 알게된 것들은 기록해두기로 했다. 문제를 마주했을 때 내 의식과 행동 순서대로 작성했다. 
 

배경

현재 파이썬에 쿠버네티스를 연결하여 kubernetes client API를 통해 deployment 및 service를 관리하는 서비스를 개발하고 있다. 상사가 제공해준 스켈레톤 코드를 기반으로 기능을 추가해 나가고 있는데, 사실 대부분 클로드가 짜준 코드라고 한다. 아무튼, 이번에는 client가 우리 서비스에 요청을 보내면 그 request body를 기반으로 deployment와 service를 배포하는 API를 개발하고 있었다. 그걸 위해서 요청받은 namespace 및 기타 정보들로 클러스터에 존재 여부를 확인하고, 그에 따라 새로 생성 및 업데이트하는 기능을 개발해야 했다. 새로 생성하는 데에는 아무 문제가 없었는데, 업데이트하는 과정에서 에러가 발생했다.
 

이슈 발생 상황

요청 정보를 기반으로 동일한 deployment 및 service 가 있는 경우  patch_namespaced_deployment() 와  patch_namespaced_service() 함수를 사용해 수정 사항을 반영하도록 했다. 그런데 deployment는 문제없이 잘 실행됐는데, service 부분에서 에러가 발생했다. 에러 발생 시 요청한 request body는 다음과 같다. 즉, name이 http인 port 객체에 대해서 포트 번호만 바꾸고 정상 동작을 확인하려고 했다.

// 처음 service 생성 시 요청 정보
{
    "ports": [
    	{
            "port": 8000,
            "name": "http"
        },
        {
            "port": 8001,
            "name": "https"
        }
    ]
}

// service 업데이트 시 요청 정보
{
	"ports": [
    	{
            "port": 8010,
            "name": "http"
        },
        {
            "port": 8001,
            "name": "https"
        }
    ]
}

 

에러 분석

에러 중 핵심 메세지만 뽑으면 다음과 같다. 
Reason: Unprocessable Entity
HTTP response body: {"message": "test-node" is invalid: spec.ports[1].name: Duplicate value"...}
서비스를 배포하는 YAML의 ports 항목은 리스트로 되어있는데, 그 중 1번 인덱스의 name값이 중복된다는 것이다. 쿠버네티스 공식 문서에 따르면, multi-port 서비스에서 ports의 name 속성은 ambiguous하지 않도록 모두 정의되어야 한다. 이 말은 곧 각 port의 name들은 유니크해야 한다는 뜻이기도 하다. 
나는 단순히 동일한 이름을 가진 객체의 포트 번호만 스위칭한다고 생각했는데, 내부 로직 상 충돌이 나는 것 같다. 그런데 업데이트하고자 한 포트 정보는 첫 번째 데이터인데, 왜 에러 메세지에는 1번 인덱스로 나오는 걸까? 0번 인덱스가 맞지 않을까? 이런 의문점들을 해결하기 위해 우선 해당 API 문서를 찾아보았다. 
 

API document 분석

kubernetes client github 페이지의 README를 보면 각 API에 대한 document 링크가 있다. service를 관리하는 API들을 둘러보니 create, delete, list, patch, read, replace 등이 있었다. 내가 사용했던 patch 함수와, 비슷한 기능을 하는 것으로 보이는 replace 함수를 비교해보기로 했다.

patch_namespaced_service document

replace_namespaced_service document

두 API를 비교해보니, patch는 서비스의 일부분을 업데이트하는 것이고 replace는 전체를 업데이트하는 거였다. 그리고 업데이트할 서비스 정보를 받는 body 부분에서 차이가 있었다. patch의 경우 단순 object고, replace는 V1Service 객체를 받는다. 여기서 object는 간단히 dict로 이해하면 된다. 즉, patch의 경우 변경이 필요한 필드만 포함한 객체를 파라미터로 받아 업데이트하는 것이고, replace는 서비스 객체를 통채로 받아 교체하는 것이다. 기존의 서비스 객체를 완전히 삭제하고 새로 생성하는 방식이라고 이해하면 될 것 같다. 

 

이 내용은 쿠버네티스의 patch 함수에 관한 API 문서에서도 찾아볼 수 있다. (사실 이게 먼전데 patch 기능이 있는 걸 몰랐다)


 

해결 방안

1. client에게 서비스의 정보 전체를 받고 있기 때문에 replace 함수 사용하기(해당 서비스 존재 여부 확인 로직 필요, 이미 있음)
→ 제일 단순하고 간편한 방식
2. 클러스터에 존재하는 service 객체를 클러스터에서 가져오고, 수정 사항이 있는 부분만 비교한 후 patch 함수 사용하기
→ 수정된 부분(변경, 삭제, 추가)을 모두 파악하는 로직을 구현하는 데 많이 복잡해질 것. 특정 필드 일부만 수정된다면 이 방식이 효율적
3. 해당하는 service 객체를 가져오고, 해당 객체에 변경된 값을 수정한 후 replace 함수 사용하기
→ 단순 수정 사항만 반영하려면(기존 필드 값들을 누락하지 않으려면) 이 경우가 적절하겠다. 하지만 내 경우에는 request가 온 그대로 업데이트를 해야하므로 해당하지 않음
 
위와 같은 경우들을 고려해본 결과, 1번 방식이 내 상황에 제일 적절하다고 판단했다. 기존 patch함수룰 replace 함수로 대체했고 이번에는 에러 없이 정상적으로 실행된 것을 확인했다! 

추가 의문점

1. 에러 메세지에서 왜 인덱스가 0번이 아니라 1번으로 출력되었는가?

쿠버네티스에서 patch 작업 수행 시 Strategic Merge Patch 방식으로 동작하기 떄문인 것 같다. 쿠버네티스 공식 문서에서 deployment에 대해서 patch하는 예제를 참고했다. "patch-demo-ctr"라는 container가 존재할 때, " patch-demo-ctr2" container에 대한 정보를 yaml로 작성하고 명령어를 실행한 것이다. 그 결과 기존 container list에 새로 추가된 것을 볼 수 있다. 즉, 내 경우 "http"라는 이름을 가진 새로운 port 정보를 추가하러고 했기 때문에 충돌이 난 것이다. 그러면 리스트 안에는 다음과 같이 2개의 값이 담겼을 것이다. 그렇기 때문에 두번째 값, 즉 1번 인덱스에서 에러가 발생한 것이다.

spec:
  ports:
  - name: http
    port: 8000
    protocol: TCP
    targetPort: 8000
  - name: http
    port: 8010
    protocol: TCP
    targetPort: 8000

 

2. 왜 patch deployment에서는 잘 되고 service에서만 에러가 발생했는가?

앞서, deployment는 문제없이 잘 실행되었다고 했다. 그렇다면 동일한 patch 방식인데 왜 service에서만 에러가 났을까? gpt에게 한번 물어봤다. (정확하지 않은 내용일 수 있으니 참고만 바람) deployment와 service가 내부적으로 다르게 동작하기 때문이라고 한다. 예를 들어 deployment YAML의 containers 속성의 경우, ports와 같은 리스트 형식이지만 name이 같으면 해당 컨테이너 정보가 업데이트 되고 새로운 컨테이너가 추가되지 않는다. 즉, 이름을 기준으로 변경 사항을 확인하여 개별적으로 병합하는 것이다. 반면 service 는 병합되지 못하고 기존 리스트에 추가(append)된다.

 

동일한 patch 기능이고, 동일하게 strategic merge patch 방식을 사용할텐데 왜 내부 로직을 다르게 만든걸까? 이는 쿠버네티스의 리소스 설계 철학과 관련이 있다고 한다. deployment의 경우 하나의 deployment에서 여러 컨테이너가 실행될 수 있으며, 그 중 일부 컨테이너만 업데이트하는 경우가 많다. 변경 사항이 없는 기존 컨테이너를 유지하는 것이 불필요한 삭제 및 재배포가 발생하지 않는다. 반면 service의 ports는 개별적인 업데이트보다 전체적인 일관성이 더 중요하며, 특정 포트가 변경될 때는 보통 기존 포트를 제거하고 새 포트를 설정하는 것이 일반적이다.(병합하여 수정하는 것이 아니라) 만약 ports 리스트가 containers처럼 개별 병합된다면, 잘못된 상태(중복된 포트 설정)으로 남아있을 위험이 있다. 

즉, 각 필드별로 사용 목적에 맞게 가장 적절한 방식이 적용되도록 설계 것이다. 필드 별로 부분 업데이트/전체 변경 중 어떤 것이 더 일반적인지를 고려하고, 그에 맞게 병합 방식을 다르게 적용한 것이라고 한다. 


3. deployment를 업데이트함에 있어 patch와 replace의 정확한 차이는?

patch는 수정 사항이 있는 필드에 대해서만 업데이트하고, replace는 그와 상관없이 전부 업데이트한다. 각 함수별로 케이스를 나눠보면 다음과 같다. 

  • patch
    • container 필드의 name과 기존 컨테이너 이릉이 전부 다르다면, 새로 생성되어 배포됨
    • 이름이 중복되고, 수정된 사항(ex: 이미지)이 있다면, 재배포됨
    • 이름이 중복되었는데 수정된 사항이 없다면, 해당 컨테이너는 그대로 유지됨 (이 케이스는 gpt에게 물어봄)
  • replace
    • 이름의 중복 여부나 수정 사항을 체크하지 않고, 전부 재배포함

 

근본적 원인 및 회고

1. 단순히 주어진 스켈레톤 코드만 활용했기 때문에, 어떤 API들이 제공되는지 모르는 상태로 개발을 진행했다. 
2. 쿠버네티스에 대한 이해도가 부족했다. kubectl을 사용할 때는 apply 명령어로 생성 및 업데이트를 모두 처리했기 때문이다. 그래서 patch/replace 기능이 있는지도 몰랐고, merge patch 방식이란 것도 처음 알게 되었다. 
 
⇒ 앞으로도 새로운 기술을 공부할 때 공식 문서를 적극적으로 참고하고, 최소한 내가 쓰는 함수가 어떤 기능을 하는지는 정확히 알고 사용해야겠다. 문서에서 다양한 API를 비교해보니 내 상황을 정확히 분석해보고, 그에 따른 장단점을 파악하며 적절한 방안을 고민해볼 수 있었다. 

쿼리 실행 계획 조회

테스트 환경 구축

이전까지의 포스팅은 모두 핵심만 정리하고자 간단한 형식으로 작성했지만, 여기서부터는 부가 설명이 필요할 것 같다. 우선 다양한 쿼리문을 테스트해보기 위해 로컬 MySQL 서버에 다음과 같이 테이블과 데이터를 생성해주었다. 귀찮아서 온라인 쿼리 사이트들도 사용해보려 했는데, 출력 결과 양식이 제대로 나오지 않아서(analyze 결과가..) 결국 MySQL Workbench를 사용했다.

스키마 구성은 제품 정보를 담는 product, 사용자 정보를 담는 customer, 그리고 주문 기록을 담는 orders 테이블로 간단히 구성했다.

▶테이블 생성 및 데이터 삽입 쿼리
-- product 테이블 생성
CREATE TABLE product (
  product_id INT AUTO_INCREMENT PRIMARY KEY,
  product_nm VARCHAR(100),
  description VARCHAR(255)
);

INSERT INTO product (product_nm, description) VALUES 
  ('Entity Framework Extensions', 'Use <a href="https://entityframework-extensions.net/" target="_blank">Entity Framework Extensions</a> to extend your DbContext with high-performance bulk operations.'),
  ('Dapper Plus', 'Use <a href="https://dapper-plus.net/" target="_blank">Dapper Plus</a> to extend your IDbConnection with high-performance bulk operations.'),
  ('C# Eval Expression', 'Use <a href="https://eval-expression.net/" target="_blank">C# Eval Expression</a> to compile and execute C# code at runtime.');

-- customer 테이블 생성
CREATE TABLE customer (
  customer_id INT AUTO_INCREMENT PRIMARY KEY,
  customer_nm VARCHAR(10)
);

INSERT INTO customer (customer_nm) VALUES 
  ('kate'),
  ('gia');

-- orders 테이블 생성
CREATE TABLE orders (
  order_id INT AUTO_INCREMENT PRIMARY KEY,
  customer_id INT,
  product_id INT,
  order_cnt INT,
  created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
  FOREIGN KEY (customer_id) REFERENCES customer(customer_id),
  FOREIGN KEY (product_id) REFERENCES product(product_id)
);

INSERT INTO orders (customer_id, product_id, order_cnt, created_at) VALUES 
  (1, 1, 2, '2025-01-01 09:00:00'),
  (1, 2, 4, '2025-01-15 11:30:00'),
  (2, 3, 1, '2025-02-01 15:45:00'),
  (2, 2, 5, '2025-02-01 17:30:00'),
  (2, 2, 5, '2025-02-11 14:00:00');

 

Workbench Visual Explain

workbench에서 쿼리를 실행하고 Result Grid 대신 Execution Plain 을 선택하면 아래와 같이 그림으로 실행 계획을 보여준다. 가장 직관적으로 확인할 수 있는 방법이다.

 

MySQL EXPLAIN 출력 형식

MySQL의 실행 계획을 보기 위해서는 쿼리문 앞에 EXPLAIN | DESCRIBE | DESC 명령어를 붙이면 된다. 3가지 모두 동일한 결과 출력한다. 추가로, MySQL 8부터 출력 형식을 단순 Table, JSON, Tree 형태로 지정 가능하다. json 형식은 기존의 표 형식보다 다양한 정보를 제공한다.

아래는 단순 출력 포맷을 보여주기 위한 예시로, 자세한 내용은 아직 몰라도 된다. 그리고, 정확히 무슨 기준인지는 모르겠지만 쿼리와 스키마가 모두 동일함에도 불구하고 explain/analyze 결과가 종종 달라지는 것 같다.. 그렇기 때문에 포스팅의 내용은 참고만 해주길! 이 부분에 대해서도 나중에 다룰 수 있다면 좋겠다.

-- 일반 테이블 형태
EXPLAIN 
SELECT * FROM customer;

-- JSON 형태
EXPLAIN FORMAT = JSON
SELECT * FROM customer;

-- TREE 형태
EXPLAIN FORMAT = TREE 
SELECT c.customer_nm, p.product_nm
FROM orders o, customer c, product p
WHERE o.customer_id = c.customer_id
	AND o.product_id = p.product_id;
▶JSON 형태
{
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "0.45"
    },
    "table": {
      "table_name": "customer",
      "access_type": "ALL",
      "rows_examined_per_scan": 2,
      "rows_produced_per_join": 2,
      "filtered": "100.00",
      "cost_info": {
        "read_cost": "0.25",
        "eval_cost": "0.20",
        "prefix_cost": "0.45",
        "data_read_per_join": "80"
      },
      "used_columns": [
        "customer_id",
        "customer_nm"
      ]
    }
  }
}

 

EXPLAIN ANALYZE 출력 형식

위에서 본 단순 EXPLAIN 결과는 MySQL 서버가 가지고 있는 통계 정보들을 활용한 예측 결과이다. 만약 실제 실행된 소요 시간과 실행 계획 정보를 출력하고 싶다면 ANALYZE 키워드를 사용해야 한다. 이 경우 Tree 형식으로 출력되며, 들여쓰기가 같은 레벨에서는 상단에 위치한 라인이 먼저 실행되고, 들여쓰기가 다른 레벨에서는 가장 안쪽에 위치한 라인이 먼저 실행된다.

EXPLAIN ANALYZE 
SELECT c.customer_nm, p.product_nm
FROM orders o, customer c, product p
WHERE o.customer_id = c.customer_id
	AND o.product_id = p.product_id;

 


EXPLAIN

필드 설명

이제 EXPLAIN 실행 결과 나오는 속성들에 대해 간단히 알아보겠다. 각 필드별 상세 옵션을 정리하기 보다는 간단한 정의를 알아보고, 실제 쿼리와 대조해보며 결과를 분석하는 방식을 익히는 데 초점을 맞추려고 한다.

사진은 아래 EXPLAIN 명령을 실행 시킨 결과이다. 이 중 rows와 filtered 속성은 MySQL의 통계 정보를 기반으로 한 것이며, 정확하지는 않은 값이다. 쿼리는 일부러 다양한 결과를 포함하고자 만든 것이므로 무의미하며 이해할 필요는 없다. 단순히 로직을 결과와 대조하며 이해하는 데 참고하길 바란다.

EXPLAIN 
(
  SELECT *  -- id = 1(row1~3)
  FROM orders o
  JOIN customer c ON o.customer_id = c.customer_id -- row2
  JOIN product p ON o.product_id = p.product_id -- row3
  WHERE c.customer_nm = 'gia' -- row1
  
  UNION ALL

  SELECT *  -- id = 2(row4~6)
  FROM orders o -- row 4
  JOIN customer c ON o.customer_id = c.customer_id -- row 5
  JOIN product p ON o.product_id = p.product_id -- row 6
  WHERE o.order_cnt > (
	SELECT COUNT(*)  -- id = 3(row 7)
    FROM orders
    WHERE created_at BETWEEN '2025-01-01' AND '2025-02-01'
  )
);

  • id: select를 기준으로 쿼리가 실행되는 순서를 나타낸다. MySQL에서는 조인을 하나의 단위로 실행하기 때문에 조인만 사용하는 쿼리라면 항상 1 값으로 나올 것이다. 위 예시에서는 union을 사용했고, 서브 쿼리까지 있기 때문에 id가 1~3까지 나온 것을 볼 수 있다.
  • select_type: select문의 유형을 나타낸다. 서브 쿼리나 union이 없으면 SIMPLE로 출력된다. union이 포함된 SQL 중 첫 번째 select의 타입은 PRIMARY, 아래 select는 UNION이다. SUBQUERY는 말 그대로 서브 쿼리에 해당한다.
  • table: 사용되는 테이블의 이름이나 alias를 출력한다. 서브쿼리나 임시 테이블을 만들 때에는 <subquery#> 나 <derived#>라고 출력된다. 만약 <derived2> 라면 id=2가 먼저 실행되고 그 결과인 임시 테이블을 참조하는 것이다.
▶마지막 row는 서브 쿼리인데 왜 table 값이 “subquery1”이 아니라 “orders”일까?

리턴하는 값이 COUNT, 즉 스칼라 값이기 때문이다. MySQL이 이를 상수로 취급하여 단순 테이블 필터링으로 변환된 것이다. (by chatGPT) 이렇게 다양한 상황이 존재할 수 있어서 옵티마이저의 결정을 이해하기가 어려운 것 같다.

  • partitions: 해당 쿼리가 사용하고 있는 파티션을 나타낸다. 파티션이란 큰 테이블을 여러 개의 작은 논리적 단위로 나눈 것을 뜻한다. 지금은 사용하고 있지 않기 때문에, 파티션을 활용한다면 더 빨리 처리할 수 있다는 정도만 알고 넘어가자.
  • type: 테이블에서 데이터를 찾는 접근 방식을 나타낸다. 쿼리의 성능에 많은 영향을 미치는 매우 중요한 항목이다. ALL은 풀 스캔, 즉 테이블 전체를 스캔한 것이다. ref와 eq_ref는 비슷하지만, eq_ref는 기본 키나 유니크 키를 사용해서 항상 하나의 행만 반환한 것이고, ref는 일반 인덱스를 사용하기 때문에 여러 개의 행이 반환될 수 있다. 즉, eq_ref가 하나의 행만 찾으면 되기 때문에 더 효율적이다.
▶왜 row2와 row3의 type이 다를까?

customer_id와 product_id는 둘 다 테이블의 기본 키인데 왜 row2는 ref이고 row3은 eq_ref일까? 이는 기준이 되는 table이 다르기 때문이다. row2의 table은 o로, orders 테이블에서의 customer_id(key)는 기본키가 아니기 때문에 일반 인덱스로 취급되어 ref인 것이다. row3의 table은 p이고, product_id(key)가 product 테이블의 키가 맞기 때문에 eq_ref이다. 그래서 key 필드에 PRIMARY라고 표시된 것이기도 하다.

  • possible_keys: 옵티마이저가 사용할 수 있는 인덱스 목록을 표시한다. 실제 사용된 것이 아니라 사용 가능한 것이다.
  • key: 위 목록 중에서 실제로 사용한 인덱스다. PRIMARY는 해당 테이블의 기본 키가 사용된 것이며, NULL인 경우 인덱스를 사용하지 않은 것이다. 이 경우 key, key_len, ref가 전부 NULL인 것을 확인할 수 있다.
  • key_len: 사용한 인덱스의 바이트 수이다. 복합 인덱스라면 인덱스를 모두 더한 값이 나온다. 인덱스가 길면 비효율적이기 때문에 참고할 수 있다.
  • ref: 조인 시 액세스된 테이블 정보가 표시된다. row2는 o 테이블(table)의 customer_id(key)를 c 테이블의 customer_id(ref)와 비교하여 조인했다는 의미이다.
  • rows: 접근 방식을 통해 접근한 행의 수를 나타낸다.
  • filtered: 스토리지 엔진에서 가져온 데이터를 MySQL 엔진이 필터링하여 제거된 비율을 나타낸다. row1의 경우, 사용자가 2명밖에 없기 때문에 where 조건으로 50% 필터링되었다는 의미이다. row7도 총 5개의 데이터 중 하나만 해당 범위를 벗어나기 때문에 20%가 필터링되었다.
  • Extra: 옵티마이저의 동작에 대한 추가 정보를 나타낸다. 여기서는 WHERE 절을 이용해서 데이터를 필터링 했음을 알 수 있다.

 


ANALYZE

출력 양식 설명

analyze를 사용하면 쿼리의 실행 시간과 각 단계의 실행 계획을 구체적으로 알 수 있다. EXPLAIN이 통계 수치를 기반으로 예상한 값을 알려줬다면, ANALYZE는 실제 데이터를 기반으로 한다. 출력은 트리 구조로 표시되며, 가장 안쪽에 들여쓰기된 작업이 먼저 실행된다. 각 줄은 조인이나 스캔 등의 작업 정보와 실행 시간에 대한 비용 정보로 구성된다.

 

 

비용 정보 형식

(cost=X rows=Y) (actual time=A...B rows=Z loops=D)

  • X: 옵티마이저가 예측한 비용
  • Y: 옵티마이저가 예측한 처리 결과 행의 수
  • A: 첫 번째 행을 반환하는데 걸린 시간(ms)
  • B: 모든 행을 반환하는데 걸린 총 시간(ms)
  • C: 실제 처리된 결과 행의 수
  • D: 해당 작업이 반복된 횟수

 


References

'Computer Science > 데이터베이스' 카테고리의 다른 글

DB 스캔 종류와 mysql explain type 칼럼  (0) 2025.04.28
DB Index란?  (0) 2025.04.24
Mysql 옵티마이저와 통계 정보  (0) 2025.02.15

MySQL 구조와 실행 순서

MySQL 구조

  • MySQL 엔진
    • Connection Handler: Client와의 연결을 관리하고 쿼리 요청을 처리
    • SQL 인터페이스: DML, DDL, Procedure, View 등 SQL 인터페이스 제공
    • SQL 파서: SQL 문법 오류 탐지 및 서버에서 처리하기 위한 트리 형태로 파싱
    • SQL 옵티마이저: 쿼리 최적화 및 실행 계획 수립
    • 캐시와 버퍼: 성능 향상을 위한 보조 저장소 기능
  • Storage 엔진
    • 핸들러 API를 통해 MySQL 엔진이 스토리지 엔진에 읽기/쓰기 요청
    • 스토리지 엔진은 플러그인 형태로 제공되기 때문에 테이블마다 선택 가능(InnoDB가 기본값)

 

쿼리 실행 순서

  1. SQL 파싱
    • MYSQL 서버의 SQL 파서라는 모듈에서 처리하며, 토큰 단위의 SQL 파싱 트리를 생성
  2. 전처리
    • 파싱 트리를 기반으로 쿼리 문장의 구조적 문제점 검사
    • 테이블과 칼럼의 존재 여부, 접근 권한 등도 체크
  3. 최적화 및 실행 계획 수립
    • 옵티마이저가 파싱 트리를 통해 최적의 실행 계획을 수립
    • 불필요한 조건 제거 및 복잡한 연산의 단순화, 레코드의 임시 테이블 저장 등을 처리
  4. 데이터 로드 및 처리
    • 위 실행 계획을 기반으로 Storage 엔진으로부터 데이터 로드
    • MySQL 엔진에서 받은 레코드를 조인하거나 정렬하는 작업을 수행

 


MySQL 옵티마이저

옵티마이저란

  • DBMS의 목적은 많은 데이터를 안전하고 빠르게 저장 및 관리하는 것
  • 이를 위해 옵티마이저가 쿼리를 최적화하며, 2가지 종류가 있음
  • 비용 기반 최적화(Cost-based optimizer, CBO)
    • 현재 대부분의 DBMS는 CBO 방식을 사용
    • 각 단위 작업의 비용 정보와 통계 정보를 활용하여 비용을 산출
  • 규칙 기반 최적화(Rule-based optimizer, RBO)
    • 단순히 옵티마이저에 내장된 우선 순위에 따라 실행 계획을 수립
    • 같은 쿼리에 대해서는 항상 같은 계획을 수립한다는 특징을 가짐

 

MySQL의 Optimizer

  • MySQL의 옵티마이저는 비용 기반으로 쿼리를 최적화함
  • 어디까지나 추정 값이며 항상 최적의 실행 계획을 만들어낼 수 있는 것은 아님
  • 사용자가 보완할 수 있도록 EXPLAIN 기능을 제공함 → 쿼리 튜닝에 활용

 

EXPLAIN/ANALYZE

자세한 포스팅은 다음 글을 참고!

  • EXPLAIN
    • 옵티마이저가 주어진 쿼리에 대해서 수립한 실행 계획
    • 실제 수행 순서가 아닌 MySQL의 통계 정보를 기반으로 계산한 예측 값
  • EXPLAIN ANALYZE(MySQL 8부터 지원)
    • 실제 실행된 쿼리의 계획과 단계 별 소요 시간을 TREE 형식으로 출력
    • 들여쓰기가 같은 레벨에서는 상단에 위치한 라인이 먼저 실행됨
    • 들여쓰기가 다른 레벨에서는 가장 안쪽에 위치한 라인이 먼저 실행됨

 


통계 정보

통계 저장 범위의 확장

  • MySQL 5.5: 각 테이블의 통계 정보가 메모리에 관리되어 서버 재시작 시 모두 사라짐
  • MySQL 5.6: InnoDB 스토리지 엔진에 통계 정보를 영구적으로 관리
  • MySQL 8: 데이터 분포도를 수집해 저장하는 히스토그램 정보가 도입

 

자동/수동 수집

  • 기본적으로 자동 수집되며, 필요에 따라 수집 방식 조정 가능
  • ANALYZE TABLE 명령어를 통해 특정 테이블의 최신 통계 정보 갱신 가능
  • SHOW INDEX 명령어를 통해 최신 통계 정보 확인 가능
  • 기본적으로 자동 수집되며, 필요에 따라 수집 방식 조정 가능
  • 히스토그램은 명령어를 통해 수동으로 수집되며 시스템 딕셔너리에 컬럼 단위로 저장되어 관리됨. MySQL 서버가 시작될 때 information_schema.column_statistics 테이블에 로드하여 활용

 

자동 갱신 케이스

  • 테이블이 새로 오픈되는 경우
  • 테이블의 레코드가 대량으로 변경되는 경우(테이블 전체 레코드 1/6 규모의 INSERT, UPDATE, DELETE가 실행되는 경우)
  • ANALYZE TABLE 명령이 실행되는 경우
  • SHOW TABLE STATUS 혹은 SHOW INDEX 명령이 실행되는 경우
  • InnoDB 모니터가 활성화되는 경우
  • Innodb_stats_on_metadata 시스템 설정이 ON인 상태에서 SHOW TABLE STATUS 명령이 실행되는 경우

 

히스토그램의 용도

  • MySQL의 일반적인 통계는 인덱스를 기반으로 카디널리티를 예측하지만, 인덱스가 없는 칼럼의 데이터 분포를 제대로 반영하지 못할 수 있음
  • MySQL 5.7까지는 실제 응용 프로그램의 데이터는 항상 균등한 분포를 가지지 않는다는 점을 간과, 정확도가 높지 않았음
  • 예를 들어, 아래 테이블에서 order_status 칼럼의 값이 complete 90%와 canceled 10%의 비중이라면 MySQL의 기본 통계는 이를 반영하지 못해 잘못된 실행 계획을 세울 수 있음
SELECT * FROM orders WHERE order_status = 'completed';

⇒ 히스토그램을 수집하면 데이터 분포를 정확히 이해하고 최적의 실행 계획을 수립할 수 있음

 


References

'Computer Science > 데이터베이스' 카테고리의 다른 글

DB 스캔 종류와 mysql explain type 칼럼  (0) 2025.04.28
DB Index란?  (0) 2025.04.24
Mysql EXPLAIN/ANALYZE 간단 실습  (0) 2025.02.16

접근

처음엔 기존 냅색 알고리즘(평범한 배낭 문제)처럼 이차원 dp 배열을 선언했었다. dp[i][j] = i번째 동전까지 써서 j원을 만들 수 있는 경우의 수로 정의하고. 그런데 문제를 다시 생각해보니, 서로 다른 물건을 담는 것과는 다르게 이 문제에서는 같은 금액의 동전을 여러 번 써도 된다는 점을 깨달았다. 그래서 for(int i = 0;i < m;i += coin) 과 같이 n개의 동전에 대해서 모두 1을 설정한 후 시작해야 하나? 싶었다. 근데 그러면 배열에 0이 너무 많고 비효율적인 것 같아서 접근이 잘못된 것 같았다. 

 

그래서 사실 솔루션을 살짝 참고했다.. 역시나 이차원이나 쓸 필요가 없었다. 2년 만에 알고리즘을 풀다보니 까먹은 내용이 너무 많았는데, 특히 dp가 감을 다시 되살리기 제일 어려운 것 같다. 앞으로는 일차원 배열을 재사용할 수 있는지 고려해볼 것! 그리고 무엇보다 dp는 직접 표를 그려가며 규칙을 찾는게 제일 쉬운 접근법인 것 같다. 머리로만 풀려고 하지 말자. 

 

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int tc = Integer.parseInt(br.readLine());
        for(int t = 0;t < tc;t++){
            // 입력값 저장
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] coins = new int[n];
            
            for(int i = 0;i < n;i++){
                int coin = Integer.parseInt(st.nextToken());
                coins[i] = coin;
            }

            int m = Integer.parseInt(br.readLine());

            // 냅색 알고리즘 계산
            int answer = solve(coins, n, m);
            sb.append(answer).append("\n");
        }

        // 결과값 출력
        System.out.println(sb.toString());
    }

    static int solve(int[] coins, int n, int m){
        int result = 0;
        int[] dp = new int[m+1];

        for(int i = 1;i <= n;i++){
            int curCoin = coins[i-1];
            
            for(int j = 0;j <= m;j++){
                if(j == curCoin) dp[j] += 1;
                else if(curCoin < j) dp[j] += dp[j-curCoin];
            }
        }
        result = dp[m];
        return result;
    }
}

'Algorithm' 카테고리의 다른 글

[백준] 1976: 여행 가자 JAVA  (0) 2025.03.01
[백준] 11403: 경로 찾기 JAVA  (0) 2025.02.28
[백준] 12865: 평범한 배낭 JAVA  (0) 2025.02.13
[백준] 13904: 과제 JAVA  (0) 2023.03.20
[백준] 1374: 강의실 JAVA  (0) 2023.03.20

접근

우선 이 블로그에서 냅색 알고리즘을 공부한 뒤 문제를 풀었다. 자꾸 내 머리로 생각을 안하고 블로그에서 본 점화식을 은연중에 따라하려고 해서 자꾸 답은 안나오는데 이유는 모르겠고 더 헤맸던 것 같다. 아예 작성하던 코드를 버리고 처음부터 내 방식대로(나는 물건 인덱스가 첫 번째 차원에 오는게 더 이해하기 쉬운 것 같다) 풀었더니 금방 성공했다. 

 

여기서 주의할 점은, (현재 수납 가능한 무게) - (넣고자 하는 물건의 무게)가 음수가 될 때의 처리인 것 같다. 나는 처음에 continue만 했기 때문에 최종 결과값이 0이 나오기도 했었다. dp 배열값은 항상 갱신해줘야 함에 유의하자. 

 

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int n, k;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력값 저장
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int[] weights = new int[n];
        int[] values = new int[n];
        
        for(int i = 0;i < n;i++){
            st = new StringTokenizer(br.readLine());
            weights[i] = Integer.parseInt(st.nextToken());
            values[i] = Integer.parseInt(st.nextToken());
        }

        // 냅색 알고리즘
        int answer = solve(weights, values);
        
        // 결과 출력
        System.out.println(answer); 
    }

    static int solve(int[] weights, int[] values){
        int result = 0;
        int[][] dp = new int[n+1][k+1];  // dp[i][j] = i번째 물건까지 넣었을 때, j 무게까지의 최대 가치

        for(int i = 1;i <= n;i++){
            int weight = weights[i-1];
            int value = values[i-1];
            
            for(int j = 1;j <= k;j++){
                if(j < weight) {
                    dp[i][j] = dp[i-1][j];
                    continue;
                }
                
                int curMaxVal = Math.max(dp[i-1][j], dp[i-1][j-weight] + value);
                dp[i][j] = curMaxVal;
                result = Math.max(result, curMaxVal);
            }
        }

        return result;
    }
}

 

'Algorithm' 카테고리의 다른 글

[백준] 11403: 경로 찾기 JAVA  (0) 2025.02.28
[백준] 9084: 동전 JAVA  (0) 2025.02.14
[백준] 13904: 과제 JAVA  (0) 2023.03.20
[백준] 1374: 강의실 JAVA  (0) 2023.03.20
[백준] 11286: 절댓값 힙 JAVA  (0) 2023.03.20

페이지 테이블

페이지 테이블 엔트리(PTE)

  • present/absent bit: 해당 PTE의 사용 여부를 나타냄
  • reference bit: 해당 페이지가 접근된 적이 있는지
  • modify bit(dirty): 해당 페이지값이 변경된 적이 있는지
  • protection bit: read/write/execute 등 어떤 작업들이 허용되는지를 나타냄

 

VPN, PFN

  • 페이지 테이블은 프로세스가 가질 수 있는 페이지의 개수만큼 주소 변환 엔트리를 가짐
  • 논리 주소는 VPN(Virtual Page Number)와 offest으로 구성
  • PTE에는 PFN(Page Frame Number)를 저장하고 있으며, 물리주소는 PFN+offset이 됨
  • VPN은 페이지 테이블을 위한 인덱스일 뿐임

 

페이징의 단점

  • 내부 단편화는 여전히 존재함
  • 2번의 메모리 접근으로 인한 속도 저하TLB가 등장
    • 페이지 테이블도 DRAM에 저장되어 있음
    • 결국 (1)페이지 테이블과 (2)실제 물리 주소 와 같이 2번 접근이 필요
  • 한 프로세스당 하나의 페이지 테이블이 존재하고, 한 주소당 하나의 PTE를 사용하기 때문에 테이블에 해당하는 용량이 많아질 수 있음

 


TLB(Translation Lookaside Buffer)

MMU with TLB

  • TLB란 MMU에 소속된 칩으로, 메모리와 CPU 사이에 있는 주소 변환을 위한 캐시
  • 페이지 테이블에 있는 리스트를 보관하며 CPU가 페이지 테이블까지 가지 않도록 해 속도를 향상시킬 수 있는 캐시 계층
  • 자주 참조되는 가상-물리주소 변환 정보를 저장

 

TLB의 문제점

  • TLB 정보는 이를 탑재시킨 프로세스에서만 유효함
  • 즉, 다른 프로세스가 동작할 때는 필요없는 정보가 TLB에 남게됨

 

단점 해결 방법

  1. 프로세스 context switching 시 TLB를 비우기
    • 빈번하게 발생할 경우 성능에 부담이 됨
  2. TLB 내에 프로세스를 식별하기 위한 주소 공간 식별자 필드를 추가
    • ASID(Address Space Identifier) 라고 함
    • 각각의 task마다 ID를 고유로 부여하며 이를 ASID에 표시하여 저장

 


페이지 테이블의 종류

Multilevel(Hierarchy) Page Table

 

Hashed Page Table

  • 각 항목은 연결 리스트를 가지고 있고, 해시 원소는 세 개의 필드(가상 페이지 번호, 매핑 프레임 번호, 다음 주소)를 가짐
  • 논리적 주소 공간의 페이지 번호인 p를 해시한 결과값으로 테이블을 검사한 뒤, 해당 물리적 메모리를 찾아가게 됨
  • 64bit 시스템에서는 클러스터형 페이지 테이블을 사용함
    • 해시형 페이지에서 각 항목들이 한 개의 페이지만 가리키는 대신 각 항목들이 여러 개의 페이지를 가리키는 방식
    • 따라서 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 매핑 정보를 지닐 수 있음
    • 메모리 접근이 불연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우에 유용

 

Inverted Page Table의 특징

https://www.youtube.com/watch?v=5cVGNOnFnvo

  • 기존 페이지 테이블
    • 보통 프로세스는 각자 하나씩 페이지 테이블을 가짐
    • 각 페이지 테이블 항목의 개수가 너무 많아질 수 있다는 단점이 있음
  • 역페이지 테이블
    • 논리적 주소가 아니라 물리적 메모리 주소 입장에서 만들어진 테이블 구조
    • 각 메모리 프레임마다 할당하여 페이지 테이블의 엔트리 개수 = 메모리 프레임의 수
    • 시스템에는 단 하나의 페이지 테이블만이 존재하여 메모리에서 훨씬 작은 공간을 점유
    • 몇 번째 프레임인지에 대한 정보가 아니라, 프로세스의 번호 pid를 저장

 

Inverted Page Table의 주소 계산 방법

  • 기존 테이블들의 경우에는 pageno를 인덱스로 하여 페이지 테이블에 바로 접근했지만, 역페이지 테이블의 경우 전체 테이블의 항목을 서치하며 해당 데이터와 일치하는 값을 찾아야 함
  • 따라서 메모리를 절약하는 대신, 탐색 시간이 오래걸릴 수 있다는 단점이 존재

⇒ 여기에 해시 테이블을 추가로 사용해 탐색 개수를 줄일 수 있음

Inverted 방식의 단점

  • 메모리 공유 불가
    • 모든 페이지와 프레임은 일대일 대응 관계이므로 프로세스간 메모리 공유가 불가능
    • 같은 프로세스 안에서도 페이지가 다르면 데이터 공유가 불가능
  • 페이지 테이블 참조 오버헤드
    • 주소의 매핑은 매우 빈번하게 일어나는데, 그때마다 테이블에서 pid/p 값을 찾아야함
    • 최악의 경우 페이지 테이블의 끝까지 탐색해야 하기 때문에 오버헤드가 굉장히 심함
    • 프로세스마다 페이지 테이블을 가지는 경우 페이지 테이블의 인덱스는 논리적 주소의 page#와 동일하기 때문에 바로 접근할 수 있지만, 역페이지 방식의 경우 메모리의 프레임 위치기 때문에 논리적 주소로 바로 접근이 불가능함

 


References

+ Recent posts