Task #85300

Improve record sorting performance

Added by Tymoteusz Motylewski over 1 year ago. Updated about 1 year ago.

Status:
Closed
Priority:
Should have
Assignee:
-
Category:
-
Target version:
-
Start date:
2018-06-18
Due date:
% Done:

100%

TYPO3 Version:
9
PHP Version:
Tags:
Complexity:
Sprint Focus:

Description

Currently when TYPO3 inserts a record to a table which is position aware ($GLOBALS['TCA'][$table]['ctrl']['sortby'] is set), it needs to calculate sorting value.
If there is no "sorting space" left between elements, the whole table needs to be resorted.

TYPO3 now does 1 update query per row in the table.
Instead we should make 1 update query to update all rows.

Additionaly the algorithm of calculating the next sorting value should be improved to allow more space between rows == meaning that full resorting will happen less often.


Related issues

Related to TYPO3 Core - Bug #88696: DataHandler getSortNumber use of increaseSortingOfFollowing wrong Closed 2019-07-05

Associated revisions

Revision 9d2f51fa (diff)
Added by Markus Klein about 1 year ago

[TASK] Reduce number of needed SQL queries for resorting of records

This reduces the resorting to require only a single update statement
in contrast to "number of records" statements.
It also only updates the records after the current one, so less records
are touched when resorting.

Now handling of the sorting value is following:
- if no record exists: set interval as sorting number
- if inserted before an element: put in the middle of the existing elements
- if inserted behind the last element: add interval to last sorting number
- if collision: move all subsequent records by 2 * interval, insert
new record with sorting = collision + interval

Before, in case of the collision all the records from given pid were
resorted. The first item was getting 512 (2*sortIntervals) as sorting,
following records were getting value of
previous record + sortIntervals (768,1024,...).

Note:
I case we have multiple records with the same sorting value,
resorting will not fix that, but just move them up.

New algorithm drawback:
Sorting column values will grow quicker in time as we're always
increasing the sorting value and never tidying the whole table
(thus possibly lowering the max used value).
The current implementation still allows to insert some 80 million
records per colpos if sizeof(int) is only 32bit.
A lot more if we have 64bit.

Changes to the DataHandler->getSortNumber method are mostly comments and
formatting (added guard clause), no change in behavior except for
additional sorting by uid. The additional sorting was required to have
the same test results across database servers.

Description of updated tests:

- workspaces/.../IRRE/ForeignField/Publish/DataSet/copyPage.csv
workspaces/.../IRRE/ForeignField/Publish/DataSet/copyPageWHotelBeforeParentContent.csv
workspaces/.../IRRE/ForeignField/PublishAll/DataSet/copyPage.csv
workspaces/.../IRRE/ForeignField/PublishAll/DataSet/copyPageWHotelBeforeParentContent.csv

Now copied tx_irretutorial_1nff_price records have the same
sorting values/order as original records (1,2,3 instead of 1,3,2).
So workspace actions result in the same values as live operations.

- backend/.../Controller/Page/Localization/CSV/DataSet/CreatedElementOrdering.csv
Order of the records in both languages is kept (before and after the patch),
It might look wrong that a record 2.5 in translation is between 1 and 2
and not between 2 and 3, but keep in mind that colpos is taken into account.
So record 2.5 has just to be after record 1 (only the two are in colpos 0).

- install/.../Updates/RowUpdater/DataSet/recordsCanBeUpdated.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizePageWSynchronization.csv
core/.../IRRE/ForeignField/Modify/DataSet/createNLocalizeParentContentNHotelNOfferChildren.csv
core/.../IRRE/ForeignField/Modify/DataSet/createNLocalizeParentContentNHotelNOfferChildrenWOSortBy.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizeNCopyPageWSynchronization.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizePageWExclude.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizePageWithSynchronizationAndCustomLocalizedHotel.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizeParentContentNCreateNestedChildrenWLanguageSynchronization.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizeParentContentSynchronization.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizeParentContentChainLanguageSynchronizationSource.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizeParentContentWAllChildren.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizePageAddMonoglotHotelChildNCopyPageWSynchronization.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizePageNAddMonoglotHotelChildWSynchronization.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizePageNAddHotelChildWSynchronization.csv
core/.../IRRE/ForeignField/Modify/DataSet/localizePageNAddHotelChildWExclude.csv
core/.../IRRE/ForeignField/Modify/DataSet/copyParentContentToLanguageWAllChildren.csv
workspaces/.../IRRE/ForeignField/Publish/DataSet/createNLocalizeParentContentNHotelNOfferChildren.csv
workspaces/.../IRRE/ForeignField/PublishAll/DataSet/localizeParentContentWAllChildren.csv
workspaces/.../IRRE/ForeignField/PublishAll/DataSet/createNLocalizeParentContentNHotelNOfferChildren.csv
workspaces/.../IRRE/ForeignField/PublishAll/DataSet/createNLocParentNHotelNOfferChildrenNDiscardCreatedParent.csv
workspaces/.../IRRE/ForeignField/PublishAll/DataSet/createNLocParentNHotelNOfferChildrenNDiscardLocParent.csv
workspaces/.../IRRE/ForeignField/Modify/DataSet/copyPage.csv
workspaces/.../IRRE/ForeignField/Modify/DataSet/localizeParentContentWAllChildren.csv
workspaces/.../IRRE/ForeignField/Modify/DataSet/createNLocalizeParentContentNHotelNOfferChildren.csv
workspaces/.../IRRE/ForeignField/Modify/DataSet/createNLocalizeParentContentNHotelNOfferChildrenWOSortBy.csv
workspaces/.../IRRE/ForeignField/Modify/DataSet/createNLocParentNHotelNOfferChildrenNDiscardCreatedParent.csv
workspaces/.../IRRE/ForeignField/Modify/DataSet/copyPageWHotelBeforeParentContent.csv
workspaces/.../IRRE/ForeignField/Publish/DataSet/localizeParentContentWAllChildren.csv
workspaces/.../IRRE/ForeignField/Publish/DataSet/createNLocParentNHotelNOfferChildrenNDiscardCreatedParent.csv
workspaces/.../IRRE/ForeignField/Publish/DataSet/createNLocParentNHotelNOfferChildrenNDiscardLocParent.csv

