swh:1:snp:5115096b921df712aeb2a08114fede57fb3331fb
Revision cb7a00227ff3565000af4859664c77224106dcb5 authored by Dhruba Borthakur on 05 November 2012, 07:47:06 UTC, committed by Dhruba Borthakur on 06 November 2012, 00:08:01 UTC
Summary:
The method Version::GetOverlappingInputs used a sequential search
to map a kay-range to a set of files. But the files are arranged
in ascending order of key, so a biary search is more effective.

This patch implements Version::GetOverlappingInputsBinarySearch
that finds one file that corresponds to the specified key range
and then iterates backwards and forwards to find all overlapping
files.

This patch is critical for making compactions efficient, especially
when there are thousands of files in a single level.

I measured that 1000 iterations of TEST_MaxNextLevelOverlappingBytes
takes 16000 microseconds without this patch. With this patch, the
same method takes about 4600 microseconds.

Test Plan: Almost all unit tests in db_test uses this method to lookup keys.

Reviewers: heyongqiang

Reviewed By: heyongqiang

CC: MarkCallaghan, emayanke, sheki

Differential Revision: https://reviews.facebook.net/D6465
1 parent 5273c81
History
Tip revision: 19076c95aa2bcee55c26fcf0960cc844ad86ee9c authored by Levi Tamasi on 21 January 2021, 22:18:25 UTC
Update HISTORY.md for PR 7888 (#7890)
Tip revision: 19076c9
File Mode Size
db
doc
hdfs
helpers
include
java
port
scribe
snappy
table
thrift
tools
util
.arcconfig -rw-r--r-- 110 bytes
.gitignore -rw-r--r-- 61 bytes
AUTHORS -rw-r--r-- 193 bytes
LICENSE -rw-r--r-- 1.4 KB
Makefile -rw-r--r-- 9.2 KB
NEWS -rw-r--r-- 509 bytes
README -rw-r--r-- 1.7 KB
README.fb -rw-r--r-- 283 bytes
TODO -rw-r--r-- 494 bytes
build_detect_platform -rwxr-xr-x 7.9 KB
build_detect_version -rwxr-xr-x 1.1 KB
fbcode.gcc471.sh -rw-r--r-- 2.3 KB

README

back to top