我們一直在努力縮小 Postgres 和我們的 Postgres 相容分散式資料庫 YugabyteDB 之間的效能差距。我們希望確保用戶在使用 Yugabyte 時獲得最佳體驗，讓他們能夠使用現有的 Postgres 應用程式並在 YugabyteDB 上運行它們而無需進行任何更改。請在我們最近的部落格中了解更多。
這項工作的關鍵部分是提供對位圖掃描的支持，這是一種結合了多個索引的掃描類型。如果沒有點陣圖掃描，則具有 OR 子句的查詢需要重寫以使用 UNION（這並不總是可行），或者它們將執行全表掃描，
這會增加延遲並降低吞吐量。
幾乎每個應用程式都有一個可以從點陣圖掃描中受益的查詢，因此它是一個重要的功能。我們決定調整點陣圖掃描以在分散式 SQL 環境中運作。
儘管 YugabyteDB 是從 Postgres 程式碼庫分叉出來的，但它不能直接使用 Postgres 點陣圖掃描。我們的儲存層完全不同，這改變了點陣圖掃 阿曼 電話號碼庫 描所需的底層資料結構。 Postgres 點陣圖掃描是基於區塊和頁面，這些概念不能完全對應到我們基於 LSM 的儲存。在分散式資料庫中，需要考慮更多的網路躍點－這為將現有 YugabyteDB 最佳化應用到位圖掃描中的新區域提供了可能性，但也需要與 PostgreSQL 不同的查詢計畫。
點陣圖掃描的實作非常有趣。以下是我的一些亮點：
儘管點陣圖掃描仍在進行中，但它們已經幫助多個客戶完成了測試並遷移到 YugabyteDB，從而避免了重寫查詢的需要。
點陣圖掃描可以提供無限的效能改進！運行時間可以從 O(n) 減少到 O(log(n))。
由於 YugabyteDB 是分散式的，因此我們可以進行獨特的效能改進。遠端過濾器和下推使我們能夠在某些場景中超越 Postgres！
在這篇部落格中，我討論：
點陣圖掃描的高階策略
Postgres如何實現點陣圖掃描
我們如何調整位圖掃描以適用於 YugabyteDB
YugabyteDB 點陣圖掃描超越普通 Postgres 的領域
什麼是點陣圖掃描？
在 PostgreSQL 中，典型的索引掃描首先存取索引以尋找滿足搜尋條件的行 ID（稱為元組 ID 或 TID）。然後掃描立即轉到主表以獲取該行。它對每個行 ID 重複此操作，滿足搜尋條件。
點陣圖掃描透過建立所有行 ID 的位圖（有序集）然後一次性迭代主表，顯著減少了對主表的隨機查找次數。點陣圖掃描還具有 BitmapAnd 和 BitmapOr 節點，允許行 ID 的多個位圖（稱為 TIDBitmap）彼此相交或併集。
看一下下面的一個簡單範例，以了解其在實踐中的工作原理。我們將看一個列出幾部電影的範例，其中包含電影的評級索引和導演的索引。
範例電影列表
首先，我們執行以下查詢作為點陣圖掃描：
從評分 = 8.0的電影中選擇*或導演喜歡“george%” ；
規劃者確定可以透過評級指數有效地回答評級條件，並透過導演指數來確定導演條件。因此，會向每個索引發送一個請求，以傳回與條件相符的行 ID。
檢索列表
檢索到的行 ID 被插入到每個索引的點陣圖集中。
點陣圖集
由於這兩個條件透過 OR 子句連接，因此我們將兩個位圖集合併以獲得一個最終位圖集。
點陣圖比較和組合
最後，該集合用於從主表中尋找行。
主表查找
點陣圖掃描可讓我們組合多 turbo shopify 主題：值得它的價格嗎？ 個索引，為 OR 或 AND 查詢提供高效率的執行計劃。
讓我們使用 YugabyteDB 實例來實際看看這個範例。
正如您在本文中看到的，YugabyteDB 重複使用了 Postgres 的點陣圖掃描，並在儲存層級進行了所需的修改。首先，下面的程式碼片段會建立一個電影表，使用該generate_series函數插入 100 萬個隨機記錄，並建立幾個二級索引。
建立電影表（名稱文字、發布日期、類型文字、評分浮動、導演文字）；
插入電影選擇
點陣圖掃描如何在 Postgres 上運作？現在我們已經很好地了解點陣圖掃描是什麼以及它們在實踐中如何運作，讓我們探索 Postgres 中實現的內部原理。
點陣圖掃描計畫節點
上面的每個計劃都是計劃節點的組合。 Postgres 點陣圖掃描是 4 個不同計劃節點的組合：
1 位元圖堆掃描（相當於 Yugabyte 上的 YB 位元圖表掃描，此計劃節點使用 TIDBitmap，使用它從主表請求行，並應用任何剩餘的過濾器）。
0+ BitmapOr（此計劃節點將多個位圖相互合併並產生一個 TIDBitmap）
0+ BitmapAnd（該計劃節點將多個 TIDBitmap 彼此相交並產生一個 TIDBitmap）
1+ 位元圖索引掃描（此計劃節點從索引收集元組 ID 並產生 TIDBitmap）
BitmapOr 或 BitmapAnd 節點可以有任意數量的 Bitmap Index Scan 節點、BitmapOr 節點或 BitmapAnd 節點作為子節點。這些 台灣數據 節點中的每一個都會建立一個 TIDBitmap 來傳遞給其父節點。
TIDBitmap 的完整定義可以在這裡找到。
Postgres 描述：
點陣圖資料結構本質上與點陣圖集類似，但特別適合儲存元組標識符 (TID) 或項目指標集。特別地，滿足將ItemPointer劃分為BlockNumber和OffsetNumber。
ItemPointer 是這裡的關鍵部分。在 Postgres 中，TID 是一個 ItemPointer，由區塊號碼和偏移量組成。塊標識頁面，
偏移量標識元組位於頁面上的位置。
本文介紹中的圖像有些簡化。 Postgres 能夠識別頁面內的特定偏移量，因此無需讀取額外的資料。
TIDBitmap 是PageTableEntries 的雜湊表。每個 PageTableEntry 代表一個區塊，並包含一組偏移量的點陣圖。它是一種非常節省空間的資料結構，並且並集和交集運算可以輕鬆地使用此資料結構。
例如，假設我們正在對 movie_ rating_idx 進行點陣圖掃描。我們已經找到了 ItemPointer(13, 4)、ItemPointer(73, 17) 和 ItemPointer(73, 96)。
TID點陣圖
然後我們在區塊 13 偏移量 0 中找到另一個符合搜尋條件的記錄。
插入項目點 13-0
然後我們在區塊 39 偏移 63 中找到另一個滿足搜尋條件的記錄。
插入項目點 39-63
當我們的哈希表填滿時會發生什麼？
有時，位圖堆掃描節點可能有一行輸出：Heap Blocks: exact=xxx lossy=yyyy。當精確的 PageTableEntries 太多時，就會發生這種情況，因此透過將它們組合成有損條目來節省一些記憶體。讓我們具體看看它是如何運作的。考慮一個已經滿的 TIDBitmap：
TIDBitmap 超出工作內存
在上面的 TIDBitmap 中插入 ItemPointer(46, 17) 之前，我們需要清理一些空間！
我們將使用 50 個區塊的區塊大小，並迭代映射。如果我們找到頁面區塊內的任何確切區塊，我們將建立一個代表頁面區塊的新有損區塊。在上面的範例中，區塊 13 和區塊 39 都適合 0-50 區塊，因此我們將它們組合成一個有損條目。
以前，映射的條目表示精確的條目，指定頁面和頁面內的偏移。現在，Postgres 將重新調整條目的用途以指示有損條目。區塊號將代表區塊的第一頁，偏移量現在將標識該範圍內的頁。我們的區塊覆蓋頁 0-50，因此該條目中的區塊編號為 0。 其中包含條目的頁為 13 和 39，因此我們將它們標記為偏移量。
我們仍然可以插入到遺失的 TIDBitmap 中。如果要將新條目插入到有損的PageTableEntry中，我們將只能記錄頁碼，並且偏移量資訊將被刪除。
插入一個 ItemPointer(46, 17)
點陣圖堆掃描
一旦建立了最終的 TIDBitmap，所有位圖索引掃描、BitmapOrs 和 BitmapAnds 都已被處理。最後一步是點陣圖堆掃描，其中 Postgres 從主表收集行並應用任何剩餘的過濾器。
由於 TIDBitmap 按排序順序保存所有 TID，因此它是從主表檢索行和頁的非常有效的機制。它從不訪問不需要的頁面，並且只訪問每個頁面一次。
規劃點陣圖掃描
如果規劃器估計條目數將超出 work_mem 的容納範圍，則規劃器會猜測 PageTableEntries 中將會有損失的部分。它估計所獲得的元組數量為(selectivity * fraction_exact_pages * n_tuples) + (fraction_lossy_pages * n_tuples)。這意味著我們將僅選擇與確切頁面中的條件相符的元組，但我們將從每個有損頁面中獲取所有元組。
如果需要的元組較少，則將獲取較少的頁面，因此訪問成本與隨機訪問成本相似。隨著獲取的頁面數量增加，訪問成本接近順序成本。
這解釋了 Postgres 上的一個有趣模式，其中只有一個條件的查詢可能會使用點陣圖索引掃描，因為點陣圖掃描的幾乎順序存取模式是有益的。如果查詢選擇的行較少，則更有可能選擇索引掃描。如果選擇更多行，則更有可能選擇順序掃描。介於兩者之間，它將使用點陣圖掃描。這是由於 Postgres 的磁碟存取成本模型所造成的。
需要更改哪些內容才能支援分散式 PostgreSQL 上的點陣圖掃描？
由於 YugabyteDB 是從 Postgres 分叉出來的，因此我們的程式碼庫中已經有了點陣圖掃描的框架。 YugabyteDB 中的臨時表被實作為普通 Postgres 表，因此位圖掃描仍然適用於 YugabyteDB 中的臨時表。
但是，我們如何支援分散式表的位圖掃描？
資料結構
YugabyteDB 上位圖掃描的最大障礙是我們的元組 ID 不同。 (page, offset) TID 適用於單節點資料庫，但不適用於分散式系統。
在 YugabyteDB 中，元組 ID 稱為 YBCTID。有關 YBCTID 的更多資訊可在 docs 中找到，但在 Postgres 層上，它表示為二進位字串，沒有頁面或偏移量的等效概念。由於從 DocDB 接收到的 YBCTID 對 Postgres 後端沒有任何意義，因此我們無法像 Postgres 儲存其 TID 那樣有效地儲存它，並且我們無法順序掃描主表。
我們需要一種具有快速插入、快速並集和交集的新資料結構。資料結構不需要提供有序迭代，因為順序在本地沒有意義。
YugabyteDB 的 YbTIDBitmap 使用標準無序集。並集和交集以線性時間運行，並且插入是恆定的。由於這是封裝在 Postgres 層中的 YbTIDBitmap 物件中，因此呼叫者不需要了解實作之間的差異，且 Postgres / YugabyteDB 的大部分程式碼可以保持不變。
下圖是 YugabyteDB 點陣圖掃描的整體流程：
YugabyteDB 位圖掃描的整體流程
點陣圖索引掃描向儲存層發送 ybctid 請求，並將這些請求插入到透過計劃樹向上傳遞的查詢層上的 YbTIDBitmap 中。
超出work_mem
當點陣圖超過work_mem時，Postgres會以相對有效的方式處理它，透過選擇性地識別需要完全取得的頁面。
由於資料結構有很大不同，YugabyteDB處理臃腫位圖的方法也需要不同。這是由#20576追蹤的，但同時，它只是丟棄位圖並回退到使用遠端過濾器的順序掃描。
我們如何才能讓 YugabyteDB 上的點陣圖掃描變得更好？
不需要太多就能讓點陣圖掃描的基本功能正常運作。然而，我們還可以做更多的事情來利用我們在 YugabyteDB 中所做的其他增強功能，並使分散式位圖掃描真正發揮作用。