Could Batched Nested Loop improve PostgreSQL like it does for YugabyteDB?
Tags: yugabytedb, distributed, sql, postgres
Published: 2023-12-23 21:48:23

I like the Batched Nested Loop feature in YugabyteDB's execution plans. It has solved many problems by making complex queries, with many joins, scalable without compromising the agility to distribute table rows and index entries transparently. Someone asked me if this feature would be useful for PostgreSQL. To find out, we need to test it.

Essentially, this feature can replace a thousand loops with one. It pushes down the outer loops to the inner loop to reduce the cross-shard calls. The thousand values from the outer table are batched into a single array.

Let's build a minimal example where the outer table has one thousand rows built with VALUES, and we want to fetch the matching rows from a one million table. I'll show what happens with an ARRAY and with a JOIN, in PostgreSQL and YugabyteDB.

## PostgreSQL

I create the following table with one million rows:
```sql
create table t2 ( id bigint, primary key(id));
insert into t2 select generate_series(1,1000000);
vacuum t2;
```

I will query it for 1000 values using a nested loop from `VALUES` and a single scan with `= ANY()`. The purpose is to understand the performance complexity by examining the execution plan with runtime statistics.

As I'm too lazy to type 1000 values, I generate it and `\gexec` it:

```sql
\pset pager off
select
 format('
explain (analyze, buffers)
 select id from t2 
 where t2.id = ANY (''{ %s }''::bigint[]) 
 order by id
',string_agg(n::text,',')) as arr,
 format('
explain (analyze, buffers)
 with t1(id) as (values( %s )) 
 select id from t1 join t2 using(id)
 order by id
',string_agg(n::text,'),(')) as val
from generate_series(1,1000) n;
\gexec
```
I'll show the execution plans with `explain (analyze, buffers)` to see how many pages were read to get those 1000 rows.

### PostgreSQL = ANY ( ARRAY )

Let's start without a join to see how our solution, with an array, accesses the thousand rows in the inner table.

```sql
                                                           QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using t2_pkey on t2  (cost=0.42..3826.50 rows=1000 width=8) (actual time=0.038..0.889 rows=1000 loops=1)
   Index Cond: (id = ANY ('{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999,1000}'::bigint[]))
   Heap Fetches: 0
   Buffers: local hit=3001
 Planning Time: 0.238 ms
 Execution Time: 0.942 ms
(6 rows)
```
This is an `Index Only Scan` because my index covers all columns I need, and with `Heap Fetches: 0` as it was freshly vacuumed. To read 1000 values, it has read 3001 buffers. It is easy to guess that each index lookup had to read the B-Tree root, then one branch and one leaf. There's no scan optimization for multiple points or ranges in PostgreSQL, each lookup is an index access, and I can already guess that it is not faster than 1000 loops.

### PostgreSQL Nested Loop Join

To use a join, I've defined those thousand values as a set of rows with the VALUES constructor.

```sql
                                                           QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=3888.83..3891.33 rows=1000 width=8) (actual time=1.426..1.479 rows=1000 loops=1)
   Sort Key: t2.id
   Sort Method: quicksort  Memory: 25kB
   Buffers: local hit=3001
   ->  Nested Loop  (cost=0.42..3839.00 rows=1000 width=8) (actual time=0.013..1.358 rows=1000 loops=1)
         Buffers: local hit=3001
         ->  Values Scan on "*VALUES*"  (cost=0.00..12.50 rows=1000 width=4) (actual time=0.001..0.163 rows=1000 loops=1)
         ->  Index Only Scan using t2_pkey on t2  (cost=0.42..3.83 rows=1 width=8) (actual time=0.001..0.001 rows=1 loops=1000)
               Index Cond: (id = "*VALUES*".column1)
               Heap Fetches: 0
               Buffers: local hit=3001
 Planning Time: 0.461 ms
 Execution Time: 1.541 ms
(13 rows)
```
With `loops=1000` the performance of the Index Only Scan is exactly the same, reading 3001 pages for 1000 lookups to a 3 levels B-Tree.

