[Intum Dev](https://intum.dev.md) / [Bazy Danych](https://intum.dev/bazy-danych.md)

# [Optymalizacja Top-K w PostgreSQL - podejście ParadeDB](https://intum.dev/bazy-danych/optymalizacja-top-k-w-postgresql-podejscie-paradedb.md)

## Problem

PostgreSQL ma trudności z efektywnym zwracaniem K najlepszych wierszy, szczególnie gdy zapytania łączą:
- Filtry nie będące częścią indeksu
- Wyszukiwanie pełnotekstowe (full text search)
- Sortowanie po relevance score

B-tree wymusza z góry ustalenie kształtu zapytania - potrzebujesz wielu dedykowanych indeksów, co powoduje bloat storage i spowolnienie zapisów.

**Uwaga przy indeksach złożonych:** indeks np. `(severity, timestamp)` nie pozwala na przechodzenie przez timestampy w porządku malejącym globalnie - tylko w obrębie każdego poziomu severity. Warto o tym pamiętać przy projektowaniu. Możliwe obejście dla prostszych przypadków: indeks częściowy na kolumnie sortowania z warunkiem WHERE (np. `WHERE severity < 3`).

PostgreSQL 18 wprowadza skip scan, ale działa on wyłącznie dla dopasowania równości - nie pomoże przy złożonych zapytaniach Top-K.

## Podejście ParadeDB

ParadeDB zastosowało podejście inspirowane wyszukiwarkami (Lucene/Tantivy). Integruje Tantivy (bibliotekę podobną do Lucene) bezpośrednio wewnątrz PostgreSQL jako extension - dzięki temu można korzystać z mocy search engine bez opuszczania ekosystemu Postgres.

### Inverted Index + Columnar Arrays
- Inverted index mapuje termy na posting listy (uporządkowane doc ID)
- Columnar layout przechowuje pola w kompaktowych tablicach z O(1) dostępem
- Eliminuje kosztowne lookupy w głównej tabeli

Warto jednak pamiętać, że columnar storage wprowadza złożoność operacyjną i ogranicza funkcje transakcyjne - nie zawsze jest to właściwy trade-off.

### Compound Index
Wszystkie pola searchable, filterable i sortable w jednym indeksie z wewnętrznym u32 document ID:
- Intersectowanie u32 streams
- SIMD-based batch comparisons

### Block WAND
Optymalizacja dla BM25 scoring - pomija całe bloki dokumentów, jeśli ich max_score nie może wejść do Top-K heapu.

### Tantivy v0.21.0
Zmiana w doc ID iterators - zamiast `seek` na następny match, umożliwia tańszy membership check dla konkretnego doc ID.

## Benchmarki

| Scenariusz | PostgreSQL | ParadeDB | Poprawa |
|---|---|---|---|
| Top 10 z filtrem text search | 33-37 sec | 0.3 sec | ~100x |
| Top K (severity + timestamp) | - | 90 -> 70 ms | 30% |

## Alternatywy - rozszerzenia PostgreSQL

| Rozszerzenie | Typ | Full Text Search | Top-K | Opis |
|---|---|---|---|---|
| **Natywny PG** (GIN + tsvector) | wbudowany | tak (podstawowy) | wolny przy złożonych filtrach | Nie wymaga niczego dodatkowego. Wystarczający dla prostych przypadków, słaby przy dynamicznych filtrach + sortowaniu |
| **pg_trgm** | wbudowany | trigramy (LIKE/similarity) | nie | Dobre do fuzzy match i autocomplete, nie do pełnego FTS z rankingiem |
| **btree_gin** | wbudowany | nie | nie | Łączy kolumny btree z GIN w jednym indeksie. Pomaga przy filtrach, ale nie rozwiązuje problemu sortowania Top-K |
| **ParadeDB** | extension (Rust) | tak (BM25, Tantivy) | tak (Block WAND) | Pełny search engine wewnątrz PG. Najlepsza wydajność Top-K, ale dodatkowa złożoność operacyjna |
| **ZomboDB** | extension (Rust) | tak (przez Elasticsearch) | tak | Most PG <-> Elasticsearch. Potężne, ale wymaga utrzymywania osobnego klastra ES |
| **pgvector** | extension (C) | nie (wyszukiwanie wektorowe) | tak (ANN/HNSW) | Do wyszukiwania semantycznego (embeddingi), nie klasycznego FTS. Świetne do RAG/AI |
| **TimescaleDB** | extension (C) | nie | tak (time-series) | Columnar compression + chunk pruning. Idealne dla danych czasowych, nie do ogólnego FTS |
| **Elasticsearch/OpenSearch** | zewnętrzny serwis | tak | tak | Osobny klaster, pełna moc search engine. Wymaga synchronizacji danych z PG |

### Kiedy co wybrać

- **Prosty FTS bez dynamicznych filtrów** - natywny GIN + tsvector wystarczy
- **Fuzzy match / autocomplete** - pg_trgm
- **FTS + złożony Top-K + dynamiczne filtry** - ParadeDB lub ZomboDB
- **Wyszukiwanie semantyczne (embeddingi)** - pgvector
- **Time-series z Top-K** - TimescaleDB
- **Duża skala, dedykowany zespół** - Elasticsearch/OpenSearch osobno

## Kluczowe wnioski

1. **B-tree jest all-or-nothing** - optymalne dla jednego kształtu zapytania, katastrofalne dla innych
2. **Search engines skalują się lepiej** - jeden compound index zamiast wielu dedykowanych
3. **Columnar design dominuje** - cache-friendly lookups, SIMD processing, metadata pruning
4. **Block-level pruning jest krytyczny** - unika oceniania milionów dokumentów
5. **PostgreSQL z odpowiednim indeksem** radzi sobie dobrze z top-K na kluczach złożonych - ParadeDB ma przewagę głównie przy full text search i dynamicznych filtrach

---

**Źródła:**
- [Optimizing Top-K in Postgres](https://www.paradedb.com/blog/optimizing-top-k) - ParadeDB Blog
- [Dyskusja na Hacker News](https://news.ycombinator.com/item?id=47302493)