<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0">
<base href="https://hibernate.atlassian.net">
<title>Message Title</title>
</head>
<body class="jira" style="color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 1.429">
<table id="background-table" cellpadding="0" cellspacing="0" width="100%" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0; background-color: #f5f5f5; border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0" bgcolor="#f5f5f5">
<!-- header here -->
<tbody>
<tr>
<td id="header-pattern-container" style="padding: 0; border-collapse: collapse; padding: 10px 20px">
<table id="header-pattern" cellspacing="0" cellpadding="0" border="0" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0">
<tbody>
<tr>
<td id="header-avatar-image-container" valign="top" style="padding: 0; border-collapse: collapse; vertical-align: top; width: 32px; padding-right: 8px" width="32"> <img id="header-avatar-image" class="image_fix" src="https://avatar-cdn.atlassian.com/7447b128f8696bc3b6c2982269c8bed7?s=48&d=https%3A%2F%2Fsecure.gravatar.com%2Favatar%2F7447b128f8696bc3b6c2982269c8bed7%3Fd%3Dmm%26s%3D48%26noRedirect%3Dtrue" height="32" width="32" border="0" style="border-radius: 3px; vertical-align: top"> </td>
<td id="header-text-container" valign="middle" style="padding: 0; border-collapse: collapse; vertical-align: middle; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; mso-line-height-rule: exactly; mso-text-raise: 1px"> <a class="user-hover" rel="rdearnaley" id="email_rdearnaley" href="https://hibernate.atlassian.net/secure/ViewProfile.jspa?name=rdearnaley" style="color:#6c797f;; color: #3b73af; text-decoration: none">Roger Dearnaley</a> <strong>updated</strong> an issue </td>
</tr>
</tbody>
</table> </td>
</tr>
<tr>
<td id="email-content-container" style="padding: 0; border-collapse: collapse; padding: 0 20px">
<table id="email-content-table" cellspacing="0" cellpadding="0" border="0" width="100%" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0; border-spacing: 0; border-collapse: separate">
<tbody>
<tr>
<!-- there needs to be content in the cell for it to render in some clients -->
<td class="email-content-rounded-top mobile-expand" style="padding: 0; border-collapse: collapse; color: #ffffff; padding: 0 15px 0 16px; height: 15px; background-color: #ffffff; border-left: 1px solid #cccccc; border-top: 1px solid #cccccc; border-right: 1px solid #cccccc; border-bottom: 0; border-top-right-radius: 5px; border-top-left-radius: 5px; height: 10px; line-height: 10px; padding: 0 15px 0 16px; mso-line-height-rule: exactly" height="10" bgcolor="#ffffff"> </td>
</tr>
<tr>
<td class="email-content-main mobile-expand " style="padding: 0; border-collapse: collapse; border-left: 1px solid #cccccc; border-right: 1px solid #cccccc; border-top: 0; border-bottom: 0; padding: 0 15px 0 16px; background-color: #ffffff" bgcolor="#ffffff">
<table class="page-title-pattern" cellspacing="0" cellpadding="0" border="0" width="100%" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0">
<tbody>
<tr>
<td class="page-title-pattern-first-line " style="padding: 0; border-collapse: collapse; font-family: Arial, sans-serif; font-size: 14px; padding-top: 10px"> <a href="https://hibernate.atlassian.net/browse/HHH" style="color: #3b73af; text-decoration: none">Hibernate ORM</a> / <a href="https://hibernate.atlassian.net/browse/HHH-12374" style="color: #3b73af; text-decoration: none"><img src="cid:jira-generated-image-avatar-f7ea844d-25f8-4b36-a04e-6280887ff589" height="16" width="16" border="0" align="absmiddle" alt="Bug" style="vertical-align: text-bottom"></a> <a href="https://hibernate.atlassian.net/browse/HHH-12374" style="color: #3b73af; text-decoration: none">HHH-12374</a> </td>
</tr>
<tr>
<td style="vertical-align: top;; padding: 0; border-collapse: collapse; padding-right: 5px; font-size: 20px; line-height: 30px; mso-line-height-rule: exactly" class="page-title-pattern-header-container"> <span class="page-title-pattern-header" style="font-family: Arial, sans-serif; padding: 0; font-size: 20px; line-height: 30px; mso-text-raise: 2px; mso-line-height-rule: exactly; vertical-align: middle"> <a href="https://hibernate.atlassian.net/browse/HHH-12374" style="color: #3b73af; text-decoration: none">Order inserts sorting code gives up too soon</a> </span> </td>
</tr>
</tbody>
</table> </td>
</tr>
<tr>
<td class="email-content-main mobile-expand wrapper-special-margin" style="padding: 0; border-collapse: collapse; border-left: 1px solid #cccccc; border-right: 1px solid #cccccc; border-top: 0; border-bottom: 0; padding: 0 15px 0 16px; background-color: #ffffff; padding-top: 10px; padding-bottom: 5px" bgcolor="#ffffff">
<table class="keyvalue-table" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0">
<tbody>
<tr>
<th style="color: #707070; font: normal 14px/20px Arial, sans-serif; text-align: left; vertical-align: top; padding: 2px 0">Change By:</th>
<td style="padding: 0; border-collapse: collapse; font: normal 14px/20px Arial, sans-serif; padding: 2px 0 2px 5px; vertical-align: top"> <a class="user-hover" rel="rdearnaley" id="email_rdearnaley" href="https://hibernate.atlassian.net/secure/ViewProfile.jspa?name=rdearnaley" style="color:#6c797f;; color: #3b73af; text-decoration: none">Roger Dearnaley</a> </td>
</tr>
</tbody>
</table> </td>
</tr>
<tr>
<td class="email-content-main mobile-expand issue-description-container" style="padding: 0; border-collapse: collapse; border-left: 1px solid #cccccc; border-right: 1px solid #cccccc; border-top: 0; border-bottom: 0; padding: 0 15px 0 16px; background-color: #ffffff; padding-top: 5px; padding-bottom: 10px" bgcolor="#ffffff">
<table class="text-paragraph-pattern" cellspacing="0" cellpadding="0" border="0" width="100%" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; mso-line-height-rule: exactly; mso-text-raise: 2px">
<tbody>
<tr>
<td class="text-paragraph-pattern-container mobile-resize-text " style="padding: 0; border-collapse: collapse; padding: 0 0 10px"> <span class="diffcontext">Line 1191 of hibernate-orm\hibernate-core\src\main\java\org\hibernate\engine\spi\ActionQueue.java in the function {{sort(List<AbstractEntityInsertAction> insertions)}} is:<br><br>{code}<br>long maxIterations = latestBatches.size() * 2;<br>{code}<br><br>This variable controls how many passes of the sort algorithm is willing to do before it gives up and assumes that the set of batches is unsortable due to a cycle of entity parent-relationships (lines 1219-1225):<br><br>{code}<br>}<br>while ( !sorted && iterations <= maxIterations);<br><br>if ( iterations > maxIterations ) {<br> LOG.warn( "The batch containing " + latestBatches.size() + " statements could not be sorted after " + maxIterations + " iterations. " +<br> "This might indicate a circular entity relationship." );<br>}<br>{code}<br><br>The formula {{long maxIterations = latestBatches.size() * 2}} assumes that the sorting algorithm in use has O(N) scaling. This is impossible -- the optimum possible performance for any general search algorithm is O(N logN) on a fully-ordered set (which is a special case of a partially-ordered set). I am uncertain whether the search algorithm in use here has O(N logN) performance (like QuickSort, but it doesn't look like that, since it doesn't include any binary search behavior), or O(N^2), or O(N^2 logN), or even O(N^3) (like Bubble Sort, which the algorithm somewhat resembles), but it definitely cannot be O(N).<br><br>I have a (complex and currently unready for submission) test case with latestBatches.size() = 10 which requires maxIterations >= 28 to be sorted correctly -- significantly more than the limit of 20 that the code above sets. I am in the process of developing a fuzz test to search for even worse cases over the range latestBatches.size() = 8 to 16 -- once I find some I will convert this into a test case or test cases and attach it here. Hopefully the ratio between the required maxIterations values for N=8 and N=16 will cast some light on what the performance scaling of the search algorithm in use is.<br><br>(FYI, good algorithms for sorting a partially-ordered set can be found at [https://en.wikipedia.org/wiki/Topological_sorting] -- apparently they are linear in the (number of nodes plus number of links) of the graph for the partially ordered set, which means they are potentially anywhere from O(N) up to O(N^2) in the number of nodes, depending on how dense the links are -- for a fully-ordered set they would be O(N^2).)<br><br>Possibly this should be a separate JIRA, but if the maxIterations limit is reached, then the code's current behavior is to log a warning and then attempt to use whatever not-fully sorted batch order its sort algorithm had currently reached. This will almost inevitably result in a constraint violation (whether the entity relationship graph does actually contain a cycle, or the list was simply not yet full sorted). I believe that the correct behavior would be to instead log a warning and then act as if ORDER_INSERTS had not been set, and perform the inserts (not batched) in their original unsorted order (i.e. in the order they were persisted in). This</span> <span class="diffremovedchars" style="background-color: #ffe7e7; text-decoration:line-through;"> may</span> <span class="diffaddedchars" style="background-color:#ddfade;"> will</span> <span class="diffcontext"> make the database operation slower, but is the order in which it is most likely to succeed without a constraint violation, and (unlike the current behavior) also gives the user of the library full control to fix the problem if a constraint violation occurs.<br><br>An even better behavior (consider this an enhancement suggestion) would be to use something like [https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm] to identify which entity types can and cannot safely be batched, then batch the ones that can be batched and sort the batches correctly, while performing the inserts for entity types that cannot safely be batched in their original order (interspersed in the appropriate places in the order of batches).</span> </td>
</tr>
</tbody>
</table> </td>
</tr>
<tr>
<td class="email-content-main mobile-expand " style="padding: 0; border-collapse: collapse; border-left: 1px solid #cccccc; border-right: 1px solid #cccccc; border-top: 0; border-bottom: 0; padding: 0 15px 0 16px; background-color: #ffffff" bgcolor="#ffffff"> <script type="application/ld+json">
{
"@context": "http://schema.org",
"@type": "EmailMessage",
"description": "View Issue",
"potentialAction": {
"@type": "ViewAction",
"target": "https://hibernate.atlassian.net/browse/HHH-12374?inbox=true&",
"name": "View Issue"
},
"publisher": {
"@type": "Organization",
"name": "Atlassian",
"url": "https://www.atlassian.com"
}
}
</script>
<table id="actions-pattern" cellspacing="0" cellpadding="0" border="0" width="100%" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; mso-line-height-rule: exactly; mso-text-raise: 1px">
<tbody>
<tr>
<td id="actions-pattern-container" valign="middle" style="padding: 0; border-collapse: collapse; padding: 10px 0 10px 24px; vertical-align: middle; padding-left: 0">
<table align="left" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0">
<tbody>
<tr>
<td class="actions-pattern-action-icon-container" style="padding: 0; border-collapse: collapse; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; mso-line-height-rule: exactly; mso-text-raise: 0; vertical-align: middle"> <a href="https://hibernate.atlassian.net/browse/HHH-12374#add-comment" target="_blank" title="Add Comment" style="color: #3b73af; text-decoration: none"> <img class="actions-pattern-action-icon-image" src="cid:jira-generated-image-static-comment-icon-776d59d2-3663-49e9-96bc-1c899ca5c1b5" alt="Add Comment" title="Add Comment" height="16" width="16" border="0" style="vertical-align: middle"> </a> </td>
<td class="actions-pattern-action-text-container" style="padding: 0; border-collapse: collapse; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; mso-line-height-rule: exactly; mso-text-raise: 4px; padding-left: 5px"> <a href="https://hibernate.atlassian.net/browse/HHH-12374#add-comment" target="_blank" title="Add Comment" style="color: #3b73af; text-decoration: none">Add Comment</a> </td>
</tr>
</tbody>
</table> </td>
</tr>
</tbody>
</table> </td>
</tr>
<!-- there needs to be content in the cell for it to render in some clients -->
<tr>
<td class="email-content-rounded-bottom mobile-expand" style="padding: 0; border-collapse: collapse; color: #ffffff; padding: 0 15px 0 16px; height: 5px; line-height: 5px; background-color: #ffffff; border-top: 0; border-left: 1px solid #cccccc; border-bottom: 1px solid #cccccc; border-right: 1px solid #cccccc; border-bottom-right-radius: 5px; border-bottom-left-radius: 5px; mso-line-height-rule: exactly" height="5" bgcolor="#ffffff"> </td>
</tr>
</tbody>
</table> </td>
</tr>
<tr>
<td id="footer-pattern" style="padding: 0; border-collapse: collapse; padding: 12px 20px">
<table id="footer-pattern-container" cellspacing="0" cellpadding="0" border="0" style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0">
<tbody>
<tr>
<td id="footer-pattern-mobile-separated-links" class="mobile-resize-text" width="100%" colspan="2" style="padding: 0; border-collapse: collapse; color: #999999; font-size: 12px; line-height: 18px; font-family: Arial, sans-serif; mso-line-height-rule: exactly; mso-text-raise: 2px"> Get Jira notifications on your phone! Download the Jira Cloud app for <a href="https://play.google.com/store/apps/details?id=com.atlassian.android.jira.core&referrer=utm_source%3DNotificationLink%26utm_medium%3DEmail" style="color: #3b73af; text-decoration: none">Android</a> or <a href="https://itunes.apple.com/app/apple-store/id1006972087?pt=696495&ct=EmailNotificationLink&mt=8" style="color: #3b73af; text-decoration: none">iOS</a>
<hr> </td>
</tr>
<tr>
<td id="footer-pattern-text" class="mobile-resize-text" width="100%" style="padding: 0; border-collapse: collapse; color: #999999; font-size: 12px; line-height: 18px; font-family: Arial, sans-serif; mso-line-height-rule: exactly; mso-text-raise: 2px"> This message was sent by Atlassian Jira <span id="footer-build-information">(v1001.0.0-SNAPSHOT#100082-<span title="f0e0ddf156004ee4d06398c3a7e3bc01cd95c523" data-commit-id="f0e0ddf156004ee4d06398c3a7e3bc01cd95c523}">sha1:f0e0ddf</span>)</span> </td>
<td id="footer-pattern-logo-desktop-container" valign="top" style="padding: 0; border-collapse: collapse; padding-left: 20px; vertical-align: top">
<table style="border-collapse: collapse; mso-table-lspace: 0; mso-table-rspace: 0">
<tbody>
<tr>
<td id="footer-pattern-logo-desktop-padding" style="padding: 0; border-collapse: collapse; padding-top: 3px; opacity: 0.150"> <img id="footer-pattern-logo-desktop" src="cid:jira-generated-image-static-footer-desktop-logo-59fd49c9-9c1c-4d83-9125-7eee4323ac72" alt="Atlassian logo" title="Atlassian logo" width="192" height="24" class="image_fix"> </td>
</tr>
</tbody>
</table> </td>
</tr>
</tbody>
</table> </td>
</tr>
</tbody>
</table>
<img src="https://u4043402.ct.sendgrid.net/wf/open?upn=YNXLe5Uzuivj8jGpuXra04BSJ-2BS7raa1puTAtyVUP-2F0UG25sB-2BHToWWBMcbXwnNUY1xCsMgdXnQn1rXAlopW223ZLRCHCvTMaUH-2Bja2xOGjMa-2FdfMDllhJZQynArhdVB74n2dV0alvDj28OmKeNyxiqt9XXlWyrtgNtP4zfMqFhaMeUS5ElRDQIX6uzVhIkx0qPNg6-2BhsTl2CZds2GZBlEURRlqh15xX3Q10FV2eNij-2BxRqlZdvVy8TGo8VXYQTMH3eLgSlD-2F-2BCS13-2FHN-2Fk5lOx-2BHyDm21SyEs-2BoNIXKUjbsveWCjGb8wT4ftlM-2Bw1sRJZGZMG-2F9ASS-2BufsgO15UjCnj2RsE1D-2FQ1o4q-2BKIzv3nR-2BxaRP8d1kIcQDjFTd3Ub2cS9cLtFtpTiuKaC7FBo07LZ-2BxtJZ5hg0ZfJmNbr4qbNTq00SGsEMr8XF1cKj8u7s3ucE8vcFDFmEkn25phxwQ-3D-3D" alt="" width="1" height="1" border="0" style="height:1px !important;width:1px !important;border-width:0 !important;margin-top:0 !important;margin-bottom:0 !important;margin-right:0 !important;margin-left:0 !important;padding-top:0 !important;padding-bottom:0 !important;padding-right:0 !important;padding-left:0 !important;"/>
</body>
</html>