An additional `Sort` increases the response time for my `order by`. It was not necessary with the array because the query planner can reorder it but a Nested Loop is ordered by the outer table. There's a solution for that. If I replace `from t1` by `from (select * from t1 order by id) t1` the Nested Loop will be aware of the order and can bypass the `Sort` operation.

## YugabyteDB

To run in in YugabyteDB, I've defined range sharding to get the index ordered like in PostgreSQL: `primary key(id asc)` and I've gathered distributed read/write and LSM-Tree metrics: `explain (analyze, buffers, dist, debug)`.

There's no need to vacuum as there's no bloating, no stale visibility map and no xid wraparound with YugabyteDB.

### YugabyteDB = ANY ( ARRAY )

```sql
 Index Scan using t2_pkey on t2  (cost=0.00..5.36 rows=1 width=8) (actual time=5.187..5.411 rows=1000 loops=1)
   Index Cond: (id = ANY ('{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,97,988,989,990,991,992,993,994,995,996,997,998,999,1000}'::bigint[]))
   Storage Table Read Requests: 1
   Storage Table Read Execution Time: 2.361 ms
   Metric rocksdb_number_db_seek: 1000.000
   Metric rocksdb_number_db_next: 1000.000
   Metric rocksdb_number_db_seek_found: 1000.000
   Metric rocksdb_number_db_next_found: 1000.000
   Metric rocksdb_iter_bytes_read: 82980.000
   Metric docdb_keys_found: 1000.000
 Planning Time: 8.063 ms
 Execution Time: 6.272 ms
 Storage Read Requests: 1
 Storage Read Execution Time: 2.361 ms
 Storage Write Requests: 0.000
 Catalog Read Requests: 4
 Catalog Read Execution Time: 3.153 ms
 Catalog Write Requests: 0.000
 Storage Flush Requests: 0
 Metric rocksdb_number_db_seek: 1000
 Metric rocksdb_number_db_next: 1000
 Metric rocksdb_number_db_seek_found: 1000
 Metric rocksdb_number_db_next_found: 1000
 Metric rocksdb_iter_bytes_read: 82980
 Metric docdb_keys_found: 1000
 Storage Execution Time: 5.514 ms
 Peak Memory Usage: 30 kB
(27 rows)
```

