Re: Incremental sort for access method with ordered scan support (amcanorderbyop)

On Thu, Apr 20, 2023 at 6:38 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> That function is pretty new and was exactly added so we didn't have to
> write list_truncate(list_copy(...), n) anymore. That gets pretty
> wasteful when the input List is long and we only need a small portion
> of it.

I searched the codes and found some other places where the manipulation
of lists can be improved in a similar way.

* lappend(list_copy(list), datum) as in get_required_extension().
This is not very efficient as after list_copy it would need to enlarge
the list immediately. It can be improved by inventing a new function,
maybe called list_append_copy, that do the copy and append all together.

* lcons(datum, list_copy(list)) as in get_query_def().
This is also not efficient. Immediately after list_copy, we'd need to
enlarge the list and move all the entries. It can also be improved by
doing all these things all together in one function.

* lcons(datum, list_delete_nth_cell(list_copy(list), n)) as in
sort_inner_and_outer.
It'd need to copy all the elements, and then delete the n'th entry which
would cause all following entries be moved, and then move all the
remaining entries for lcons. Maybe we can invent a new function for it?

So is it worthwhile to improve these places?

Besides, I found one place that can be improved the same way as what we
did in 9d299a49.

--- a/src/backend/rewrite/rewriteSearchCycle.c
+++ b/src/backend/rewrite/rewriteSearchCycle.c
@@ -523,7 +523,7 @@ rewriteSearchAndCycle(CommonTableExpr *cte)

fexpr = makeFuncExpr(F_INT8INC, INT8OID, list_make1(fs),
InvalidOid, InvalidOid, COERCE_EXPLICIT_CALL);

- lfirst(list_head(search_col_rowexpr->args)) = fexpr;
+ linitial(search_col_rowexpr->args) = fexpr;

Also, in applyparallelworker.c we have the usage as

TransactionId xid_tmp = lfirst_xid(list_nth_cell(subxactlist, i));

I wonder if we can invent function list_nth_xid to do it, to keep
consistent with list_nth/list_nth_int/list_nth_oid.

Thanks
Richard