range_del

# 1 memtable.

define
mem
  a.SET.1:b
  a.SET.3:c
  a.SET.5:d
  b.MERGE.1:b
  b.MERGE.3:c
  b.MERGE.5:d
  b.RANGEDEL.6:c
  b.MERGE.7:e
  c.SET.1:b
  c.SET.3:c
  c.SET.5:d
----
mem: 1

get seq=2
a
b
c
----
a:b
b:b
c:b

get seq=4
a
b
c
----
a:c
b:bc
c:c

get seq=6
a
b
c
----
a:d
b:bcd
c:d

get seq=7
a
b
c
----
a:d
b: pebble: not found
c:d

get seq=8
a
b
c
----
a:d
b:e
c:d

get seq=6
a
b
c
----
a:d
b:bcd
c:d

iter seq=6
first
next
next
next
seek-ge a
seek-ge b
seek-ge c
seek-ge d
last
prev
prev
prev
seek-lt a
seek-lt b
seek-lt c
seek-lt d
----
a:d
b:bcd
c:d
.
a:d
b:bcd
c:d
.
c:d
b:bcd
a:d
.
.
a:d
b:bcd
c:d

iter seq=7
first
next
next
seek-ge a
seek-ge b
seek-ge c
seek-ge d
last
prev
prev
seek-lt a
seek-lt b
seek-lt c
seek-lt d
----
a:d
c:d
.
a:d
c:d
c:d
.
c:d
a:d
.
.
a:d
a:d
c:d

# Multiple memtables.

define
mem
  a.SET.1:b
  b.MERGE.1:b
  c.SET.1:b
mem
  a.SET.3:c
  b.MERGE.3:c
  c.SET.3:c
mem
  a.SET.5:d
  b.MERGE.5:d
  c.SET.5:d
mem
  b.RANGEDEL.6:c
mem
  b.MERGE.7:e
----
mem: 5

get seq=2
a
b
c
----
a:b
b:b
c:b

get seq=4
a
b
c
----
a:c
b:bc
c:c

get seq=6
a
b
c
----
a:d
b:bcd
c:d

get seq=7
a
b
c
----
a:d
b: pebble: not found
c:d

get seq=8
a
b
c
----
a:d
b:e
c:d

get seq=6
a
b
c
----
a:d
b:bcd
c:d

iter seq=6
first
next
next
next
seek-ge a
seek-ge b
seek-ge c
seek-ge d
last
prev
prev
prev
seek-lt a
seek-lt b
seek-lt c
seek-lt d
----
a:d
b:bcd
c:d
.
a:d
b:bcd
c:d
.
c:d
b:bcd
a:d
.
.
a:d
b:bcd
c:d

iter seq=7
first
next
next
seek-ge a
seek-ge b
seek-ge c
seek-ge d
last
prev
prev
seek-lt a
seek-lt b
seek-lt c
seek-lt d
----
a:d
c:d
.
a:d
c:d
c:d
.
c:d
a:d
.
.
a:d
a:d
c:d

# Overlapping range deletions in the same memtable.

define
mem
  a.SET.1:1
  a.SET.3:2
  a.SET.5:3
  a.SET.7:4
  b.SET.1:1
  b.SET.3:2
  b.SET.5:3
  b.SET.7:4
  c.SET.1:1
  c.SET.3:2
  c.SET.5:3
  c.SET.7:4
  d.SET.1:1
  d.SET.3:2
  d.SET.5:3
  d.SET.7:4
  a.RANGEDEL.2:b
  b.RANGEDEL.4:c
  b.RANGEDEL.2:c
  c.RANGEDEL.6:d
  c.RANGEDEL.4:d
  c.RANGEDEL.2:d
----
mem: 1

get seq=2
a
b
c
d
----
a:1
b:1
c:1
d:1

get seq=3
a
b
c
d
----
a: pebble: not found
b: pebble: not found
c: pebble: not found
d:1

get seq=5
a
b
c
d
----
a:2
b: pebble: not found
c: pebble: not found
d:2

get seq=7
a
b
c
d
----
a:3
b:3
c: pebble: not found
d:3

get seq=9
a
b
c
d
----
a:4
b:4
c:4
d:4

iter seq=2
first
next
next
next
next
last
prev
prev
prev
prev
----
a:1
b:1
c:1
d:1
.
d:1
c:1
b:1
a:1
.

iter seq=3
first
next
last
prev
----
d:1
.
d:1
.

