swh:1:snp:5115096b921df712aeb2a08114fede57fb3331fb
Revision 4229f6df508d9b02419c3da16c4f5aa7f2d6deae authored by Maysam Yabandeh on 12 October 2019, 03:28:36 UTC, committed by myabandeh on 16 October 2019, 17:51:46 UTC
Summary: Partition Filters make use of a top-level index to find the partition that might have the bloom hash of the key. The index is with internal key format (before format version 3). Each partition contains the i) blooms of the keys in that range ii) bloom of prefixes of keys in that range, iii) the bloom of the prefix of the last key in the previous partition. When ::SeekForPrev(key), we first perform a prefix bloom test on the SST file. The partition however is identified using the full internal key, rather than the prefix key. The reason is to be compatible with the internal key format of the top-level index. This creates a corner case. Example: - SST k, Partition N: P1K1, P1K2 - SST k, top-level index: P1K2 - SST k+1, Partition 1: P2K1, P3K1 - SST k+1 top-level index: P3K1 When SeekForPrev(P1K3), it should point us to P1K2. However SST k top-level index would reject P1K3 since it is out of range. One possible fix would be to search with the prefix P1 (instead of full internal key P1K3) however the details of properly comparing prefix with full internal key might get complicated. The fix we apply in this PR is to look into the last partition anyway even if the key is out of range. Pull Request resolved: https://github.com/facebook/rocksdb/pull/5907 Differential Revision: D17889918 Pulled By: maysamyabandeh fbshipit-source-id: 169fd7b3c71dbc08808eae5a8340611ebe5bdc1e
1 parent 73a35c6
Tip revision: 19076c95aa2bcee55c26fcf0960cc844ad86ee9c authored by Levi Tamasi on 21 January 2021, 22:18:25 UTC
Update HISTORY.md for PR 7888 (#7890)
Update HISTORY.md for PR 7888 (#7890)
Tip revision: 19076c9
File | Mode | Size |
---|---|---|
buckifier | ||
build_tools | ||
cache | ||
cmake | ||
coverage | ||
db | ||
docs | ||
env | ||
examples | ||
file | ||
hdfs | ||
include | ||
java | ||
logging | ||
memory | ||
memtable | ||
monitoring | ||
options | ||
port | ||
table | ||
test_util | ||
third-party | ||
tools | ||
trace_replay | ||
util | ||
utilities | ||
.clang-format | -rw-r--r-- | 138 bytes |
.gitignore | -rw-r--r-- | 853 bytes |
.lgtm.yml | -rw-r--r-- | 67 bytes |
.travis.yml | -rw-r--r-- | 3.6 KB |
.watchmanconfig | -rw-r--r-- | 130 bytes |
AUTHORS | -rw-r--r-- | 322 bytes |
CMakeLists.txt | -rw-r--r-- | 38.4 KB |
CODE_OF_CONDUCT.md | -rw-r--r-- | 3.3 KB |
CONTRIBUTING.md | -rw-r--r-- | 706 bytes |
COPYING | -rw-r--r-- | 17.7 KB |
DEFAULT_OPTIONS_HISTORY.md | -rw-r--r-- | 1.5 KB |
DUMP_FORMAT.md | -rw-r--r-- | 763 bytes |
HISTORY.md | -rw-r--r-- | 88.9 KB |
INSTALL.md | -rw-r--r-- | 7.5 KB |
LANGUAGE-BINDINGS.md | -rw-r--r-- | 1.1 KB |
LICENSE.Apache | -rw-r--r-- | 11.1 KB |
LICENSE.leveldb | -rw-r--r-- | 1.5 KB |
Makefile | -rw-r--r-- | 69.4 KB |
README.md | -rw-r--r-- | 1.8 KB |
ROCKSDB_LITE.md | -rw-r--r-- | 1.0 KB |
TARGETS | -rw-r--r-- | 33.3 KB |
USERS.md | -rw-r--r-- | 6.2 KB |
Vagrantfile | -rw-r--r-- | 1017 bytes |
WINDOWS_PORT.md | -rw-r--r-- | 12.5 KB |
appveyor.yml | -rw-r--r-- | 2.7 KB |
defs.bzl | -rw-r--r-- | 1.3 KB |
issue_template.md | -rw-r--r-- | 243 bytes |
src.mk | -rw-r--r-- | 32.2 KB |
thirdparty.inc | -rw-r--r-- | 7.8 KB |
Computing file changes ...