1

Configuration

PostgreSQL 11.4

SET default_statistics_target=1000;

Data

The scenario is that there are "computers" each with "files", which each have path (ordered text list) unique to that computer. In this case, there are 20 computers each 20,000 files.

(This is obviously different semantics than a real "file system"; the important element for this example is prefix/range searching on file.file_path.)

CREATE TABLE computer (
  computer_id serial PRIMARY KEY,
  computer_name text UNIQUE
);

CREATE TABLE file (
  file_id serial PRIMARY KEY,
  computer_id int NOT NULL REFERENCES computer (computer_id),
  file_path text[],
  UNIQUE (computer_id, file_path)
);

INSERT INTO computer (computer_name)
SELECT generate_series::text
FROM generate_series(1, 20);

INSERT INTO file (computer_id, file_path)
SELECT computer_id,
  ARRAY[
    md5((generate_series / 20)::text),
    md5(generate_series::text)
  ]
FROM generate_series(1, 20 * 1000)
  CROSS JOIN computer;

ANALYZE computer, file;

Query

I want to search on computers named '3' and '6', for files matching a list of 500 prefixes. For ease of demonstration, I put these prefixes in a table (table or array, I haven't seen a difference):

SELECT ARRAY[md5((generate_series * 2)::text)] AS search_prefix
INTO search
FROM generate_series(1, 500);

ANALYZE search;

Poor result

The intuitive query

EXPLAIN ANALYZE SELECT count(*)
FROM computer
  NATURAL JOIN file
  JOIN search ON file_path BETWEEN search_prefix AND array_append(search_prefix, NULL)
WHERE computer_name IN ('3', '6');

yields

    QUERY PLAN                                                                             
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=415614.05..415614.06 rows=1 width=8) (actual time=10694.152..10694.153 rows=1 loops=1)
   ->  Nested Loop  (cost=813.30..410058.49 rows=2222222 width=0) (actual time=41.600..10691.268 rows=19962 loops=1)
         Join Filter: ((file.file_path >= search.search_prefix) AND (file.file_path <= array_append(search.search_prefix, NULL::text)))
         Rows Removed by Join Filter: 19980038
         ->  Nested Loop  (cost=813.30..10046.24 rows=40000 width=93) (actual time=12.807..49.178 rows=40000 loops=1)
               ->  Seq Scan on computer  (cost=0.00..1.25 rows=2 width=4) (actual time=0.015..0.021 rows=2 loops=1)
                     Filter: (computer_name = ANY ('{3,6}'::text[]))
                     Rows Removed by Filter: 18
               ->  Bitmap Heap Scan on file  (cost=813.30..4822.50 rows=20000 width=97) (actual time=8.148..21.328 rows=20000 loops=2)
                     Recheck Cond: (computer_id = computer.computer_id)
                     Heap Blocks: exact=13116
                     ->  Bitmap Index Scan on file_computer_id_file_path_key  (cost=0.00..808.30 rows=20000 width=0) (actual time=6.242..6.242 rows=20000 loops=2)
                           Index Cond: (computer_id = computer.computer_id)
         ->  Materialize  (cost=0.00..13.50 rows=500 width=57) (actual time=0.000..0.024 rows=500 loops=40000)
               ->  Seq Scan on search  (cost=0.00..11.00 rows=500 width=57) (actual time=0.018..0.157 rows=500 loops=1)
 Planning Time: 3.846 ms
 Execution Time: 10694.312 ms

Good result

The only way I can get good performance is by rewriting the query and working over the query planner

SET join_collapse_limit TO 1;
SET enable_hashjoin TO FALSE;
SET enable_mergejoin TO FALSE;

EXPLAIN ANALYZE SELECT count(*)
FROM computer
  CROSS JOIN search
  NATURAL JOIN file
WHERE computer_name IN ('3', '6')
  AND file_path BETWEEN search_prefix AND array_append(search_prefix, NULL);

which yields ~200x faster performance:

    QUERY PLAN                                                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=2251534.33..2251534.34 rows=1 width=8) (actual time=52.493..52.493 rows=1 loops=1)
   ->  Nested Loop  (cost=106.88..2245978.77 rows=2222222 width=0) (actual time=0.128..49.548 rows=19962 loops=1)
         ->  Nested Loop  (cost=0.00..24.75 rows=1000 width=61) (actual time=0.037..1.028 rows=1000 loops=1)
               ->  Seq Scan on search  (cost=0.00..11.00 rows=500 width=57) (actual time=0.014..0.159 rows=500 loops=1)
               ->  Materialize  (cost=0.00..1.26 rows=2 width=4) (actual time=0.000..0.001 rows=2 loops=500)
                     ->  Seq Scan on computer  (cost=0.00..1.25 rows=2 width=4) (actual time=0.016..0.025 rows=2 loops=1)
                           Filter: (computer_name = ANY ('{3,6}'::text[]))
                           Rows Removed by Filter: 18
         ->  Bitmap Heap Scan on file  (cost=106.88..2223.73 rows=2222 width=97) (actual time=0.029..0.041 rows=20 loops=1000)
               Recheck Cond: ((computer_id = computer.computer_id) AND (file_path >= search.search_prefix) AND (file_path <= array_append(search.search_prefix, NULL::text)))
               Heap Blocks: exact=7220
               ->  Bitmap Index Scan on file_computer_id_file_path_key  (cost=0.00..106.33 rows=2222 width=0) (actual time=0.024..0.024 rows=20 loops=1000)
                     Index Cond: ((computer_id = computer.computer_id) AND (file_path >= search.search_prefix) AND (file_path <= array_append(search.search_prefix, NULL::text)))
 Planning Time: 0.485 ms
 Execution Time: 52.564 ms

Why am I not getting good performance with my first query? Are there any other ways I could do the prefix search without fighting the query planner so strongly?

2
  • You could try modeling that with a more natural data type like ltree. Then maybe the query will become simpler and easier to estimate for the optimizer. Feb 17, 2020 at 7:29
  • @LaurenzAlbe, interesting. The characters restrictions on ltree may be limiting, but that is worth looking at. Feb 17, 2020 at 7:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.