[DocDB] YBOperation.partition_key encoding should respect null value

[arybochkin]

Jira Link: [DB-363](https://yugabyte.atlassian.net/browse/DB-363)

Description

Let's assume the following example

# create table test1(id int primary key, name text);
# create unique index idx1 on test1(name ASC) split at values(('p'));
# insert into test1 values(3, 'p');

and encoded partition bound looks like 5370000021 in hex

In accordance with documentation column ybuniqueidxkeysuffix may be of kNullLow, kNullHigh or base table ctid values. Hence the following possible YBOperation.partition_key should be concerned as correctly encoded values (in hex):

537000002421 > 5370000021
537000007C21 > 5370000021
537000005347C0C4488000010001022121000021> 5370000021

In all of these cases the write operation will be forwarded to a correct tablet as all possible values for the first byte are greater than the encoded value of kGroupEnd == 0x21.
But as of now, first and second options are encoded with 537000000021 < 5370000021. Mainly, this is happening because QLValuePB::VALUE_NOT_SET is treated as kLowest for a YBOperation.partition_key, but should not. There is a stack of calls that leads to the inconsistency:
GetRangeComponents()
GetRangePartitionKey()
InitWritePartitionKey()

The fact the YBOperation.partition_key has incorrect format is also confirmed by a manual decoding (via unit test), the following error appears:
Error when decoding range components of a document key: Expected a primitive value type, got kLowest.

Note. Refer to KeyEntryValue::NullValue() and PostgreSQL documentation for details on how null should be encoded. By default NULL LAST approach is used or ASC ordering and NULL FIRST for DESC ordering.

Step to reproduce the issue:

1. Create a cluster with enable_automatic_tablet_splitting=true:

./bin/yb-ctl create --master_flags="enable_automatic_tablet_splitting=true,tablet_split_low_phase_shard_count_per_node=16,tablet_split_low_phase_size_threshold_bytes=13421" --tserver_flags="yb_num_shards_per_tserver=1"

2. Create a table and a unique index

# create table test1(id int primary key, name text);
# create unique index idx1 on test1(name ASC) split at values(('p'));

Tablets info after statements have been executed:

yugabyte        idx1       000033e1000030008000000000004005        d75c1be78e94456d9803758d6650a897        range: [<start>, DocKey([], ["p"]))
yugabyte        idx1       000033e1000030008000000000004005        b5531d9aa54a45fb821fcf2baca3f268        range: [DocKey([], ["p"]), <end>)

3. Insert a row with a value that matches partition bounds

# insert into test1 values(3, 'p');

YBOperation is forwarded to the first tablet d75c1be78e94456d9803758d6650a897 as YBOperation.partition_key is less than the second partition lower bound: 537000000021 < 5370000021. But the operation should have been forwarded to the second tablet in accordance with range bounds. Tablets dump confirms the inserted row is persisted in the first tablet (with respect to DocDB format):

tablet-d75c1be78e94456d9803758d6650a897 in readable format:
SubDocKey(DocKey([], ["p", null]), [SystemColumnId(0); HT{ physical: 1649185585666746 }]) -> null; intent doc ht: HT{ physical: 1649185585665110 }
SubDocKey(DocKey([], ["p", null]), [ColumnId(12); HT{ physical: 1649185585666746 w: 1 }]) -> "G\xfc\xa0H\x80\x00\x00\x03!!"; intent doc ht: HT{ physical: 1649185585665110 w: 1 }

Data Block # 1 @ 0051
--------------------------------------
  HEX    5370000024214A80238001785106292545804A: 238001785106292BA9804A24
  ASCII  S p : # Ä  x Q  ) + © Ä J $ 
  ------
  HEX    5370000024214B8C238001785106292545803FAB: 238001785106292BA9803FAB5347FCA048800000032121
  ASCII  S p : # Ä  x Q  ) + © Ä ? ´ S G ¸ † H Ä 
  ------

tablet-b5531d9aa54a45fb821fcf2baca3f268
<empty>

[arybochkin]

Another example.

1. Create a cluster

./bin/yb-ctl create --master_flags="enable_automatic_tablet_splitting=false"

2 Create a table and a unique index

# create table employees(id int primary key, name text, description text);
# create unique index idx1 on employees(description ASC);

Tablet and tablets info after (1) and (2) have been executed:

yugabyte        test1   000033e1000030008000000000004000        9cbdf6c37ea04fcda1f588e6942de292        hash_split: [0x0000, 0x7FFF)
yugabyte        test1   000033e1000030008000000000004000        5de68de4ae5d4a2897141761e40bc689        hash_split: [0x7FFF, 0xFFFF)
yugabyte        idx1    000033e1000030008000000000004001        4b9381341ce74522832665cf69e11a90        range: [<start>, <end>)

3. Download collect_insert_data.txt and rename to collect_insert_data.py
4. Modify the collect_insert_data.py in order it created a sql script with for insertion first 10 rows only, and execute the script
   python collect_insert_data.py
5. Execute sql script

./bin/ysqlsh -f sql_data.sql

6. Insert a series of 4 rows with null values

# insert into employees values(11, 'new_name', null);
# insert into employees values(12, 'new_name', null);
# insert into employees values(13, 'new_name', null);
# insert into employees values(14, 'new_name', null);

7. Execute select count for different cases

# select count(*) from employees;
 count 
-------
    14
(1 row)

# select count(*) from employees where description is null;
 count 
-------
     4
(1 row)

8. Flush and dump the tablet

./yb-ts-cli flush_tablet 4b9381341ce74522832665cf69e11a90
./sst_dump --file=tablet-4b9381341ce74522832665cf69e11a90/ --command=scan --output_format=decoded_regulardb

Shortened dump:

Process tablet-4b9381341ce74522832665cf69e11a90/000010.sst
Sst file format: block-based
SubDocKey(DocKey([], ["Canal building…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["Canal building…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["Engineering has existed…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["Engineering has existed…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["In this context…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["In this context…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["John Smeaton was…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["John Smeaton was…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["Later, as the design…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["Later, as the design…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["Similarly, in addition…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["Similarly, in addition…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["The science of classical…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["The science of classical…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["The term engineering…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["The term engineering…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["The word engine itself…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["The word engine itself…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], ["With the rise of…", null]), [SystemColumnId(0)...])
SubDocKey(DocKey([], ["With the rise of…", null]), [ColumnId(12)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0x1c99…)…, [SystemColumnId(0)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0x1c99…)…, [ColumnId(12)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0x37f1…)…, [SystemColumnId(0)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0x37f1…)…, [ColumnId(12)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0x41ca…)…, [SystemColumnId(0)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0x41ca…)…, [ColumnId(12)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0xcd71…)…, [SystemColumnId(0)...])
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0xcd71…)…, [ColumnId(12)...])

Last eight records in hexadecimal format:

7C53471C99...0000214A80...
7C53471C99...0000214B8C...
7C534737F1...0000214A80...
7C534737F1...0000214B8C...
7C534741CA...0000214A80...
7C534741CA...0000214B8C...
7C5347CD71...0000214A80...
7C5347CD71...0000214B8C...

Please mention how null is persisted on disk – it is 0x7C despite the fact the index is declared as (description ASC), NULL LAST approach is used for null values for regular columns, refer to KeyEntryValue::NullValue() and PostgreSQL documentation

9. Execute manual tablet splitting and wait until two new tablets appear

./yb-admin split_tablet \
-master_addresses localhost:7100 4b9381341ce74522832665cf69e11a90

Index tablets info after splitting has been executed:

yugabyte        idx1       000033e1000030008000000000004005        d67753006820420994182f684bb11ff6
range: [<start>, DocKey([], ["Similarly, in addition…, null]))
yugabyte        idx1       000033e1000030008000000000004005        299f23ab9a4f4e61bcdbe07722765d50
range: [DocKey([], ["Similarly, in addition…, null]), <end>)

Tablet partition boundary in hex: 5353696D696C61726C792C20…7300002421

Table idx1: table_partition_list: { version: 0 keys: ["", "SSimilarly...\x00\x00$!"] }
Note: DocKey([], ["Similarly, in addition…, null]) == "SSimilarly, in addition\x00\x00$!" == 5353696D696C61726C792C20696E206164646974696F6E...0000242116

Content of tablets is looking as expected with respect to split key (matches partitions bound, see above):

tablet-d67753006820420994182f684bb11ff6:
SubDocKey(DocKey([], ["Canal building…", null]), [SystemColumnId(0)...])
...
SubDocKey(DocKey([], ["Later, as the design…", null]), [ColumnId(12)...])

tablet-299f23ab9a4f4e61bcdbe07722765d50:
SubDocKey(DocKey([], ["Similarly, in addition…", null]), [SystemColumnId(0)...])
...
SubDocKey(DocKey([], [null, EncodedSubDocKey(DocKey(0xcd71…)…, [ColumnId(12)...])

10. Insert one more row with null value

# insert into employees values(15, 'new_name', null);

The rows count gives the following results:

# select count(*) from employees
 count 
-------
    15
(1 row)

# SET enable_indexscan = off;
# select count(*) from employees where description is null
 count 
-------
     5
(1 row)

# SET enable_indexscan = on;
# select count(*) from employees where description is null
 count 
-------
     4
(1 row)

But it is expected to have 5 for last case as well. This is happening due to YBOperation is forwarded to a wrong tablet due to YBOperation.partition_key contains incorrectly encoded null value == 0x00, but should be 0x7C for this case.

[arybochkin]

keeping opened to not forget to backport after version mismatch issue (#13168) is fixed.

[arybochkin]

Backported to 2.14, hence closing.