your analysis seems valid, I even am not sure if we need the sorting at all.
In the creat index code the id list is processed and for each id parentid is determined and the idlist set, I don't see where it is needed to have the list sorted

I was of a similar view.

Lacking certainty about whether there was some point to the sorting--though it appeared to me there was not--I went ahead and sorted it so that I could guarantee continuity before and after the change.

Hi @telackey
My name is Simon. I am a part of DS team.
You are very welcome with the contribution! :)

One thing. Could you, please, create a pull-request with the commit? It is part of our process now and it will be easier to test and review there.

You can find the instructions here - http://www.port389.org/docs/389ds/contributing.html#creating-a-patch-for-review

Thanks!

I did my own tests, with master, with the provided patch and with the patch without sorting.
The ldif contained 12million entries with 2.4m inner nodes, it was basically a tree where
each node had 5 children in 10 levels.

With master the preparation for the ancestorid with ldbm_get_nonleaf_ids() took 40min, with the patch <1min and the sorting only took <1sec.

For all three tests the generated ancestorid was identical, so sorting is not needed, but it also does not hurt. A small difference with the patch sorted and unsorted was the size of the ancestorid.db file, with master and patch(sorted) it was 2.468GB, with patch(unsorted) it was 2.486GB - so there is a slight difference in fragmentation caused by the order of insertion.

I suggest to use the provided patch as it is, it speeds up the import considerably and creates and identical db file

Thank you!

@telackey - do you want to create PR for this, or do you want me to do it?

If you do file the PR please use C-style comments, not java style comments //

If you are happy with the patch as-is (modulo the comment style, which is easy to change), I can open up the PR.

Should it be against master?

I am also happy if you do it. Whichever is easier.

yes it would be master branch, and the commit message would like:

Ticket 49850 - <DESCRIPTION OF PROBLEM>

Description:  <your description of the issue and fix>

https://pagure.io/389-ds-base/issue/49850

Reviewed by: lkrispen

Then I will cherry-pick it to 1.3.8

https://pagure.io/389-ds-base/pull-request/50630

Sorry this took so long @telackey

My testing with a "heavily nested" 1 million entry LDIF shows a 35% performance improvement. Most likely the more nested the LDIF is the better the improvement would be.

I did not see any impact on a flat ldif file with 1 million entries.

Commit fc47620 relates to this ticket

225f4e1..fc47620 master -> master

3b47e3f..fb4ea1d 389-ds-base-1.4.1 -> 389-ds-base-1.4.1

13340ad..9eba2ce 389-ds-base-1.4.0 -> 389-ds-base-1.4.0

3fbff08..3be2a20 389-ds-base-1.3.10 -> 389-ds-base-1.3.10

There is a crash if an ldif with only the root entry is imported, there will be no leafs an nodes is NULL and

 qsort((void *)&nodes->b_ids[0], nodes->b_nids, (size_t)sizeof(ID), idl_sort_cmp);

crashes

Just do a quick NULL test before the qsort?

Or possibly take the sort out entirely, as mentioned above.

Or possibly take the sort out entirely, as mentioned above.

@lkrispen fixed it in this PR: https://pagure.io/389-ds-base/pull-request/50672

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/2909

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.