limit,offset 페이지 장면 을 사용 할 때 왜 느 립 니까?

한 문제 부터 말하자면
5 년 전 텐 센트 에서 페이지 를 나 누 는 장면 에서 my sql 요청 속도 가 매우 느 린 것 을 발견 했다.데이터 양 이 10w 밖 에 안 되 는 상황 에서 select xx from 단일 컴퓨터 는 약 2,3 초 입 니 다.
나 는 스승 님 께 왜 냐 고 물 었 다.그 는"색인 장면,my sql 에서 n 번 째 로 큰 수 를 얻 었 는데 시간 복잡 도 는 얼마 입 니까?"라 고 반문 했다.
답안 의 추적
장면 확인
status 에 색인 이 있다 고 가정 합 니 다.select * from table where status = xx limit 10 offset 10000。
아주 느 릴 겁 니 다.데이터 양 이 많 지 않 은 경우 에는 몇 초 지연 이 있다.
흰 둥 이 가 대답 하 다.
그 때 는 매우 안정 감 이 있 었 고 무슨 일이 든 스승 님 께 서 맡 기 셨 습 니 다.어차피 기술 은 팀 에서 최 악이 라 서 log(N)를 멋대로 맞 혔 습 니 다.노드 를 찾 으 려 면 log(N)가 아 닙 니까?자 연 스 럽 게 스승 님 께 서 는 나 에 게 스스로 연구 하 라 고 하 셨 다.
이 단 계 는 10 분 이 걸 렸 다.
계속 대답 하 다
자세히 분석 해 보면 색인 을 통 해 찾 는 것 이 매우 어색 하 다 는 것 을 알 수 있다.앞의 100 개 수가 왼쪽 나무 와 오른쪽 자수의 분포 상황 을 모 르 기 때문에 이 진 트 리 의 검색 특성 을 이용 할 수 없습니다.
학습 을 통 해 my sql 의 색인 이 b+트 리 라 는 것 을 알 게 되 었 습 니 다.

이 그림 을 보고 탁 트 였 다.잎 노드 로 구 성 된 링크 를 통 해 o(n)의 복잡 도 로 100 번 째 큰 나 무 를 찾 을 수 있 습 니 다.그러나 o(n)라 도 사람 을 놀 라 게 할 정도 로 느 리 지 않 은 데 는 이유 가 있 을 까?
이 단 계 는 주로 인터넷 을 통 해 자 료 를 찾 아 중단 하고 10 일 동안 계속 사용 했다.
체계 적 학습
여 기 는 두 권 의 책 을 추천 합 니 다.한 권 의 는 그 를 통 해 InnoDB 의 실현 체제,예 를 들 어 mvcc,색인 실현,파일 저장 에 대해 더욱 깊이 이해 할 수 있 습 니 다.
두 번 째 책 은 이다.이 책 은 사용 차원 에서 시작 되 었 으 나 비교적 깊이 있 게 말 했 고 디자인 의 방향 도 많이 언급 했다.
두 권 의 책 을 결합 하여 반복 적 으로 깨 닫 게 되면 my sql 은 겨우 방 에 들 어 갈 수 있 게 되 었 다.
여기에 두 가지 관건 적 인 개념 이 있다.
4.567917.클 러 스 터 색인:메 인 키 색인 과 대응 하 는 실제 데 이 터 를 포함 하고 색인 의 잎 노드 는 데이터 노드 입 니 다4.567917.보조 색인:2 급 노드 로 이해 할 수 있 습 니 다.그 잎 노드 는 색인 노드 이 고 메 인 키 id 를 포함 합 니 다
앞의 10000 개가 버 려 도 my sql 은 2 급 색인 에 있 는 메 인 키 id 를 통 해 클 러 스 터 색인 에서 데 이 터 를 한 번 찾 습 니 다.이것 은 10000 번 의 랜 덤 io 이 므 로 자 연 스 럽 게 하 스 치가 느 립 니 다.
여기 서 왜 이런 행동 을 했 는 지 의문 을 제기 할 수 있 습 니 다.이것 은 my sql 의 레이 어 링 과 관계 가 있 습 니 다.limit offset 은 엔진 층 이 돌아 오 는 결과 집합 에 만 작용 할 수 있 습 니 다.엔진 층 도 무고 하 다 는 얘 기다.10000 개가 버 려 야 한 다 는 사실 을 몰 랐 다.
다음은 my sql 레이 어 링 설명도 입 니 다.엔진 층 과 server 층 이 실제 분 리 된 것 을 볼 수 있 습 니 다.