Order of the records is kept, less records have changed sorting values,
as now we're just resorting records after the current one.

- impexp/.../DatabaseAssertions/importPagesAndRelatedTtContentWithDifferentImageToExistingData.csv
impexp/.../DatabaseAssertions/importPagesAndRelatedTtContentWithSameImageToExistingData.csv
now existing page sorting is not changed when importing data.

- workspaces/.../IRRE/CSV/Publish/DataSet/moveParentContentToDifferentPageNChangeSorting.csv
workspaces/.../IRRE/CSV/Modify/DataSet/moveParentContentToDifferentPageNChangeSorting.csv
workspaces/.../IRRE/CSV/PublishAll/DataSet/moveParentContentToDifferentPageNChangeSorting.csv

in CSV relation we don't care about the child sorting field as
the order is determined by the value of the CSV field.

Resolves: #85300
Releases: master
Change-Id: I033acae475be8778d10dfb5d506d63804aa941e0
Reviewed-on: https://review.typo3.org/57218
Tested-by: TYPO3com <>
Reviewed-by: Markus Klein <>
Tested-by: Markus Klein <>
Reviewed-by: Anja Leichsenring <>
Tested-by: Anja Leichsenring <>
Reviewed-by: Christian Kuhn <>
Tested-by: Christian Kuhn <>

History

#1 Updated by Gerrit Code Review over 1 year ago

  • Status changed from New to Under Review

Patch set 6 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#2 Updated by Gerrit Code Review over 1 year ago

Patch set 7 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#3 Updated by Gerrit Code Review over 1 year ago

Patch set 8 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#4 Updated by Gerrit Code Review over 1 year ago

Patch set 9 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#5 Updated by Gerrit Code Review about 1 year ago

Patch set 10 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#6 Updated by Gerrit Code Review about 1 year ago

Patch set 11 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#7 Updated by Gerrit Code Review about 1 year ago

Patch set 12 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#8 Updated by Gerrit Code Review about 1 year ago

Patch set 13 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#9 Updated by Gerrit Code Review about 1 year ago

Patch set 14 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#10 Updated by Gerrit Code Review about 1 year ago

Patch set 15 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#11 Updated by Gerrit Code Review about 1 year ago

Patch set 16 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#12 Updated by Gerrit Code Review about 1 year ago

Patch set 17 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#13 Updated by Gerrit Code Review about 1 year ago

Patch set 18 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#14 Updated by Gerrit Code Review about 1 year ago

Patch set 19 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#15 Updated by Gerrit Code Review about 1 year ago

Patch set 20 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#16 Updated by Gerrit Code Review about 1 year ago

Patch set 21 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#17 Updated by Gerrit Code Review about 1 year ago

Patch set 22 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#18 Updated by Gerrit Code Review about 1 year ago

Patch set 23 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#19 Updated by Gerrit Code Review about 1 year ago

Patch set 24 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#20 Updated by Gerrit Code Review about 1 year ago

Patch set 25 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#21 Updated by Gerrit Code Review about 1 year ago

Patch set 26 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#22 Updated by Gerrit Code Review about 1 year ago

Patch set 27 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#23 Updated by Gerrit Code Review about 1 year ago

Patch set 28 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#24 Updated by Gerrit Code Review about 1 year ago

Patch set 29 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#25 Updated by Gerrit Code Review about 1 year ago

Patch set 30 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#26 Updated by Gerrit Code Review about 1 year ago

Patch set 31 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#27 Updated by Gerrit Code Review about 1 year ago

Patch set 32 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#28 Updated by Gerrit Code Review about 1 year ago

Patch set 33 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#29 Updated by Gerrit Code Review about 1 year ago

Patch set 34 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#30 Updated by Gerrit Code Review about 1 year ago

Patch set 35 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#31 Updated by Gerrit Code Review about 1 year ago

Patch set 36 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#32 Updated by Gerrit Code Review about 1 year ago

Patch set 37 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#33 Updated by Gerrit Code Review about 1 year ago

Patch set 38 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#34 Updated by Gerrit Code Review about 1 year ago

Patch set 39 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#35 Updated by Gerrit Code Review about 1 year ago

Patch set 40 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at https://review.typo3.org/57218

#36 Updated by Markus Klein about 1 year ago

  • Status changed from Under Review to Resolved
  • % Done changed from 0 to 100

#37 Updated by Benni Mack about 1 year ago

  • Status changed from Resolved to Closed

#38 Updated by Tymoteusz Motylewski 3 months ago

  • Related to Bug #88696: DataHandler getSortNumber use of increaseSortingOfFollowing wrong added

Also available in: Atom PDF