4.1 Nested Loops

 

 

use-the-index-luke 저자 Markus Winand

---------------------------------------------

Markus Winand는 SQL에 대한 통찰력을 제공하고 다양한 시스템이 SQL을 지원하는 방법을 modern-sql.com 에서 보여줍니다. 이전에 그는 use-the-index-luke.com 을 만들었는데, 지금도 활발하게 유지되고 있습니다. Markus는 winand.at 를 통해 강사, 연사 및 컨설턴트로 고용될 수 있습니다.

---------------------------------------------

You can upload a Korean translation of use-the-index-luke.com on your blog

Thank you from the bottom of my heart to author Makus Winand for allowing me.

 

These are translations that I use for studying by using a papago (google translate)

The translations may not be correct or there may be a typo.

I'd appreciate it if you could point it out in the comments.

---------------------------------------------

---------------------------------------------

use-the-index-luke.com 의 한글번역본을 블로그에 업로드 해도 된다고

허락해주신 Makus Winand 저자님께 진심으로 감사합니다.

 

이 번역본들은 제가 공부용도로 번역기(papago, google transrate)를 돌려서 

번역한 내용들이라 맞지 않거나, 오타가 있을수 있습니다.

댓글로 지적해주시면 감사하겠습니다.

---------------------------------------------

 

https://use-the-index-luke.com/sql/join/nested-loops-join-n1-problem

ㄴ중첩 루프

중첩 루프 조인은 가장 기본적인 조인 알고리즘입니다. 두 개의 중첩된 쿼리를 사용하는 것처럼 작동합니다. 하나의 테이블에서 결과를 가져오는 외부 또는 구동 쿼리와 다른 테이블에서 해당 데이터를 가져오는 구동 쿼리의 각 행에 대한 두 번째 쿼리입니다.

 

실제로 "중첩 선택"을 사용하여 중첩 루프 알고리즘을 직접 구현할 수 있습니다. 그럼에도 불구하고 네트워크 대기 시간이 디스크 대기 시간에 더하여 발생하여 전체 응답 시간을 더욱 악화시키기 때문에 이는 번거로운 접근 방식입니다. "중첩된 선택"은 인시하지 않고 구현하기 쉽기 때문에 여전히 매우 일반적입니다. ORM(Object-Relational Mapping) 도구는 이 점에서 특히 "유용"합니다. 소위 N+1 선택 문제가 이 분야에서 안타까운 악명을 얻게된 정도입니다.

 

다음 예는 다른 ORM 도구로 생성된 이러한 "우발적인 중첩 선택" 조인을 보여줍니다. 예제에서는 성이 'WIN'으로 시작하는 직원을 검색 하고 이러한 직원에 대해 판매기록을 모두 가져옵니다.

----------------------------------------------------------

The JPA example uses the CriteriaBuilder interface.

CriteriaBuilder queryBuilder = em.getCriteriaBuilder();
CriteriaQuery<Employees>
   query = queryBuilder.createQuery(Employees.class);
Root<Employees> r = query.from(Employees.class);
query.where(
  queryBuilder.like(
    queryBuilder.upper(r.get(Employees_.lastName)),
    "WIN%"
  )
);

List<Employees> emp = em.createQuery(query).getResultList();

for (Employees e: emp) {
  // process Employee
  for (Sales s: e.getSales()) {
    // process sale for Employee
  }
}

Hibernate JPA 3.6.0 generates N+1 select queries:

select employees0_.subsidiary_id as subsidiary1_0_
       -- MORE COLUMNS
  from employees employees0_
 where upper(employees0_.last_name) like ?

 

  select sales0_.subsidiary_id as subsidiary4_0_1_
         -- MORE COLUMNS
    from sales sales0_
   where sales0_.subsidiary_id=?
     and sales0_.employee_id=?

 

  select sales0_.subsidiary_id as subsidiary4_0_1_
         -- MORE COLUMNS
    from sales sales0_
   where sales0_.subsidiary_id=?
     and sales0_.employee_id=?

----------------------------------------------------------

ORM은 SQL 조인을 생성하지 않고 SALES 테이블에 중첩된 선택 항목을 쿼리합니다.

이 효과는 "N+1 selects problem" 또는 "N+1 problem"으로 알려져 있습니다. 이는 driving 쿼리가 N행을 반환하는 경우 총 N+1 selects를 실행하기 때문입니다.

----------------------------------------------------------

SQL 로깅 사용

개발 중 SQL 로깅을 사용하도록 설정하고 생성된 SQL문을 검토합니다.

 

DBIx::Class

export DBIC_TRACE=1 in your shell.

 

Doctrine

소스 코드 수준에서만 사용할 수 있습니다.