이때 까지 느 린 이 유 를 대충 알 았 다.이 단 계 는 1 년 이 걸 렸 다.
유추
이때 일 한 지 3 년 이 되 었 고 소스 코드 도 보기 시작 했다.etcd 를 본 후에 tidb 의 소스 코드 를 보 았 습 니 다.어떤 데이터 베 이 스 를 막론하고 사실은 한 문장의 조 회 는 논리 연산 자로 구성 된다.
논리 연산 자 소개
구체 적 인 최적화 규칙 을 쓰기 전에 먼저 조회 계획 안의 논리 적 계산 자 를 간단하게 소개 한다.

DataSource 이것 이 바로 데이터 소스,즉 표,select*from t 안의 t 입 니 다

selection 선택,예 를 들 어 select xxx from t where xx=5 안의 where 여과 조건

Projection 투영,selectc from t 안의 c 열 은 투영 작업 입 니 다

Join 연결,select xx from t1,t2 where t1.c=t2.c 는 t1 t2 두 개의 시 계 를 Join 으로 하 는 것 입 니 다

선택,투영,연결(SPJ 로 약칭)은 가장 기본 적 인 연산 자 입 니 다.이 가운데 조 인 트 는 내부 연결,왼쪽,오른쪽,외부 연결 등 다양한 연결 방식 이 있다.
select b from t1,t2 where t1.c=t2.c and t1.a>5 가 논리 적 조회 계획 으로 바 뀐 후 t1 t2 에 대응 하 는 DataSource 는 데 이 터 를 건 져 올 리 는 것 을 책임 집 니 다.
위 에 Join 연산 자 를 연결 하여 두 표 의 결 과 를 t1.c=t2.c 로 연결 하고 t1.a>5 를 누 르 면 selection 필 터 를 하고 마지막 으로 b 열 을 투영 합 니 다.
다음 그림 은 최적화 되 지 않 은 표현 이다.

그 러 니까 my sql 이 limit,offset 을 엔진 층 에 전달 하고 싶 지 않 은 것 이 아니 라 논리 연산 자 를 나 누 었 기 때문에 구체 적 인 연산 자가 조건 에 맞 는 데 이 터 를 얼마나 포함 하고 있 는 지 알 수 없습니다.
어떻게
'고성능 MySQL'은 두 가지 방안 을 언급 했다.
방안 1
업무 의 실제 수요 에 따라 다음 페이지,이전 페이지 의 기능 으로 바 꿀 수 있 는 지,특히 ios,android 엔 드 에 서 는 예전 의 완전한 페이지 가 흔 하지 않 았 습 니 다.
limit,offset 을>보조 색인(즉 검색 조건)id 로 바 꾸 는 방식 입 니 다.이 id 를 다시 호출 할 때 전단 으로 되 돌려 야 합 니 다.
방안 2
정면 이 강하 다.여기 서 하나의 개념 을 소개 합 니 다.색인 커버:보조 색인 조회 데이터 가 id 와 보조 색인 자체 만 있 으 면 클 러 스 터 색인 을 찾 을 필요 가 없습니다.
사고방식 은 다음 과 같다:select xxx,xxx from in(select id from table where secondindex=xxx limit 10 offset 10000)이 말 은 조건 조회 에서 데이터 에 대응 하 는 데이터베이스 의 유일한 id 값 을 찾 습 니 다.메 인 키 는 보조 색인 에 있 기 때문에 클 러 스 터 색인 디스크 로 돌아 가 끌 어 올 리 지 않 아 도 됩 니 다.이미 limit 에서 나 온 10 개의 메 인 키 id 를 통 해 클 러 스 터 색인 을 조회 합 니 다.이렇게 하면 무 작위 io 가 열 번 밖 에 안 돼 요.
업무 가 확실히 페이지 를 나 눠 야 하 는 상황 에서 이 방안 을 사용 하면 성능 을 크게 향상 시 킬 수 있다.일반적으로 성능 요 구 를 만족 시 킬 수 있다.
마지막 에 쓰다
나의 스승 님 께 서 내 가 졸업 하기 3 년 전의 지도 에 매우 감 사 드 리 며 나 에 게 많은 인내심 을 주 셨 다.명절 과 휴일 에 저 에 게 책 을 읽 는 임 무 를 주 었 습 니 다.점심 시간 에 제 가 공부 하 는 진 도 를 살 펴 보고 질문 하 는 방식 으로 저 에 게 문 제 를 탐색 하도록 이 끌 었 습 니 다.저 는 텐 센트 를 졸업 한 후에 만 날 때마다 많은 아 이 디 어 를 주 었 습 니 다.수업 을 전수 하고 의혹 을 풀 었 습 니 다.어느 하나 도 이 루 지 못 했 습 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.