title: Encode interval as string for intersection query
body: <p>The goal is to check if two intervals intersect one another. Easy... right? Just plug this guy in and we can move on?</p>
  <pre class="lang-js prettyprint-override"><code>intersects = itemStart &lt; queryEnd &amp;&amp; queryStart &lt; itemEnd
  </code></pre>
  <p>Not so fast, we have the following constraints:</p>
  <ul>
  <li>We cannot use the candidate item's interval directly during the intersection check. We must pre-process the interval <code>[itemStart, itemEnd] =&gt; encodedItem</code>. The encoded item interval must be either a number or a string. We can however use the <code>[queryStart, queryEnd]</code> separately or not during the check.</li>
  <li>When performing the intersection check we are limited to the following operations: <code>beginsWith</code>, <code>between</code>. No further boolean operators can be applied. (These are limitations of <a href="https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/LegacyConditionalParameters.KeyConditions.html" rel="nofollow noreferrer">dynamodb</a>).
  <ul>
  <li><code>beginsWith(a, b)</code> checks whether string a starts with string b.</li>
  <li><code>between(a, b, c)</code> checks whether a is between b and c. Works with strings and numbers.</li>
  </ul>
  </li>
  <li>The start and end values of the items are in the range <code>[0, 3254778254386]</code>.</li>
  </ul>
  <p>In summary, the final intersection check must take the form of one of these two:</p>
  <pre class="lang-js prettyprint-override"><code>intersects = between(encodedItem, encodedQueryStart, encodedQueryEnd)
  </code></pre>
  <pre class="lang-js prettyprint-override"><code>intersects = beginsWith(encodedItem, encodedQuery)
  </code></pre>
  <p>Perhaps there is a mathematical proof that flattening the 2 dimensional interval into 1 dimension prevents us from inspecting whether the intervals intersect.</p>
  <hr />
  <h3 id="the-actual-goal-l5kk">The actual goal</h3>
  <p>While I am interested in random string problems as a pastime, there is a real world problem underlying this one. I am trying to perform date range intersection queries on a key value database, in this case dynamodb</p>
  <hr />
  <h3 id="what-ive-tried-so-far-mrmm">What I've tried so far</h3>
  <p><strong>Z-Ordering</strong></p>
  <p>I have been looking into geospatial indexes and Z-Ordering which has given me some faith that this is possible. <a href="https://aws.amazon.com/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1/" rel="nofollow noreferrer">[0]</a><a href="https://en.wikipedia.org/wiki/Geohash" rel="nofollow noreferrer">[1]</a><a href="https://aws.amazon.com/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-2/" rel="nofollow noreferrer">[2]</a><a href="https://firebase.google.com/docs/firestore/solutions/geoqueries" rel="nofollow noreferrer">[3]</a> With Z-ordering you can work out if a query interval contains another by interleaving the interval into a string.</p>
  <p>e.g.</p>
  <pre><code>            itemA = { start: 123, end: 456 }
       encodedItemA = &quot;142536&quot;
              itemB = { start: 111, end: 115 }
       encodedItemB = &quot;111115&quot;
              query = { start: 110, end: 119 }
  encodedQueryStart = &quot;111100&quot; // interleave query.start with itself
    encodedQueryEnd = &quot;111199&quot; // interleave query.end with itself
  </code></pre>
  <p>Once this preprocessing is done I can do</p>
  <pre><code>isContained = between(encodedItem, encodedQueryStart, encodedQueryEnd)
  isContained = between(&quot;142536&quot;, &quot;111100&quot;, &quot;111199&quot;) // returns false ✅
  isContained = between(&quot;111115&quot;, &quot;111100&quot;, &quot;111199&quot;) // returns true ✅
  </code></pre>
  <p>However, &quot;isContained&quot; is not the same as &quot;intersects&quot;.</p>
  <p><strong>Redundancy</strong></p>
  <p>The other thing I've explored is expanding every item so that it is no longer an interval but represented by many points facilitating prefix search. e.g.</p>
  <pre><code>itemA = { start: 123, end: 456 } is inserted as 334 rows:
             itemA1 = 123
             itemA2 = 124
                ...
             itemAN = 456
  itemB = { start: 111, end: 115 } is inserted as 5 rows:
             itemB1 = 111
             itemB2 = 112
                ...
             itemBN = 115
  query = { start: 110, end: 119 }
  encodedQuery = commonPrefix(query.start, query.end) = &quot;11&quot;
  intersects = beginsWith(&quot;111&quot;, &quot;11&quot;) // returns false ✅
  intersects = beginsWith(&quot;123&quot;, &quot;11&quot;) // returns true ✅
  </code></pre>
  <p>This comes with its own trade offs.</p>
  <hr />
  <p>Is there any other clever wizardry I could try to make this work? </p>