iter seq=5
first
next
next
last
prev
prev
----
a:2
d:2
.
d:2
a:2
.

iter seq=7
first
next
next
next
last
prev
prev
prev
----
a:3
b:3
d:3
.
d:3
b:3
a:3
.

iter seq=9
first
next
next
next
next
last
prev
prev
prev
prev
----
a:4
b:4
c:4
d:4
.
d:4
c:4
b:4
a:4
.

# Overlapping range deletions in different memtables. Note that the
# range tombstones are not fragmented in this case.

define
mem
  a.SET.1:1
  b.SET.1:1
  c.SET.1:1
  d.SET.1:1
mem
  a.SET.3:2
  b.SET.3:2
  c.SET.3:2
  d.SET.3:2
  a.RANGEDEL.2:d
mem
  a.SET.5:3
  b.SET.5:3
  c.SET.5:3
  d.SET.5:3
  b.RANGEDEL.4:d
mem
  a.SET.7:4
  b.SET.7:4
  c.SET.7:4
  d.SET.7:4
  c.RANGEDEL.4:d
----
mem: 4

get seq=2
a
b
c
d
----
a:1
b:1
c:1
d:1

get seq=3
a
b
c
d
----
a: pebble: not found
b: pebble: not found
c: pebble: not found
d:1

get seq=5
a
b
c
d
----
a:2
b: pebble: not found
c: pebble: not found
d:2

get seq=7
a
b
c
d
----
a:3
b:3
c: pebble: not found
d:3

get seq=9
a
b
c
d
----
a:4
b:4
c:4
d:4

iter seq=2
first
next
next
next
next
last
prev
prev
prev
prev
----
a:1
b:1
c:1
d:1
.
d:1
c:1
b:1
a:1
.

iter seq=3
first
next
last
prev
----
d:1
.
d:1
.

iter seq=5
first
next
next
last
prev
prev
----
a:2
d:2
.
d:2
a:2
.

iter seq=7
first
next
next
next
last
prev
prev
prev
----
a:3
b:3
d:3
.
d:3
b:3
a:3
.

iter seq=9
first
next
next
next
next
last
prev
prev
prev
prev
----
a:4
b:4
c:4
d:4
.
d:4
c:4
b:4
a:4
.

# User-key that spans tables in a level.

define
L1
  a.SET.3:3
L1
  a.SET.2:2
L1
  a.SET.1:1
----
mem: 1
1:
  000004:[a-a]
  000005:[a-a]
  000006:[a-a]

get seq=1
a
----
a: pebble: not found

get seq=2
a
----
a:1

get seq=3
a
----
a:2

get seq=4
a
----
a:3

iter seq=2
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:1
a:1
.
a:1
.
a:1

iter seq=3
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:2
a:2
.
a:2
.
a:2

iter seq=4
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:3
a:3
.
a:3
.
a:3

define
L1
  a.MERGE.3:3
L1
  a.MERGE.2:2
L1
  a.MERGE.1:1
----
mem: 1
1:
  000004:[a-a]
  000005:[a-a]
  000006:[a-a]

get seq=1
a
----
a: pebble: not found

get seq=2
a
----
a:1

get seq=3
a
----
a:12

get seq=4
a
----
a:123

iter seq=2
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:1
a:1
.
a:1
.
a:1

iter seq=3
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:12
a:12
.
a:12
.
a:12

iter seq=4
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:123
a:123
.
a:123
.
a:123

# User-key spread across multiple levels.

define
mem
  a.MERGE.4:4
L1
  a.MERGE.3:3
L2
  a.MERGE.2:2
L3
  a.MERGE.1:1
----
mem: 1
1:
  000004:[a-a]
2:
  000005:[a-a]
3:
  000006:[a-a]

get seq=1
a
----
a: pebble: not found

get seq=2
a
----
a:1

get seq=3
a
----
a:12

get seq=4
a
----
a:123

get seq=5
a
----
a:1234

iter seq=2
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:1
a:1
.
a:1
.
a:1

iter seq=3
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:12
a:12
.
a:12
.
a:12

iter seq=4
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:123
a:123
.
a:123
.
a:123

iter seq=5
first
seek-ge a
seek-ge b
last
seek-lt a
seek-lt b
----
a:1234
a:1234
.
a:1234
.
a:1234

# Range deletions on multiple levels.
define
L0
  a.SET.4:4
  b.SET.4:4
  d.SET.4:4
  c.RANGEDEL.4:d
