Theo định kỳ, nhiệm vụ tìm kiếm dữ liệu liên quan bằng một bộ khóa phát sinh, cho đến khi chúng tôi nhận được tổng số hồ sơ cần thiết.
Ví dụ "sống động như thật" nhất là hiển thị 20 vấn đề lâu đời nhất, liệt kê trong danh sách nhân viên (ví dụ, trong cùng một bộ phận). Đối với các "bảng điều khiển" quản lý khác nhau với các bản tóm tắt ngắn gọn về các lĩnh vực công việc, một chủ đề tương tự được yêu cầu khá thường xuyên.
Trong bài viết, chúng tôi sẽ xem xét việc triển khai trên PostgreSQL của một phiên bản “ngây thơ” để giải quyết vấn đề như vậy, một thuật toán “thông minh hơn” và rất phức tạp "vòng lặp" trong SQL với điều kiện thoát khỏi dữ liệu tìm thấy, có thể hữu ích cho cả sự phát triển chung và sử dụng trong các trường hợp tương tự khác.
Hãy lấy một tập dữ liệu thử nghiệm từ . Để các bản ghi đầu ra không thỉnh thoảng "nhảy" khi các giá trị được sắp xếp khớp với nhau, mở rộng chỉ mục chủ đề bằng cách thêm khóa chính. Đồng thời, điều này sẽ ngay lập tức mang lại cho nó tính duy nhất và đảm bảo cho chúng tôi tính duy nhất của thứ tự sắp xếp:
CREATE INDEX ON task(owner_id, task_date, id);
-- а старый - удалим
DROP INDEX task_owner_id_task_date_idx;Như nó được nghe, vì vậy nó được viết
Trước tiên, hãy phác thảo phiên bản đơn giản nhất của yêu cầu, chuyển ID của người biểu diễn :
SELECT
*
FROM
task
WHERE
owner_id = ANY('{1,2,4,8,16,32,64,128,256,512}'::integer[])
ORDER BY
task_date, id
LIMIT 20;
Hơi buồn - chúng tôi chỉ đặt hàng 20 bản ghi và Index Scan đã trả lại cho chúng tôi 960 dòng, mà sau đó cũng phải được sắp xếp ... Và hãy cố gắng đọc ít hơn.
không hợp lệ + Mảng
Việc xem xét đầu tiên sẽ giúp chúng tôi - nếu chúng tôi cần tổng số 20 được sắp xếp hồ sơ, nó là đủ để đọc không quá 20 được sắp xếp theo cùng một thứ tự cho mỗi chìa khóa. Tốt, chỉ số phù hợp (owner_id, task_date, id) chúng tôi có.
Hãy sử dụng cùng một cơ chế trích xuất và "biến thành cột" nhập bảng tích phân, như trong . Và cũng áp dụng tích chập cho một mảng bằng hàm ARRAY():
WITH T AS (
SELECT
unnest(ARRAY(
SELECT
t
FROM
task t
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 20 -- ограничиваем тут...
)) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
(r).*
FROM
T
ORDER BY
(r).task_date, (r).id
LIMIT 20; -- ... и тут - тоже
Ồ, nó đã tốt hơn nhiều rồi! Nhanh hơn 40% và dữ liệu ít hơn 4.5 lần đã phải đọc.
Cụ thể hóa các bản ghi bảng thông qua CTEtôi sẽ lưu ý rằng trong vài trường hợp nỗ lực làm việc ngay lập tức với các trường bản ghi sau khi tìm kiếm nó trong truy vấn con, mà không "gói" trong CTE, có thể dẫn đến "phép nhân" InitPlan tỷ lệ thuận với số lượng các trường giống nhau này:
SELECT
((
SELECT
t
FROM
task t
WHERE
owner_id = 1
ORDER BY
task_date, id
LIMIT 1
).*);Result (cost=4.77..4.78 rows=1 width=16) (actual time=0.063..0.063 rows=1 loops=1)
Buffers: shared hit=16
InitPlan 1 (returns $0)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.031..0.032 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t (cost=0.42..387.57 rows=500 width=48) (actual time=0.030..0.030 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 2 (returns $1)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_1 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 3 (returns $2)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_2 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4"
InitPlan 4 (returns $3)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_3 (cost=0.42..387.57 rows=500 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
Bản ghi tương tự đã được "tìm kiếm" 4 lần... Cho đến PostgreSQL 11, hành vi này xảy ra thường xuyên và giải pháp là "bọc" trong CTE, đây là ranh giới vô điều kiện cho trình tối ưu hóa trong các phiên bản này.
bộ tích lũy đệ quy
Trong phiên bản trước, tổng cộng, chúng tôi đọc 200 dòng vì lợi ích cần thiết 20. Đã không phải là 960, mà thậm chí còn ít hơn - có thể không?
Hãy cố gắng sử dụng kiến thức mà chúng ta cần tổng số 20 Hồ sơ. Nghĩa là, chúng tôi sẽ chỉ lặp lại phép trừ dữ liệu cho đến khi đạt được số lượng chúng tôi cần.
Bước 1: Bắt đầu danh sách
Rõ ràng, danh sách 20 mục "mục tiêu" của chúng ta phải bắt đầu bằng các mục "đầu tiên" cho một trong các khóa owner_id của chúng ta. Vì vậy, trước tiên chúng tôi tìm thấy như vậy "rất đầu tiên" cho mỗi phím và đặt nó vào danh sách, sắp xếp nó theo thứ tự chúng ta muốn - (task_date, id).
Bước 2: tìm các bản ghi "tiếp theo"
Bây giờ nếu chúng tôi lấy mục đầu tiên từ danh sách của mình và bắt đầu "bước" thêm xuống chỉ số với việc lưu khóa owner_id, thì tất cả các bản ghi được tìm thấy chỉ là những bản ghi tiếp theo trong lựa chọn kết quả. Tất nhiên, chỉ cho đến khi chúng tôi vượt qua khóa được áp dụng mục thứ hai trong danh sách.
Nếu hóa ra chúng tôi đã vượt qua mục nhập thứ hai, thì mục đọc cuối cùng nên được thêm vào danh sách thay vì mục đầu tiên (có cùng chủ sở hữu_id), sau đó danh sách được sắp xếp lại.
Đó là, chúng tôi luôn hiểu rằng danh sách không có nhiều hơn một mục cho mỗi khóa (nếu các mục đã hết và chúng tôi chưa "vượt qua", thì mục đầu tiên sẽ biến mất khỏi danh sách và sẽ không có gì được thêm vào ), và họ luôn được sắp xếp theo thứ tự tăng dần của khóa ứng dụng (task_date, id).
Bước 3: Lọc và mở rộng bản ghi
Trong phần các hàng của lựa chọn đệ quy của chúng tôi, một số bản ghi rv được trùng lặp - đầu tiên chúng tôi tìm thấy chẳng hạn như “vượt qua biên giới của mục thứ 2 trong danh sách”, sau đó chúng tôi thay thế bằng mục đầu tiên trong danh sách. Và do đó, lần xuất hiện đầu tiên nên được lọc ra.
Truy vấn cuối cùng khủng khiếp
WITH RECURSIVE T AS (
-- #1 : заносим в список "первые" записи по каждому из ключей набора
WITH wrap AS ( -- "материализуем" record'ы, чтобы обращение к полям не вызывало умножения InitPlan/SubPlan
WITH T AS (
SELECT
(
SELECT
r
FROM
task r
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 1
) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
array_agg(r ORDER BY (r).task_date, (r).id) list -- сортируем список в нужном порядке
FROM
T
)
SELECT
list
, list[1] rv
, FALSE not_cross
, 0 size
FROM
wrap
UNION ALL
-- #2 : вычитываем записи 1-го по порядку ключа, пока не перешагнем через запись 2-го
SELECT
CASE
-- если ничего не найдено для ключа 1-й записи
WHEN X._r IS NOT DISTINCT FROM NULL THEN
T.list[2:] -- убираем ее из списка
-- если мы НЕ пересекли прикладной ключ 2-й записи
WHEN X.not_cross THEN
T.list -- просто протягиваем тот же список без модификаций
-- если в списке уже нет 2-й записи
WHEN T.list[2] IS NULL THEN
-- просто возвращаем пустой список
'{}'
-- пересортировываем словарь, убирая 1-ю запись и добавляя последнюю из найденных
ELSE (
SELECT
coalesce(T.list[2] || array_agg(r ORDER BY (r).task_date, (r).id), '{}')
FROM
unnest(T.list[3:] || X._r) r
)
END
, X._r
, X.not_cross
, T.size + X.not_cross::integer
FROM
T
, LATERAL(
WITH wrap AS ( -- "материализуем" record
SELECT
CASE
-- если все-таки "перешагнули" через 2-ю запись
WHEN NOT T.not_cross
-- то нужная запись - первая из спписка
THEN T.list[1]
ELSE ( -- если не пересекли, то ключ остался как в предыдущей записи - отталкиваемся от нее
SELECT
_r
FROM
task _r
WHERE
owner_id = (rv).owner_id AND
(task_date, id) > ((rv).task_date, (rv).id)
ORDER BY
task_date, id
LIMIT 1
)
END _r
)
SELECT
_r
, CASE
-- если 2-й записи уже нет в списке, но мы хоть что-то нашли
WHEN list[2] IS NULL AND _r IS DISTINCT FROM NULL THEN
TRUE
ELSE -- ничего не нашли или "перешагнули"
coalesce(((_r).task_date, (_r).id) < ((list[2]).task_date, (list[2]).id), FALSE)
END not_cross
FROM
wrap
) X
WHERE
T.size < 20 AND -- ограничиваем тут количество
T.list IS DISTINCT FROM '{}' -- или пока список не кончился
)
-- #3 : "разворачиваем" записи - порядок гарантирован по построению
SELECT
(rv).*
FROM
T
WHERE
not_cross; -- берем только "непересекающие" записи
Vì vậy, chúng tôi giao dịch 50% dữ liệu đọc cho 20% thời gian thực hiện. Đó là, nếu bạn có lý do để tin rằng việc đọc có thể kéo dài (ví dụ: dữ liệu thường không có trong bộ đệm và bạn phải chuyển sang đĩa để đọc nó), thì theo cách này, bạn có thể phụ thuộc vào việc đọc ít hơn.
Trong mọi trường hợp, thời gian thực hiện hóa ra tốt hơn so với tùy chọn đầu tiên "ngây thơ". Nhưng việc sử dụng tùy chọn nào trong số 3 tùy chọn này là tùy thuộc vào bạn.
Nguồn: www.habr.com