<!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>created</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-df383bd3-32ae-400c-b90a-ef3cf9453f06" 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">Issue Type:</th>
<td class="has-icon" style="padding: 0; border-collapse: collapse; font: normal 14px/20px Arial, sans-serif; padding: 2px 0 2px 5px; vertical-align: top"> <img src="cid:jira-generated-image-avatar-df383bd3-32ae-400c-b90a-ef3cf9453f06" height="16" width="16" border="0" align="absmiddle" alt="Bug" style="vertical-align: text-bottom"> Bug </td>
</tr>
<tr>
<th style="color: #707070; font: normal 14px/20px Arial, sans-serif; text-align: left; vertical-align: top; padding: 2px 0">Assignee:</th>
<td style="padding: 0; border-collapse: collapse; font: normal 14px/20px Arial, sans-serif; padding: 2px 0 2px 5px; vertical-align: top"> Unassigned </td>
</tr>
<tr>
<th style="color: #707070; font: normal 14px/20px Arial, sans-serif; text-align: left; vertical-align: top; padding: 2px 0">Created:</th>
<td style="padding: 0; border-collapse: collapse; font: normal 14px/20px Arial, sans-serif; padding: 2px 0 2px 5px; vertical-align: top"> 08/Mar/2018 17:20 PM </td>
</tr>
<tr>
<th style="color: #707070; font: normal 14px/20px Arial, sans-serif; text-align: left; vertical-align: top; padding: 2px 0">Priority:</th>
<td class="has-icon" style="padding: 0; border-collapse: collapse; font: normal 14px/20px Arial, sans-serif; padding: 2px 0 2px 5px; vertical-align: top"> <img src="cid:jira-generated-image-static-major-177dc6c0-ad30-4da4-af76-6f81709c82a0" height="16" width="16" border="0" align="absmiddle" alt="Major" style="vertical-align: text-bottom"> Major </td>
</tr>
<tr>
<th style="color: #707070; font: normal 14px/20px Arial, sans-serif; text-align: left; vertical-align: top; padding: 2px 0">Reporter:</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"> <p style="margin-top:0;margin-bottom:10px;; margin: 10px 0 0; margin-top: 0">Line 1191 of hibernate-orm\hibernate-core\src\main\java\org\hibernate\engine\spi\ActionQueue.java in the function <tt>sort(List<AbstractEntityInsertAction> insertions)</tt> is:</p>
<div class="code panel" style="border-width: 1px;; border: 1px solid #cccccc; background: #f5f5f5; font-size: 12px; line-height: 1.333; font-family: monospace; border: 1px solid #cccccc; -moz-border-radius: 3px; border-radius: 3px; margin: 9px 0">
<div class="codeContent panelContent" style="padding: 9px 12px">
<pre class="code-java" style="margin: 10px 0 0; margin-top: 0; max-height: 30em; overflow: auto; white-space: pre-wrap; word-wrap: normal">
<span class="code-object" style="color: #910091">long</span> maxIterations = latestBatches.size() * 2;
</pre>
</div>
</div> <p style="margin-top:0;margin-bottom:10px;; margin: 10px 0 0">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):</p>
<div class="code panel" style="border-width: 1px;; border: 1px solid #cccccc; background: #f5f5f5; font-size: 12px; line-height: 1.333; font-family: monospace; border: 1px solid #cccccc; -moz-border-radius: 3px; border-radius: 3px; margin: 9px 0">
<div class="codeContent panelContent" style="padding: 9px 12px">
<pre class="code-java" style="margin: 10px 0 0; margin-top: 0; max-height: 30em; overflow: auto; white-space: pre-wrap; word-wrap: normal">
}
<span class="code-keyword" style="color: #000091">while</span> ( !sorted && iterations <= maxIterations);
<span class="code-keyword" style="color: #000091">if</span> ( iterations > maxIterations ) {
LOG.warn( <span class="code-quote" style="color: #009100">"The batch containing "</span> + latestBatches.size() + <span class="code-quote" style="color: #009100">" statements could not be sorted after "</span> + maxIterations + <span class="code-quote" style="color: #009100">" iterations. "</span> +
<span class="code-quote" style="color: #009100">"This might indicate a circular entity relationship."</span> );
}
</pre>
</div>
</div> <p style="margin-top:0;margin-bottom:10px;; margin: 10px 0 0">The formula <tt>long maxIterations = latestBatches.size() * 2</tt> assumes that the sorting algorithm in use is O(N). This is impossible – the optimum possible performance for any general search algorithm is O(N logN). I am uncertain whether the search algorithm in use here has O(N logN) performance (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).</p> <p style="margin-top:0;margin-bottom:10px;; margin: 10px 0 0">I have a (complex and currently unready for submission) test case with latestBatches.size() = 10 which requires maxIterations >= 28 to be sorted correctly – 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 for latestBatches.size() = 8 to 16 – once I find some I will convert this into a test case 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.</p> <p style="margin-top:0;margin-bottom:10px;; margin: 10px 0 0"><span class="error">[FYI, Optimal searching algorithms for sorting a partially-ordered set whose can be found at https://en.wikipedia.org/wiki/Topological_sorting -- apparently they are linear in the number of node plus number of links of the graph for the partially ordered set, which means they are potentially either O(N logN) or O(N^2) in the number of nodes, depending on how dense the links are.]</span></p> <p style="margin-top:0;margin-bottom:10px;; margin: 10px 0 0">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_INSTERTS 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 may 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.</p> <p style="margin-top:0;margin-bottom:10px;; margin: 10px 0 0">An even better behavior (consider this an enhancement suggestion) would be to use something like <a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" class="external-link" rel="nofollow" style="color: #3b73af; text-decoration: none">https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm</a> 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).</p> </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-9494e127-5f86-4843-a962-e44765ebe815" 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-e6edacc6-4207-40e8-b30c-29b3a0558ba2" 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-2Fk5lP-2BGhCO1g5wTRf2sfIiE9Dy8MrqYAE2uRaS9sS-2FmgQEu99cZVPqHi3tPrN4nV8VXLHOac5GrdqhPC-2BGAkob-2Bnwqq9m9H4yoEicwl4KwvHUDpVtw7FX6SfTJ-2FN1Tny8Z2nl4DI-2F2oXAVaBYGbP89jfBP7GFnglsQO0kza-2BtqiSkj45DlhHoVNcbIYjiFzrAJQ2g-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>