L1
  a.SET.3:3
  d.SET.3:3
  b.RANGEDEL.3:d
L2
  d.SET.2:2
  a.RANGEDEL.2:d
L3
  a.SET.1:1
  b.SET.1:1
  c.SET.1:1
  d.SET.1:1
----
mem: 1
0.0:
  000004:[a-d]
1:
  000005:[a-d]
2:
  000006:[a-d]
3:
  000007:[a-d]

get seq=2
a
b
c
d
----
a:1
b:1
c:1
d:1

get seq=3
a
b
c
d
----
a: pebble: not found
b: pebble: not found
c: pebble: not found
d:2

get seq=4
a
b
c
d
----
a:3
b: pebble: not found
c: pebble: not found
d:3

get seq=5
a
b
c
d
----
a:4
b:4
c: pebble: not found
d:4

iter seq=2
first
next
next
next
last
prev
prev
prev
----
a:1
b:1
c:1
d:1
d:1
c:1
b:1
a:1

iter seq=3
first
last
----
d:2
d:2

iter seq=4
first
next
last
prev
----
a:3
d:3
d:3
a:3

iter seq=5
first
next
next
last
prev
prev
----
a:4
b:4
d:4
d:4
b:4
a:4

# Range deletions spanning tables within a level.

define
mem
  a.SET.3:3
  b.SET.3:3
  c.SET.3:3
  d.SET.3:3
L1
  a.RANGEDEL.2:b
L1
  b.RANGEDEL.2:c
L1
  c.RANGEDEL.2:d
L2
  a.SET.1:1
  b.SET.1:1
  c.SET.1:1
  d.SET.1:1
----
mem: 1
1:
  000004:[a-b]
  000005:[b-c]
  000006:[c-d]
2:
  000007:[a-d]

get seq=2
a
b
c
d
----
a:1
b:1
c:1
d:1

get seq=3
a
b
c
d
----
a: pebble: not found
b: pebble: not found
c: pebble: not found
d:1

get seq=4
a
b
c
d
----
a:3
b:3
c:3
d:3

iter seq=2
first
next
next
next
last
prev
prev
prev
----
a:1
b:1
c:1
d:1
d:1
c:1
b:1
a:1

iter seq=3
first
last
----
d:1
d:1

iter seq=4
first
next
next
next
last
prev
prev
prev
----
a:3
b:3
c:3
d:3
d:3
c:3
b:3
a:3

# Invalid LSM structure (range deletion at newer level covers newer
# write at an older level). This LSM structure is not generated
# naturally, but tested here to show the level-by-level nature of Get.

define
L1
  a.RANGEDEL.1:b
L2
  a.SET.2:2
----
mem: 1
1:
  000004:[a-b]
2:
  000005:[a-a]

get seq=3
a
----
a: pebble: not found

# A range tombstone straddles two SSTs. One is compacted to a lower level. Its
# keys that are newer than the range tombstone should not disappear.
#
# Uses a snapshot to prevent range tombstone from being elided when it gets
# compacted to the bottommost level.

define target-file-sizes=(100, 1) snapshots=(1)
L0
  a.RANGEDEL.1:e
L0
  a.SET.2:v
L0
  c.SET.3:v
----
mem: 1
0.1:
  000005:[a-a]
  000006:[c-c]
0.0:
  000004:[a-e]

compact a-e
----
1:
  000007:[a-c]
  000008:[c-e]

compact d-e
----
1:
  000007:[a-c]
2:
  000008:[c-e]

iter seq=4
seek-ge b
next
----
c:v
.

# Reverse the above test: compact the left file containing the split range
# tombstone downwards, and iterate from right to left.

define target-file-sizes=(100, 1) snapshots=(1)
L0
  a.RANGEDEL.1:e
L0
  a.SET.2:v
L0
  c.SET.3:v
----
mem: 1
0.1:
  000005:[a-a]
  000006:[c-c]
0.0:
  000004:[a-e]

compact a-e
----
1:
  000007:[a-c]
  000008:[c-e]

compact a-b
----
1:
  000008:[c-e]
2:
  000007:[a-c]

iter seq=4
seek-lt d
prev
prev
----
c:v
a:v
.

# A range tombstone straddles two sstables. One is compacted two
# levels lower. The other is compacted one level lower. The one that
# is compacted one level lower should not see its boundaries expand
# causing it to delete more keys. A snapshot is used to prevent range
# tombstone from being elided when it gets compacted to the bottommost
# level.