프로덕션용으로 이 기능을 사용하지 않도록 설정해야 합니다. 구성 가능한 로거를 직접 구축해 보십시오.

 

$logger = new \Doctrine\DBAL\Logging\EchoSqlLogger;

$config->setSQLLogger($logger);

Hibernate (native)

<property name="show_sql">true</property> in App.config or hibernate.cfg.xml

 

JPA

In persistence.xml but depending on the JPA provider—e.g., for eclipselink, Hibernate and OpenJPA:

 

<property name="eclipselink.logging.level" value="FINE"/>

<property name="hibernate.show_sql" value="TRUE"/>

<property name="openjpa.Log" value="SQL=TRACE"/>

Most ORMs offer a programmatic way to enable SQL logging as well. That involves the risk of accidentally deploying the setting in production.

----------------------------------------------------------

"중첩된 선택" 접근 방식은 반 패턴이지만 여전히 중첩된 루프 조인을 꽤 잘 설명합니다. 데이터베이스는 위의 ORM도구와 똑같이 조인을 실행합니다.

따라서 중첩 루프 조인에 대한 인덱싱은 위에 표시된 select 명령문에 대한 인덱싱과 같습니다. 이는 직원 테이블의 함수 기반 인덱스이고 판매 테이블의 조인 predicates에 대한 연결된 인덱스 입니다.

----------------------------------------------------------

CREATE INDEX emp_up_name ON employees (UPPER(last_name))

CREATE INDEX sales_emp ON sales (subsidiary_id, employee_id)

----------------------------------------------------------

SQL 조인은 동일한 인덱스 조회를 수행하더라도 네트워크 통신을 많이 방지하므로 중첩된 선택 접근 방식보다 효율적입니다. 매판매마다 직원 속성이 중복되기 때문에 전송되는 데이터의 총량이 더 크면 더욱 빠릅니다. 이는 응답 시간과 처리량이라는 두 가지 성능 차원 때문입니다. 컴퓨터 네트워크에서는 대기 시간과 대역폭이라고 합니다. 대역폭은 응답시간에 작은 영향을 미치지만 지연 시간은 큰 영향을 미칩니다. 즉, 데이터베이스 왕복 횟수가 전송되는 데이터의 양보다 응답 시간에 더 중요합니다.

----------------------------------------------------------

Tip

 

데이터베이스에서 조인을 실행합니다.

----------------------------------------------------------

대부분의 ORM 도구는 SQL 조인을 만들 수 있는 몇 가지 방법을 제공합니다. 소위 열정적인 fetching mode가 아마 중요한 모드일 것입니다. 일반적으로 엔티티 매핑의 속성 수준(예: 판매 클래스의 직원 속성)에서 구성됩니다. 그러면 ORM 도구는 판매 테이블에 액세스할 때 항상 직원 테이블에 연결됩니다. 엔티티 매핑에서 신속한 가져오기를 구성하는 것은 판매 데이터와 함께 직원 세부 정보가 항상 필요한 경우에만 의미가 있습니다.

 

상위 개체에 액세스할 때마다 하위 레코드가 필요하지 않으면 빠르게 가져오는 것은 역효과를 낳습니다. 전화번호부 애플리케이션의 경우, 직원 세부 정보를 표시할 때 판매 기록을 로드하는 것은 의미가 없습니다.

 

다른 경우에는 관련 영업 데이터가 필요할 수 있지만 항상 필요한 것은 아닙니다.

정적 구성은 해결책이 아닙니다.

----------------------------------------------------------

The JPA CriteriaBuilder interface 는 Root<>을 제공합니다.

조인을 제어하기 위한 fetch() 메서드입니다.

참조된 개체를 기본 쿼리에 가입시키는 시기와 방법을 지정할 수 있습니다. 이 예에서는 일부 직원이 매출이 없더라도 왼쪽 조인을 사용하여 모든 직원을 검색합니다.

 

-------------------------------------------------

경고

JPA와 Hibernate는 판매할 때마다 직원을 반환합니다.

 

매출이 30개인 직원이 30번 등장한다는 뜻입니다.

매우 방해가 되지만 지정된 동작(EJB 3.0 지속성, 항목 4.4.5.3 "Fetch Joins".)입니다. 예를 들어 LinkedHashSet을 사용하여 상위 관계를 수동으로 복제하거나 예저와 같이 distinct() 함수를 사용할 수 있습니다.

-------------------------------------------------

 

CriteriaBuilder qb = em.getCriteriaBuilder();

CriteriaQuery<Employees> q = qb.createQuery(Employees.class);

Root<Employees> r = q.from(Employees.class);

q.where(queryBuilder.like(

    queryBuilder.upper(r.get(Employees_.lastName)),

    "WIN%")

);

 