The Index Scan involves searching for 1000 values in the LSM-Tree, which is a RocksDB for each YugabyteDB table or index shard. It is different than B-Tree. One `rocksdb_number_db_seek` goes to the key ( MemTable and Level 0 SST files), and `rocksdb_number_db_next` reads the row. It is worth noting that the 1000 searches are carried out by a single `Read Request`, which is one distributed read. This means that even if the index tablet is located in another zone, the query will still take only a few milliseconds. Unlike PostgreSQL, YugabyteDB can perform an [Index Skip Scan](https://wiki.postgresql.org/wiki/Loose_indexscan) when reading from the LSM-Tree, fetching multiple values in one scan.


### YugabyteDB Nested Loop Join

Given the previous observation, I've replaced `from t1` with `from (select * from t1 order by id) t1` to show that the final `Sort` operation is not needed in this case:

```sql
 Nested Loop  (cost=82.33..208.72 rows=1000 width=8) (actual time=1.547..441.056 rows=1000 loops=1)
   CTE t1
     ->  Values Scan on "*VALUES*"  (cost=0.00..12.50 rows=1000 width=4) (actual time=0.001..0.158 rows=1000 loops=1)
   ->  Sort  (cost=69.83..72.33 rows=1000 width=4) (actual time=0.840..1.443 rows=1000 loops=1)
         Sort Key: t1.id
         Sort Method: quicksort  Memory: 71kB
         ->  CTE Scan on t1  (cost=0.00..20.00 rows=1000 width=4) (actual time=0.004..0.547 rows=1000 loops=1)
   ->  Index Scan using t2_pkey on t2  (cost=0.00..0.11 rows=1 width=8) (actual time=0.422..0.422 rows=1 loops=1000)
         Index Cond: (id = t1.id)
         Storage Table Read Requests: 1
         Storage Table Read Execution Time: 0.377 ms
         Metric rocksdb_block_cache_hit: 3.000
         Metric rocksdb_block_cache_index_hit: 1.000
         Metric rocksdb_block_cache_filter_hit: 1.000
         Metric rocksdb_block_cache_data_hit: 1.000
         Metric rocksdb_block_cache_bytes_read: 117565.000
         Metric rocksdb_number_db_seek: 1.000
         Metric rocksdb_number_db_next: 1.000
         Metric rocksdb_number_db_seek_found: 1.000
         Metric rocksdb_number_db_next_found: 1.000
         Metric rocksdb_iter_bytes_read: 82.980
         Metric rocksdb_block_cache_multi_touch_hit: 3.000
         Metric rocksdb_block_cache_multi_touch_bytes_read: 117565.000
         Metric docdb_keys_found: 1.000
 Planning Time: 0.800 ms
 Execution Time: 442.253 ms
 Storage Read Requests: 1000
 Storage Read Execution Time: 377.414 ms
 Storage Write Requests: 0.000
 Catalog Read Requests: 0
 Catalog Write Requests: 0.000
 Storage Flush Requests: 0
 Metric rocksdb_block_cache_hit: 3000
 Metric rocksdb_block_cache_index_hit: 1000
 Metric rocksdb_block_cache_filter_hit: 1000
 Metric rocksdb_block_cache_data_hit: 1000
 Metric rocksdb_block_cache_bytes_read: 117565000
 Metric rocksdb_number_db_seek: 1000
 Metric rocksdb_number_db_next: 1000
 Metric rocksdb_number_db_seek_found: 1000
 Metric rocksdb_number_db_next_found: 1000
 Metric rocksdb_iter_bytes_read: 82980
 Metric rocksdb_block_cache_multi_touch_hit: 3000
 Metric rocksdb_block_cache_multi_touch_bytes_read: 117565000
 Metric docdb_keys_found: 1000
 Storage Execution Time: 377.414 ms
 Peak Memory Usage: 232 kB
(47 rows)
```
The key distinction is that the 1000 lookups (`rocksdb_number_db_seek: 1000`) in the LSM-Tree were performed via 1000 separate read requests (`Storage Read Requests: 1000`). This approach adds network latency for each iteration, making it non-scalable. Our goal is to optimize the process by batching values and reducing the number of loops required, utilizing the Index Skip Scan mentioned above.

### YB Batched Nested Loop Join

I'm running this in YugabyteDB 2.19 where the Batched Nested Loop is not yet enabled by default. I enabled it y increasing the batch size from 1 to 1024.
```sql
set yb_bnl_batch_size to 1024;
```

Here is the execution plan for the same query:
```sql
                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=144.67..147.17 rows=1000 width=8) (actual time=7.384..7.430 rows=1000 loops=1)
   Sort Key: t2.id
   Sort Method: quicksort  Memory: 71kB
   CTE t1
     ->  Values Scan on "*VALUES*"  (cost=0.00..12.50 rows=1000 width=4) (actual time=0.001..0.153 rows=1000 loops=1)
   ->  YB Batched Nested Loop Join  (cost=69.83..82.34 rows=1000 width=8) (actual time=6.163..7.053 rows=1000 loops=1)
         Join Filter: (t1.id = t2.id)
         ->  Sort  (cost=69.83..72.33 rows=1000 width=4) (actual time=0.861..0.908 rows=1000 loops=1)
               Sort Key: t1.id
               Sort Method: quicksort  Memory: 71kB
               ->  CTE Scan on t1  (cost=0.00..20.00 rows=1000 width=4) (actual time=0.006..0.576 rows=1000 loops=1)
         ->  Index Scan using t2_pkey on t2  (cost=0.00..4.11 rows=1 width=8) (actual time=3.853..4.111 rows=1000 loops=1)
               Index Cond: (id = ANY (ARRAY[(t1.id)::bigint, ($2)::bigint, ($3)::bigint, ..., ($1024)::bigint]))
               Storage Table Read Requests: 1
               Storage Table Read Execution Time: 2.413 ms
               Metric rocksdb_block_cache_hit: 2.000
               Metric rocksdb_block_cache_index_hit: 1.000
               Metric rocksdb_block_cache_data_hit: 1.000
               Metric rocksdb_block_cache_bytes_read: 52088.000
               Metric rocksdb_number_db_seek: 1000.000
               Metric rocksdb_number_db_next: 1000.000
               Metric rocksdb_number_db_seek_found: 1000.000
               Metric rocksdb_number_db_next_found: 1000.000
               Metric rocksdb_iter_bytes_read: 82980.000
               Metric rocksdb_block_cache_multi_touch_hit: 2.000
               Metric rocksdb_block_cache_multi_touch_bytes_read: 52088.000
               Metric docdb_keys_found: 1000.000
 Planning Time: 1.756 ms
 Execution Time: 10.993 ms
 Storage Read Requests: 1
 Storage Read Execution Time: 2.413 ms
 Storage Write Requests: 0.000
 Catalog Read Requests: 0
 Catalog Write Requests: 0.000
 Storage Flush Requests: 0
 Metric rocksdb_block_cache_hit: 2
 Metric rocksdb_block_cache_index_hit: 1
 Metric rocksdb_block_cache_data_hit: 1
 Metric rocksdb_block_cache_bytes_read: 52088
 Metric rocksdb_number_db_seek: 1000
 Metric rocksdb_number_db_next: 1000
 Metric rocksdb_number_db_seek_found: 1000
 Metric rocksdb_number_db_next_found: 1000
 Metric rocksdb_iter_bytes_read: 82980
 Metric rocksdb_block_cache_multi_touch_hit: 2
 Metric rocksdb_block_cache_multi_touch_bytes_read: 52088
 Metric docdb_keys_found: 1000
 Storage Execution Time: 2.413 ms
 Peak Memory Usage: 5714 kB
(49 rows)
```

YugabyteDB replaced 1000 `Index Cond: (id = t1.id)` loops with  with one `Index Cond: (id = ANY (ARRAY[(t1.id)::bigint, ($2)::bigint, ($3)::bigint, ..., ($1024)::bigint]))` loop. The join executes with only one 'Read Request', providing high performance even when distributed.

One potential issue to note is that the batching process does not retain the order of the rows. To address this, a `Sort` operation has been added. However, when dealing with a large amount of data, the execution time of the `Sort` operation can be a concern, especially when using `LIMIT` or `FETCH FIRST ... ROWS`. The non-batched version may lead to better performance. This will be improved soon.

### YugabyteDB Order-Preserving Batched Nested Loop

Batched Nested Loop was disabled by default during the preview phase, but it has been tested extensively by numerous customers and open-source users. It is an improvement over Nested Loop for almost all queries, with the exception of those that use ORDER BY LIMIT as mentioned above. This is because, in such cases, all rows must be sorted before fetching the top-N ones. This has been addressed by issue [#19589](https://github.com/yugabyte/yugabyte-db/issues/19589) by sorting each batch and will be available in the next release.

I'm too impatient to show you the execution plan. I've build YugabyteDB from the source with the commit for [#19589](https://github.com/yugabyte/yugabyte-db/issues/19589) and you can do the same because it is fully Open Source (instructions [here](https://docs.yugabyte.com/preview/contribute/core-database/build-from-src-almalinux/)):

```sql
yugabyte=# select version();
                                                                                         version

--------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------
 PostgreSQL 11.2-YB-2.21.0.0-b0 on x86_64-pc-linux-gnu, compiled by clang version 16.0.6 (https://github.com/yugabyte/llvm-project.git 1e6329f40e5c531c09ade70
15278078682293ebd), 64-bit
(1 row)

yugabyte=# \! curl -s $(hostname):7000 | awk -F">" '/<pre>version/{print $NF}'
version 2.21.0.0 build 376 revision 6aef7ad88c9575c480b13be8f23ecce91bcdd08c build_type RELEASE built at 19 Dec 2023 06:42:35 UTC

yugabyte=# select name, setting from pg_settings where name like '%bnl%';
            name             | setting
-----------------------------+---------
 yb_bnl_batch_size           | 1024
 yb_bnl_enable_hashing       | on
 yb_bnl_optimize_first_batch | on
 yb_prefer_bnl               | on
(4 rows)
```

I created the same table again and ran the same query on it:
```sql
create table t2 ( id bigint, primary key(id asc));
insert into t2 select generate_series(1,1000000);
\pset pager off
select
 format('explain (analyze, buffers, dist, debug) select id from t2 where t2.id = ANY (''{ %s }''::bigint[]) order by id',string_agg(n::text,',')) as arr ,
 format('explain (analyze, buffers, dist, debug) with t1(id) as (values(%s)) select id from (select * from t1 order by id) t1 join t2 using(id) order by id',string_agg(n::text,'),(')) as val
from generate_series(1,1000) n;
\gexec
```

In this version, Batched Nested Loop is enabled by default. Here is the execution plan for the join:
```sql
                                                      QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
 YB Batched Nested Loop Join  (cost=82.33..193.16 rows=1000 width=8) (actual time=8.085..8.158 rows=1000 loops=1)
   Join Filter: (t1.id = t2.id)
   Sort Keys: t2.id
   CTE t1
     ->  Values Scan on "*VALUES*"  (cost=0.00..12.50 rows=1000 width=4) (actual time=0.001..0.107 rows=1000 loops=1)
   ->  Sort  (cost=69.83..72.33 rows=1000 width=4) (actual time=1.071..1.100 rows=1000 loops=1)
         Sort Key: t1.id
         Sort Method: quicksort  Memory: 71kB
         ->  CTE Scan on t1  (cost=0.00..20.00 rows=1000 width=4) (actual time=0.005..0.439 rows=1000 loops=1)
   ->  Index Scan using t2_pkey on t2  (cost=0.00..0.11 rows=1 width=8) (actual time=5.030..5.196 rows=1000 loops=1)
         Index Cond: (id = ANY (ARRAY[(t1.id)::bigint, ($2)::bigint, ($3)::bigint, ..., ($1024)::bigint]))
         Storage Table Read Requests: 1
         Storage Table Read Execution Time: 1.822 ms
         Metric rocksdb_block_cache_hit: 2.000
         Metric rocksdb_block_cache_index_hit: 1.000
         Metric rocksdb_block_cache_data_hit: 1.000
         Metric rocksdb_block_cache_bytes_read: 52088.000
         Metric rocksdb_number_db_seek: 1000.000
         Metric rocksdb_number_db_next: 1000.000
         Metric rocksdb_number_db_seek_found: 1000.000
         Metric rocksdb_number_db_next_found: 1000.000
         Metric rocksdb_iter_bytes_read: 82980.000
         Metric rocksdb_block_cache_multi_touch_hit: 2.000
         Metric rocksdb_block_cache_multi_touch_bytes_read: 52088.000
         Metric docdb_keys_found: 1000.000
         Metric ql_read_latency: sum: 935.000, count: 1.000
 Planning Time: 15.052 ms
 Execution Time: 10.667 ms
 Storage Read Requests: 1
 Storage Read Execution Time: 1.822 ms
 Storage Write Requests: 0
 Catalog Read Requests: 40
 Catalog Read Execution Time: 26.263 ms
 Catalog Write Requests: 0
 Storage Flush Requests: 0
 Metric rocksdb_block_cache_hit: 2
 Metric rocksdb_block_cache_index_hit: 1
 Metric rocksdb_block_cache_data_hit: 1
 Metric rocksdb_block_cache_bytes_read: 52088
 Metric rocksdb_number_db_seek: 1000
 Metric rocksdb_number_db_next: 1000
 Metric rocksdb_number_db_seek_found: 1000
 Metric rocksdb_number_db_next_found: 1000
 Metric rocksdb_iter_bytes_read: 82980
 Metric rocksdb_block_cache_multi_touch_hit: 2
 Metric rocksdb_block_cache_multi_touch_bytes_read: 52088
 Metric docdb_keys_found: 1000
 Metric ql_read_latency: sum: 935, count: 1
 Storage Execution Time: 28.085 ms
 Peak Memory Usage: 5751 kB
(50 rows)
```
The change is that the `Sort Keys: t2.id` has been moved under the `YB Batched Nested Loop Join`. Currently, since I am reading fewer rows than the batch size, there is no difference in the response time. However, with more rows, sorting small batches is quicker and requires less memory. This performance improvement will be more noticeable when a LIMIT is added as it won't have to sort all the rows.

### YugabyteDB High Performance Top-N Join

There's an additional optimization in this latest version, that we have seen with the new `yb_bnl_optimize_first_batch=on` parameter.

I query the Top-42 rows by adding a `fetch first 42 rows` or `limit 42` clause to the `order by`:
```sql
explain (analyze, buffers, dist, debug) with t1(id) as (
values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31),(32),(33),(34),(35),(36),(37),(38),(39),(40),(41),(42),(43),(44),(45),(46),(47),(48),(49),(50),(51),(52),(53),(54),(55),(56),(57),(58),(59),(60),(61),(62),(63),(64),(65),(66),(67),(68),(69),(70),(71),(72),(73),(74),(75),(76),(77),(78),(79),(80),(81),(82),(83),(84),(85),(86),(87),(88),(89),(90),(91),(92),(93),(94),(95),(96),(97),(98),(99),(100),(101),(102),(103),(104),(105),(106),(107),(108),(109),(110),(111),(112),(113),(114),(115),(116),(117),(118),(119),(120),(121),(122),(123),(124),(125),(126),(127),(128),(129),(130),(131),(132),(133),(134),(135),(136),(137),(138),(139),(140),(141),(142),(143),(144),(145),(146),(147),(148),(149),(150),(151),(152),(153),(154),(155),(156),(157),(158),(159),(160),(161),(162),(163),(164),(165),(166),(167),(168),(169),(170),(171),(172),(173),(174),(175),(176),(177),(178),(179),(180),(181),(182),(183),(184),(185),(186),(187),(188),(189),(190),(191),(192),(193),(194),(195),(196),(197),(198),(199),(200),(201),(202),(203),(204),(205),(206),(207),(208),(209),(210),(211),(212),(213),(214),(215),(216),(217),(218),(219),(220),(221),(222),(223),(224),(225),(226),(227),(228),(229),(230),(231),(232),(233),(234),(235),(236),(237),(238),(239),(240),(241),(242),(243),(244),(245),(246),(247),(248),(249),(250),(251),(252),(253),(254),(255),(256),(257),(258),(259),(260),(261),(262),(263),(264),(265),(266),(267),(268),(269),(270),(271),(272),(273),(274),(275),(276),(277),(278),(279),(280),(281),(282),(283),(284),(285),(286),(287),(288),(289),(290),(291),(292),(293),(294),(295),(296),(297),(298),(299),(300),(301),(302),(303),(304),(305),(306),(307),(308),(309),(310),(311),(312),(313),(314),(315),(316),(317),(318),(319),(320),(321),(322),(323),(324),(325),(326),(327),(328),(329),(330),(331),(332),(333),(334),(335),(336),(337),(338),(339),(340),(341),(342),(343),(344),(345),(346),(347),(348),(349),(350),(351),(352),(353),(354),(355),(356),(357),(358),(359),(360),(361),(362),(363),(364),(365),(366),(367),(368),(369),(370),(371),(372),(373),(374),(375),(376),(377),(378),(379),(380),(381),(382),(383),(384),(385),(386),(387),(388),(389),(390),(391),(392),(393),(394),(395),(396),(397),(398),(399),(400),(401),(402),(403),(404),(405),(406),(407),(408),(409),(410),(411),(412),(413),(414),(415),(416),(417),(418),(419),(420),(421),(422),(423),(424),(425),(426),(427),(428),(429),(430),(431),(432),(433),(434),(435),(436),(437),(438),(439),(440),(441),(442),(443),(444),(445),(446),(447),(448),(449),(450),(451),(452),(453),(454),(455),(456),(457),(458),(459),(460),(461),(462),(463),(464),(465),(466),(467),(468),(469),(470),(471),(472),(473),(474),(475),(476),(477),(478),(479),(480),(481),(482),(483),(484),(485),(486),(487),(488),(489),(490),(491),(492),(493),(494),(495),(496),(497),(498),(499),(500),(501),(502),(503),(504),(505),(506),(507),(508),(509),(510),(511),(512),(513),(514),(515),(516),(517),(518),(519),(520),(521),(522),(523),(524),(525),(526),(527),(528),(529),(530),(531),(532),(533),(534),(535),(536),(537),(538),(539),(540),(541),(542),(543),(544),(545),(546),(547),(548),(549),(550),(551),(552),(553),(554),(555),(556),(557),(558),(559),(560),(561),(562),(563),(564),(565),(566),(567),(568),(569),(570),(571),(572),(573),(574),(575),(576),(577),(578),(579),(580),(581),(582),(583),(584),(585),(586),(587),(588),(589),(590),(591),(592),(593),(594),(595),(596),(597),(598),(599),(600),(601),(602),(603),(604),(605),(606),(607),(608),(609),(610),(611),(612),(613),(614),(615),(616),(617),(618),(619),(620),(621),(622),(623),(624),(625),(626),(627),(628),(629),(630),(631),(632),(633),(634),(635),(636),(637),(638),(639),(640),(641),(642),(643),(644),(645),(646),(647),(648),(649),(650),(651),(652),(653),(654),(655),(656),(657),(658),(659),(660),(661),(662),(663),(664),(665),(666),(667),(668),(669),(670),(671),(672),(673),(674),(675),(676),(677),(678),(679),(680),(681),(682),(683),(684),(685),(686),(687),(688),(689),(690),(691),(692),(693),(694),(695),(696),(697),(698),(699),(700),(701),(702),(703),(704),(705),(706),(707),(708),(709),(710),(711),(712),(713),(714),(715),(716),(717),(718),(719),(720),(721),(722),(723),(724),(725),(726),(727),(728),(729),(730),(731),(732),(733),(734),(735),(736),(737),(738),(739),(740),(741),(742),(743),(744),(745),(746),(747),(748),(749),(750),(751),(752),(753),(754),(755),(756),(757),(758),(759),(760),(761),(762),(763),(764),(765),(766),(767),(768),(769),(770),(771),(772),(773),(774),(775),(776),(777),(778),(779),(780),(781),(782),(783),(784),(785),(786),(787),(788),(789),(790),(791),(792),(793),(794),(795),(796),(797),(798),(799),(800),(801),(802),(803),(804),(805),(806),(807),(808),(809),(810),(811),(812),(813),(814),(815),(816),(817),(818),(819),(820),(821),(822),(823),(824),(825),(826),(827),(828),(829),(830),(831),(832),(833),(834),(835),(836),(837),(838),(839),(840),(841),(842),(843),(844),(845),(846),(847),(848),(849),(850),(851),(852),(853),(854),(855),(856),(857),(858),(859),(860),(861),(862),(863),(864),(865),(866),(867),(868),(869),(870),(871),(872),(873),(874),(875),(876),(877),(878),(879),(880),(881),(882),(883),(884),(885),(886),(887),(888),(889),(890),(891),(892),(893),(894),(895),(896),(897),(898),(899),(900),(901),(902),(903),(904),(905),(906),(907),(908),(909),(910),(911),(912),(913),(914),(915),(916),(917),(918),(919),(920),(921),(922),(923),(924),(925),(926),(927),(928),(929),(930),(931),(932),(933),(934),(935),(936),(937),(938),(939),(940),(941),(942),(943),(944),(945),(946),(947),(948),(949),(950),(951),(952),(953),(954),(955),(956),(957),(958),(959),(960),(961),(962),(963),(964),(965),(966),(967),(968),(969),(970),(971),(972),(973),(974),(975),(976),(977),(978),(979),(980),(981),(982),(983),(984),(985),(986),(987),(988),(989),(990),(991),(992),(993),(994),(995),(996),(997),(998),(999),(1000)
) select id 
 from (select * from t1 order by id) t1
 join t2 using(id) order by id fetch first 42 rows only
;
```
Here is the execution plan:
```sql
                                                       QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=82.33..86.98 rows=42 width=8) (actual time=3.619..3.634 rows=42 loops=1)
   CTE t1
     ->  Values Scan on "*VALUES*"  (cost=0.00..12.50 rows=1000 width=4) (actual time=0.001..0.109 rows=1000 loops=1)
   ->  YB Batched Nested Loop Join  (cost=69.83..180.66 rows=1000 width=8) (actual time=3.617..3.620 rows=42 loops=1)
         Join Filter: (t1.id = t2.id)
         Sort Keys: t2.id
         ->  Sort  (cost=69.83..72.33 rows=1000 width=4) (actual time=0.695..0.697 rows=42 loops=1)
               Sort Key: t1.id
               Sort Method: quicksort  Memory: 71kB
               ->  CTE Scan on t1  (cost=0.00..20.00 rows=1000 width=4) (actual time=0.006..0.427 rows=1000 loops=1)
         ->  Index Scan using t2_pkey on t2  (cost=0.00..0.11 rows=1 width=8) (actual time=0.978..0.991 rows=42 loops=1)
               Index Cond: (id = ANY (ARRAY[(t1.id)::bigint, ($2)::bigint, ($3)::bigint, ..., ($1024)::bigint]))
               Storage Table Read Requests: 1
               Storage Table Read Execution Time: 0.698 ms
               Metric rocksdb_block_cache_hit: 2.000
               Metric rocksdb_block_cache_index_hit: 1.000
               Metric rocksdb_block_cache_data_hit: 1.000
               Metric rocksdb_block_cache_bytes_read: 52088.000
               Metric rocksdb_number_db_seek: 42.000
               Metric rocksdb_number_db_next: 42.000
               Metric rocksdb_number_db_seek_found: 42.000
               Metric rocksdb_number_db_next_found: 42.000
               Metric rocksdb_iter_bytes_read: 3358.000
               Metric rocksdb_block_cache_multi_touch_hit: 2.000
               Metric rocksdb_block_cache_multi_touch_bytes_read: 52088.000
               Metric docdb_keys_found: 42.000
               Metric ql_read_latency: sum: 140.000, count: 1.000
 Planning Time: 1.215 ms
 Execution Time: 4.370 ms
```
Not only the `Sort` operation is restricted to the batch size, but the LIMIT has been pushed down, resulting in the first batch only reading `rows=42`. This query's performance is optimal, with only one read request and one seek per row to output. 

YugabyteDB enables scalable distributed joins, which is an advantage over sharded databases like Citus or Aurora Limitless that require co-locating joined shards.

## Would it improve PostgreSQL?

Batching the nested loop join has a significant advantage in YugabyteDB as it reduces the number of remote calls, making joins scalable.

We attempted to simulate an array parameter in PostgreSQL, but it didn't result in any performance improvements. This is because PostgreSQL doesn't support Index Skip Scan, which means that every index lookup, whether from an outer table or an inner array, takes the same amount of time. 

Although this approach may be more efficient if Index Skip Scan is implemented in a future version, the benefits will be minimal. It can help avoid the reading of B-Tree root and branches, but most of the time, they are shared buffer hits in a monolithic database, which is already fast.

Batching can be a useful strategy for optimizing PostgreSQL Index Scan if the array is sorted based on the CTID - the physical location of rows in heap tables. This approach can enhance the table access through the caches, particularly when the index has a poor correlation factor. Oracle has `TABLE ACCESS BY INDEX ROWID BATCHED` to accomplish this, but this does not have all the advantages because it will not preserve the row ordering from the outer table, similar to PostgreSQL Bitmap Heap Scan.

---

The **YugabyteDB Batched Nested Loop** is an excellent example of the benefits of its innovative architecture. It uses a **fork of PostgreSQL** to offer comprehensive SQL features, which it inherits from PostgreSQL's maturity. However, unlike an extension, it is not restricted and in terms of performance it can provide **Distributed SQL scalability**, including **joins** and **pagination**.