define target-file-sizes=(100, 1) snapshots=(1)
L0
  a.RANGEDEL.1:e
L0
  a.SET.2:v
L0
  c.SET.3:v
L2
  d.SET.0:v
----
mem: 1
0.1:
  000005:[a-a]
  000006:[c-c]
0.0:
  000004:[a-e]
2:
  000007:[d-d]

compact a-b
----
1:
  000008:[a-c]
  000009:[c-d]
  000010:[d-e]
2:
  000007:[d-d]

compact d-e
----
1:
  000008:[a-c]
  000009:[c-d]
3:
  000011:[d-e]

get seq=4
c
----
c:v

compact a-b L1
----
1:
  000009:[c-d]
2:
  000008:[a-c]
3:
  000011:[d-e]

get seq=4
c
----
c:v

# A slight variation on the scenario above where a range tombstone is
# expanded past the boundaries of its "atomic compaction unit".

define target-file-sizes=(100, 1) snapshots=(1)
L0
  a.RANGEDEL.1:e
L0
  a.SET.2:v
L0
  c.SET.3:v
L0
  f.SET.4:v
L2
  d.SET.0:v
----
mem: 1
0.1:
  000005:[a-a]
  000006:[c-c]
0.0:
  000004:[a-e]
  000007:[f-f]
2:
  000008:[d-d]

compact a-b
----
0.0:
  000007:[f-f]
1:
  000009:[a-c]
  000010:[c-d]
  000011:[d-e]
2:
  000008:[d-d]

compact d-e
----
0.0:
  000007:[f-f]
1:
  000009:[a-c]
  000010:[c-d]
3:
  000012:[d-e]

get seq=4
c
----
c:v

compact f-f L0
----
1:
  000009:[a-c]
  000010:[c-d]
  000007:[f-f]
3:
  000012:[d-e]

compact a-f L1
----
2:
  000013:[a-c]
  000014:[c-d]
  000015:[f-f]
3:
  000012:[d-e]

get seq=4
c
----
c:v

define
L0
  a.RANGEDEL.3:f
L0
  a.RANGEDEL.4:c
  c.RANGEDEL.4:f
L1
  b.RANGEDEL.2:e
L2
  c.RANGEDEL.1:d
----
mem: 1
0.1:
  000005:[a-f]
0.0:
  000004:[a-f]
1:
  000006:[b-e]
2:
  000007:[c-d]

wait-pending-table-stats
000007
----
num-entries: 1
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 0

wait-pending-table-stats
000006
----
num-entries: 1
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 836

wait-pending-table-stats
000004
----
num-entries: 1
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 1672

wait-pending-table-stats
000005
----
num-entries: 2
num-deletions: 2
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 1672


# Range deletions with varying overlap.
define
L0
  a.SET.4:4
  b.SET.4:4
  d.SET.4:4
  c.RANGEDEL.4:d
L1
  a.SET.3:3
  d.SET.3:3
  b.RANGEDEL.3:d
L2
  d.SET.2:2
  a.RANGEDEL.2:d
L3
  a.SET.1:1
  b.SET.1:1
  c.SET.1:1
  d.SET.1:1
----
mem: 1
0.0:
  000004:[a-d]
1:
  000005:[a-d]
2:
  000006:[a-d]
3:
  000007:[a-d]

wait-pending-table-stats
000007
----
num-entries: 4
num-deletions: 0
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 0

wait-pending-table-stats
000006
----
num-entries: 2
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 787

wait-pending-table-stats
000005
----
num-entries: 3
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 68

wait-pending-table-stats
000004
----
num-entries: 4
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 100

# Multiple Range deletions in a table.
define
L0
  a.RANGEDEL.6:d
  e.RANGEDEL.6:z
L0
  a.RANGEDEL.5:d
L0
  e.RANGEDEL.4:z
L1
  a.SET.2:1
  b.SET.2:1
  c.SET.2:1
L2
  x.SET.1:2
----
mem: 1
0.1:
  000004:[a-z]
0.0:
  000005:[a-d]
  000006:[e-z]
1:
  000007:[a-c]
2:
  000008:[x-x]

wait-pending-table-stats
000005
----
num-entries: 1
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 782

wait-pending-table-stats
000006
----
num-entries: 1
num-deletions: 1
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 771

wait-pending-table-stats
000004
----
num-entries: 2
num-deletions: 2
point-deletions-bytes-estimate: 0
range-deletions-bytes-estimate: 1553