Introduce list_reverse() to make lcons() usage less inefficient
От | David Rowley |
---|---|
Тема | Introduce list_reverse() to make lcons() usage less inefficient |
Дата | |
Msg-id | CAApHDvppEARU76FGEEDvEAvXxUa4MyUZcvOPSHrG4EusYtfzNw@mail.gmail.com обсуждение исходный текст |
Ответы |
Re: Introduce list_reverse() to make lcons() usage less inefficient
|
Список | pgsql-hackers |
While working on [1] to make improvements in the query planner around the speed to find EquivalenceMembers in an EquivalenceClass, because that patch does have a large impact in terms of performance improvements, some performance tests with that patch started to highlight some other places that bottleneck the planner's performance. One of those places is in generate_orderedappend_paths() when we find that the required sort order is the same as the reverse of the partition order. In this case, we build a list of paths for each partition using the lcons() function. Since Lists are now arrays in PostgreSQL, lcons() isn't as efficient as it once was and it must memmove the entire existing contents of the list up one element to make way to prepend the new element. This is effectively quadratic and becomes noticeable with a large number of partitions. One way we could solve that is to just lappend() the new item and then just reverse the order of the list only when we need to. This has the added advantage of removing a bunch of semi-duplicated code from generate_orderedappend_paths(). It also has a noticeable impact on the planner's performance. I did a quick test with: create table lp (a int, b int) partition by list(a); select 'create table lp'||x::text||' partition of lp for values in('||x::text||');' from generate_Series(1,10000)x; \gexec create index on lp(a); Using: psql -c "explain (analyze, timing off) select * from lp order by a desc" postgres | grep "Planning Time" master: Planning Time: 6034.765 ms Planning Time: 5919.914 ms Planning Time: 5720.529 ms master + eclass idx (from [1]) (yes, it really is this much faster) Planning Time: 549.262 ms Planning Time: 489.023 ms Planning Time: 497.803 ms master + eclass idx + list_reverse (attached) Planning Time: 517.067 ms Planning Time: 463.613 ms Planning Time: 463.036 ms I suspect there won't be much controversy here and there's certainly not much complexity, so in absence of anyone voicing an opinion here, I'm inclined to not waste too much time on this one and just get it done. I'll leave it for a few days. David [1] https://postgr.es/m/flat/CAJ2pMkZNCgoUKSE+_5LthD+KbXKvq6h2hQN8Esxpxd+cxmgomg@mail.gmail.com
Вложения
В списке pgsql-hackers по дате отправления: