BUG #12866: Another performance problem with intarray extenstion operators
The following bug has been logged on the website:
Bug reference: 12866
Logged by: Maksym Boguk
Email address: maxim.boguk@gmail.com
PostgreSQL version: 9.3.5
Operating system: Linux
Description:
Hi,
I found second case where intarray operators have serious performance
issues:
create table test1 as select array_agg(id) as _array from
generate_series(100000,1, -1) as g(id);
analyze verbose test;
generic version:
# EXPLAIN ANALYZE SELECT 1 FROM test1 WHERE ARRAY[16997]
OPERATOR(pg_catalog.<@) _array;
QUERY PLAN
------------------------------------------------------------------------------------------------
Seq Scan on test1 (cost=0.00..17.38 rows=7 width=0) (actual
time=1.286..1.287 rows=1 loops=1)
Filter: ('{16997}'::integer[] OPERATOR(pg_catalog.<@) _array)
Total runtime: 1.301 ms
intarray version:
=# EXPLAIN ANALYZE SELECT 1 FROM test1 WHERE ARRAY[16997]
OPERATOR(public.<@) _array;
QUERY PLAN
------------------------------------------------------------------------------------------------------
Seq Scan on test1 (cost=0.00..17.38 rows=1 width=0) (actual
time=2738.589..2738.591 rows=1 loops=1)
Filter: ('{16997}'::integer[] <@ _array)
Total runtime: 2738.607 ms
Whats made situation worse - intarray version could not be terminated by
ctrl-c or pg_terminate_backend (so don't try it with 1M or more array
elements).
PS: filling array in descending order is critical to reproducing the issue.
PPS: my previous bug report about issues with intarray (wrong selectivity
estimator functions used) seems stuck in the moderation queue.
--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs
maxim.boguk@gmail.com writes:
I found second case where intarray operators have serious performance
issues:
...
PS: filling array in descending order is critical to reproducing the issue.
The problem is evidently in isort():
/*
* We use a simple insertion sort. While this is O(N^2) in the worst
* case, it's quite fast if the input is already sorted or nearly so.
* Also, for not-too-large inputs it's faster than more complex methods
* anyhow.
*/
That comment, as well as the current code, date to my commit fdf2dbda;
but it doesn't look like the previous code was any better in terms of
worst-case behavior. It's tempting to just trash the whole thing in
favor of qsort().
regards, tom lane
--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs