Какая сложность запроса данных по id в PostgreSQL?

Какая сложность запроса данных по id в PostgreSQL?

Сложность запроса по id в PostgreSQL зависит от типа индекса и структуры данных. В стандартном случае — это O(log n), но давайте разберемся подробнее.

Стандартный случай: B-tree индекс (O(log n))

PostgreSQL по умолчанию создает B-tree индекс на первичный ключ:

-- Автоматически создается при PRIMARY KEY
CREATE TABLE users (
    id BIGSERIAL PRIMARY KEY,  -- B-tree индекс
    name TEXT
);

-- Запрос by id: O(log n)
SELECT * FROM users WHERE id = 123;

Почему O(log n)? B-tree — сбалансированное дерево, где каждый уровень сокращает пространство поиска. Для таблицы с 1 млрд записей потребуется всего 3-4 дополнительных проверки (log₂(1,000,000,000) ≈ 30 бит).

import time
import psycopg2

conn = psycopg2.connect("dbname=testdb user=postgres")
cursor = conn.cursor()

# Запрос по индексированному id
start = time.time()
cursor.execute("SELECT * FROM users WHERE id = %s", (123,))
result = cursor.fetchone()
query_time = time.time() - start

print(f"Время запроса: {query_time:.6f} сек")  # ~0.001-0.01 сек

Сложность без индекса: O(n) — полный скан таблицы

Если индекса нет, PostgreSQL сканирует всю таблицу:

-- Без индекса на id — медленно!
SELECT * FROM users WHERE id = 123;  -- O(n) - полный скан

-- EXPLAIN покажет Seq Scan вместо Index Scan
EXPLAIN ANALYZE SELECT * FROM users WHERE id = 123;

Output:

Seq Scan on users  (cost=0.00..35000.00 rows=1 width=50)
  Filter: (id = 123)

Это в 1000x медленнее, чем индексированный запрос!

Другие типы индексов в PostgreSQL

Hash индекс — O(1) в лучшем случае:

-- Создаем Hash индекс для быстрого поиска по точному значению
CREATE INDEX idx_users_id_hash ON users USING HASH (id);

-- Запрос: O(1) в среднем случае (но может быть O(n) при коллизиях)
SELECT * FROM users WHERE id = 123;

Hash индексы могут быть быстрее B-tree для точного поиска, но имеют недостатки:

• Не поддерживают range queries (WHERE id > 100)
• Не ACID-безопасны при crash recovery (до версии 10)

BRIN индекс — O(1) для последовательных данных:

-- Для очень больших таблиц с отсортированными данными
CREATE INDEX idx_users_id_brin ON users USING BRIN (id);

-- Работает хорошо, если данные отсортированы естественно
SELECT * FROM users WHERE id = 123;

Реальная производительность

# Пример с измерением
import psycopg2
import time

conn = psycopg2.connect("dbname=large_db user=postgres")
cursor = conn.cursor()

# Запрос с B-tree индексом
start = time.time()
for i in range(1000):
    cursor.execute("SELECT id, name FROM users WHERE id = %s", (i,))
    cursor.fetchone()
b_tree_time = time.time() - start

# Запрос без индекса (после DROP INDEX)
cursor.execute("DROP INDEX IF EXISTS idx_users_id")

start = time.time()
for i in range(1000):
    cursor.execute("SELECT id, name FROM users WHERE id = %s", (i,))
    cursor.fetchone()
seq_scan_time = time.time() - start

print(f"С индексом (B-tree): {b_tree_time:.4f} сек")      # ~0.1 сек
print(f"Без индекса (Seq): {seq_scan_time:.4f} сек")      # ~10 сек
print(f"Разница: {seq_scan_time / b_tree_time:.0f}x")     # 100x медленнее

Проверка плана запроса (EXPLAIN)

-- Смотрим, как PostgreSQL выполнит запрос
EXPLAIN ANALYZE SELECT * FROM users WHERE id = 123;

Идеальный вывод (с индексом):

Index Scan using users_pkey on users  (cost=0.42..8.44 rows=1)
  Index Cond: (id = 123)
  Planning Time: 0.053 ms
  Execution Time: 0.147 ms

Плохой вывод (без индекса):

Seq Scan on users  (cost=0.00..35000.00 rows=1)
  Filter: (id = 123)
  Planning Time: 0.087 ms
  Execution Time: 12000.000 ms

Оптимизация запросов по id

# ✅ Используй подготовленные statements
from psycopg2.extras import execute_values

cursor.execute(
    "SELECT * FROM users WHERE id = %s",
    (123,)  # Параметризованный запрос
)

# ❌ Избегай конкатенации строк (SQL injection + медленнее)
# cursor.execute(f"SELECT * FROM users WHERE id = {123}")

# ✅ Для множественных id используй IN
cursor.execute(
    "SELECT * FROM users WHERE id = ANY(%s)",
    ([1, 2, 3, 4, 5],)  # O(log n * k), где k — количество id
)

# ❌ Плохо: 100 отдельных запросов
for id in user_ids:
    cursor.execute("SELECT * FROM users WHERE id = %s", (id,))

# ✅ Хорошо: 1 запрос на 100 id
cursor.execute("SELECT * FROM users WHERE id = ANY(%s)", (user_ids,))

Практические рекомендации

-- 1. Убедись, что PRIMARY KEY индексирован (автоматически)
CREATE TABLE users (
    id BIGSERIAL PRIMARY KEY,  -- B-tree индекс, O(log n)
    email TEXT UNIQUE,         -- Тоже индексирован
    created_at TIMESTAMP
);

-- 2. Для больших таблиц (>1M записей) рассмотри BRIN
-- если данные естественно отсортированы
CREATE INDEX idx_users_id_brin ON users USING BRIN (id)
    WHERE created_at > NOW() - INTERVAL '1 year';

-- 3. Монитори индексы
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
ORDER BY idx_scan DESC;

Итоговая таблица сложности