r.fetch("sales", JoinType.LEFT);

// needed to avoid duplication of Employee records

q.distinct(true);

 

List<Employees> emp = em.createQuery(q).getResultList();

 

Hibernate 3.6.0 generates the following SQL statement:

 

select distinct

       employees0_.subsidiary_id as subsidiary1_0_0_

     , employees0_.employee_id as employee2_0_0_

       -- MORE COLUMNS

     , sales1_.sale_id as sale1_0__

  from employees employees0_

  left outer join sales sales1_

          on employees0_.subsidiary_id=sales1_.subsidiary_id

         and employees0_.employee_id=sales1_.employee_id

 where upper(employees0_.last_name) like ?

 

 

쿼리에 예산된 왼쪽 조인이 있지만 불필요한 고유 키워드도 있습니다. 안타깝게도 JPa는 자식 레코드의 중복을 제거하지 않고 중복된 부모 항목을 필터링하기 위한 별도의 API 호출을 제공하지 않습니다.

SQL 쿼리의 고유 키워드는 대부분의 데이터베이스가 실제로 중복 레코드를 필터링하기 때문에 경고합니다.

일부 데이터베이스만 기본 키가 이 경우 고유성을 보장한다는 것을 인식합니다.

 

 

The native Hibernate API solves the problem on the client side using a result set transformer:

 

Criteria c = session.createCriteria(Employees.class);

c.add(Restrictions.ilike("lastName", 'Win%'));

 

c.setFetchMode("sales", FetchMode.JOIN);

c.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);

 

List<Employees> result = c.list();

 

 

 

It generates the following query:

 

select this_.subsidiary_id as subsidiary1_0_1_

     , this_.employee_id as employee2_0_1_

       -- MORE this_ columns on employees

     , sales2_.sale_id as sale1_3_

       -- MORE sales2_ columns on sales

  from employees this_

  left outer join sales sales2_

          on this_.subsidiary_id=sales2_.subsidiary_id

         and this_.employee_id=sales2_.employee_id

 where lower(this_.last_name) like ?

 

 

이 메서드는 의도하지 않은 절 없이 직선 SQL을 생성합니다. 최대 절전 모드에서는 대/소문자를 구분하지 않는 쿼리에 lower()를 사용합니다. 이는 기능 기반 인덱싱에 중요한 세부 정보입니다.

----------------------------------------------------------

실행 계획은 NESTED LOOPS OUTER 연상을 표시합니다.

 

----------------------------------------------------------

---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  822 |   38 |
| 1 | NESTED LOOPS OUTER          |             |  822 |   38 |
| 2 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |    1 |    4 |
|*3 |   INDEX RANGE SCAN          | EMP_UP_NAME |    1 |      |
| 4 |  TABLE ACCESS BY INDEX ROWID| SALES       |  821 |   34 |
|*5 |   INDEX RANGE SCAN          | SALES_EMP   |   31 |      |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
  3 - access(UPPER("LAST_NAME") LIKE 'WIN%')
      filter(UPPER("LAST_NAME") LIKE 'WIN%')
  5 - access("E0_"."SUBSIDIARY_ID"="S1_"."SUBSIDIARY_ID"(+)
        AND  "E0_"."EMPLOYEE_ID"  ="S1_"."EMPLOYEE_ID"(+))

----------------------------------------------------------

데이터베이스는 먼저 EMP_UP_NAME을 통해 EMPLOYEES 테이블에서 결과를 검색하고 이후 각 직원에 대한 해당 레코드를 SALES 테이블에서 가져옵니다.

 

----------------------------------------------------------

Tip

 

ORM을 파악하고 조인을 제어합니다.

ORM 도구마다 조인 동작을 제어하는 방법이 다릅니다. Eager fetching은 모든 개체 관계형 매퍼에서 제공하지 않는 하나의 예에 불과합니다.

ORM의 기능을 조사하는 작은 표본 집합을 구현하는 것이 좋습니다. 이것은 좋은 연습일 뿐만 아니라 개발 중에 참조로 사용될 수 있으며, 조인을 사용할 때의 부작용으로 부모 레코드를 복제하는 것과 같은 예상치 못한 동작을 보여줄 수 있습니다. 샘플을 다운로드하여 시작합니다.

----------------------------------------------------------

 

중첩된 루프 조인은 diriving 쿼리가 작은 결과 집합을 반환하는 경우 우수한 성능을 제공합니다. 그렇지 않으면 최적화 도구가 다음 섹션에 설명된 해시 조인과 같이 완전히 다른 조인 알고리즘을 선택할 수 있지만, 이는 응용 프로그램이 조인을 사용하여 데이터베이스에 실제로 필요한 데이터를 알려주는 경우에만 가능합니다.