Know Your Indices
Tags: indexing, performance, sql, practice
Published: 2021-06-25 10:43:36

<p style="margin-top: 16px;">
  This is the first in a pair of articles on SQL indices.
</p>

<h1 style="margin-top:16px">
  <span style="font-size:16pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#2e74b5"><span style="font-weight:normal">Part 1 - Know your indices</span></span></span></span></span>
</h1>

<p style="margin-bottom:11px">
   
</p>

<h2 style="margin-top:3px">
  <span style="font-size:13pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#2e74b5"><span style="font-weight:normal">What is an index, anyway?</span></span></span></span></span>
</h2>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Picture the last time you went to a library. Typically they have books sorted by subject matter (and then author and title), and each shelf has an end-plate with a code describing the subject of its books. If you wanted to collect books of a certain subject, instead of walking across every aisle and reading the inside cover of every book, you could head straight for the bookshelf labelled with your desired subject matter and choose your books. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">A SQL index has the same general function: improving performance by giving a quick reference to the value of fields for each row in a table. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Setting up indices is one of the main steps in preparing your classes for optimal SQL performance. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">In this article, we’ll cover:</span></span></span>
</p>

  1. <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">What is an index and why/when should I use them?</span></span></span>
  2. <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">What types of indices exist and which scenarios are they ideal for?</span></span></span>
  3. <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">What does an index look like?</span></span></span>
  4. <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">How do I create one?</span></span></span>
<li style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">And when I have indices, what do I do with them?</span></span></span>
</li>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">I will be referring to classes from our Sample schema. These are available through the following Github repository, and they are also provided in the Samples namespace in Caché and Ensemble installations:</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <a href="https://github.com/intersystems/Samples-Data"><span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">https://github.com/intersystems/Samples-Data</span></span></span></a>
</p>

<p style="margin-bottom:11px">
   
</p>

<h2 style="margin-top:3px">
  <span style="font-size:13pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#2e74b5"><span style="font-weight:normal">The basics</span></span></span></span></span>
</h2>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">You can index any persistent property and any property that can be reliably computed from persistent data.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Say we want to index the property TaxID in Sample.Company. In Studio or Atelier, we would add the following to the class definition:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">                <span style="font-family:Courier New,Courier,monospace;"><span style="color:navy">Index </span><span style="color:black">TaxIDIdx On TaxID</span><span style="color:black">;</span></span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">The equivalent DDL SQL statement would look something like this:</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">                <span style="font-family:Courier New,Courier,monospace;">CREATE INDEX TaxIDIdx ON Sample.Company (TaxID); </span></span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">The default global index structure is as follows:</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">               <span style="font-family:Courier New,Courier,monospace;"> ^Sample.CompanyI("TaxIDIdx</span></span><span style="font-family:Courier New,Courier,monospace;"> <span style="color:black">",&lt;TaxIDValueAtRowID>,&lt;RowID>) = ""</span></span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">Note that there are fewer subscripts to read than fields in a typical data global. </span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">Consider the query “<span style="font-family:Courier New,Courier,monospace;">SELECT Name,TaxID FROM Sample.Company WHERE TaxID = 'J7349'</span>”. It’s logically straightforward, and the query plan for executing this query reflects this:</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

 ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mb6x6a8ebv1tfy41isj4.png)

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">This plan essentially says we check the index global for rows with the given TaxID value, then refer back to the data global (“master map”) to retrieve the matching row. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Now consider the same query <i>without </i>an index on TaxIDX. The resulting query plan is, as expected, less efficient:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/k9uvode8jaqe4fq4zbmf.png) 

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Without indices, IRIS's underlying query execution relies on reading into memory and applying the WHERE clause’s condition to each row of the table – and since we would not logically expect any company to share a TaxID, we’re doing all this work for just one row!</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Of course, having indices means having index<i> and </i>row data on disk. Depending on what we have a condition on and how much data our table contains, this can prove to have its own challenges when we create and populate an index. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">So when do we add an index to a property? </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">The blanket case is when we frequently condition on a property. Some examples are identifying information such as a person’s SSN or a banking account number. You can also consider birth dates or an account’s funds.  Going back to Sample.Company, perhaps the class would benefit from indexing property Revenue if we wanted to collect data on high-earning organizations. Conversely, properties we’re unlikely to condition on are less fitting to be indexed: say a company slogan or description. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Simple – except we must also consider which type of index is best!</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<h2 style="margin-top:3px">
  <span style="font-size:13pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#2e74b5"><span style="font-weight:normal">Types of Indices</span></span></span></span></span>
</h2>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">There are six major types of indices I’ll go over here: standard, bitmap, compound, collection, bitslice, and data. I’ll also touch briefly on iFind indices, which are based on streams. There are possible overlaps here, and we’ve already touched on standard indices with the example above. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">I will share examples on how to create indices in your class definition, but adding new indices to a class is more involved than simply adding a line in your class definition. We’ll go over additional considerations in the next part. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Let’s use Sample.Person as an example. Note that Person has subclass Employee, which will be relevant in understanding some examples. Employee shares its data global storage with Person, and all of Person’s indices are inherited by Employee – this means Employee uses Person’s index global for these inherited indices. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">If you’re unfamiliar, here’s a general overview of these classes: Person has properties SSN, DOB, Name, Home (an embedded Address object containing State and City), Office (also an Address), and list collection FavoriteColors. Employee has additional property Salary (which I myself defined).</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<h3 style="margin-top:3px">
  <u><span style="font-size:12pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#1f4d78"><span style="font-weight:normal">Standard</span></span></span></span></span></u>
</h3>

<p style="margin-bottom:11px">
   
</p>

<p style="text-indent:.25in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Index </span><span style="color:black">DateIDX On DOB;</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Here I’m using ‘standard’ loosely to refer to indices that store the plain value of a property (as opposed to a binary representation). If the value is a string, it will be stored under some collation – SQLUPPER by default.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Compared to bitmap or bitslice indices, standard indices are more human-readable and relatively effortless to maintain. We have one global node for each row in the table.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Below is how DateIDX is stored at a global level. </span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="text-indent:.25in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("DateIDX",51274,100115)="~Sample.Employee~" ; Date is 05/20/81</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Note the first subscript after the index’s name is the date value, the last subscript is the ID of the Person with that DOB, and the value stored at this global node indicates that this Person is also a member of the subclass Sample.Employee. If this Person were not a member of any subclass, the value at the node would be an empty string. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">This base structure will be consistent with most non-bit indices, where indices on more than one property create more subscripts in the global, and having more than one value stored at the node produces a $listbuild object, for example:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">                <span style="font-family:Courier New,Courier,monospace;">^Package.ClassI(IndexName,IndexValue1,IndexValue2,IndexValue3,RowID) = $lb(SubClass,DataValue1,DataValue2)</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="text-indent:.25in; margin-bottom:11px">
   
</p>

<h3 style="margin-top:3px">
  <u><span style="font-size:12pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#1f4d78"><span style="font-weight:normal">Bitmap – A bitwise representation of the set of IDs corresponding to a property value.</span></span></span></span></span></u>
</h3>

<p style="margin-bottom:11px">
   
</p>

<p style="text-indent:.25in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Index </span><span style="color:black">HomeStateIDX On Home.State [ </span><span style="color:navy">Type </span><span style="color:black">= bitmap];</span></span></span></span>
</p>

<p style="text-indent:.25in; margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Bitmap indices are stored per unique value as opposed to standard indices, which are stored per row.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Going further into the example above, let’s say the Person with ID 1 lives in Massachusetts, ID 2 in New York, ID 3 in Massachusetts, and ID 4 in Rhode Island. HomeStateIDX is essentially stored as follows:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<table>
  <tr>
    <td>
      ID
    </td>
    
    <td>
      1
    </td>
    
    <td>
      2
    </td>
    
    <td>
      3
    </td>
    
    <td>
      4
    </td>
    
    <td>
      (…)
    </td>
  </tr>
  
  <tr>
    <td>
      (…)
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
      -
    </td>
  </tr>
  
  <tr>
    <td>
      MA
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
    
    <td>
      -
    </td>
  </tr>
  
  <tr>
    <td>
      NY
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
      -
    </td>
  </tr>
  
  <tr>
    <td>
      RI
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
      -
    </td>
  </tr>
  
  <tr>
    <td>
      (…)
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
      -
    </td>
  </tr>
</table>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">If we wanted a query to return data from people living in New England, the system performs a bitwise OR on the bitmap index’s relevant rows. It’s quick to see that we must load into memory Person objects with ID 1, 3, and 4 at the very least.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Bitmaps can be efficient for AND, RANGE, and OR operators in your WHERE clauses.  </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">While there is no official cap of how many unique values you can have for a property before a bitmap index will be less efficient than a standard index, the general rule of thumb is up to about 10,000 distinct values. So, while a bitmap index may be effective on a US state, a US city or county bitmap index would not be as useful. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Another concept to consider is storage efficiency. If you’re planning on adding and removing rows from your table frequently, your bitmap index’s storage can become less efficient. Consider the example above: say we removed many rows for whatever reason, and we no longer have people in our table who live in less populated states such as Wyoming or North Dakota. The bitmap thus has several rows with only zeroes. On the other side of the coin, creating new rows on large tables can eventually become slower as large bitmap storage must accommodate more unique values. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">In these examples, I have about 150,000 rows in Sample.Person. Each global node stores up to 64,000 IDs, so the bitmap index global at value MA is split into three parts:</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">      ^Sample.PersonI("HomeStateIDX"," MA",1)=$zwc(135,7992)_$c(0,(...))</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("HomeStateIDX"," MA",2)=$zwc(404,7990,(…))</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("HomeStateIDX"," MA",3)=$zwc(132,2744)_$c(0,(…))</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><b>Special case: Extent Bitmap</b>  </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">An extent bitmap, often named $&lt;ClassName>, is a bitmap index on the IDs of a class – this gives IRIS a quick way of knowing whether a row exists and can be helpful for COUNT queries or queries on subclasses. These indices are generated automatically when a bitmap index is added to the class; you can also manually create a bitmap extent index in a class definition as follows:</span></span></span>
</p>

<p style="margin-left:48px; margin-bottom:11px">
  <br /><span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Index </span><span style="color:black">Company [ </span><span style="color:navy">Extent</span><span style="color:black">, </span><span style="color:navy">SqlName </span><span style="color:black">= </span><span style="color:green">"$Company"</span><span style="color:black">, </span><span style="color:navy">Type </span><span style="color:black">= bitmap ];</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">Or via DDL keyword BITMAPEXTENT:</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">CREATE BITMAPEXTENT INDEX "$Company" ON TABLE Sample.Company </span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<h3 style="margin-top:3px">
  <u><span style="font-size:12pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#1f4d78"><span style="font-weight:normal">Compound – Indices based on two or more properties</span></span></span></span></span></u>
</h3>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Index </span><span style="color:black">OfficeAddrIDX On (Office.City, Office.State);</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">The general use case of compound indices is having frequent queries conditioning on two or more properties. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">The order of properties in a compound index matters due to how the index is stored on a global level. Having the more selective property first is more performance efficient because it will save initial disk reads of the index global; in this example, Office.City is first because there more unique cities than states in the US. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Having a less selective property first is more space efficient. In terms of global structure, the index tree would be more balanced were State to be first. Think about it: each state contains plenty of cities, but some city names belong to only one state.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">You can also consider whether you’d expect to run frequent queries conditioning on only one of either property – this can save you from defining yet another index. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Here’s an example of the compound index’s global structure:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="text-indent:.25in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("OfficeAddrIDX"," BOSTON"," MA",100115)="~Sample.Employee~"</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><b>Aside: Compound index or bitmap indices?</b> </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">For queries with conditions on multiple properties, you may also want to consider whether separate bitmap indices would be more effective than a single compound index. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Bitwise operations on two different indices may be more efficient provided that bitmap indices suit each property appropriately. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">You can also have compound bitmap indices – these are bitmap indices where the unique value is the intersection of the multiple properties you’re indexing on. Consider the table given in the previous section, but instead of states we have every possible pair of a state and city (e.g. Boston, MA, Cambridge, MA, even Los Angeles, MA, etc.), and cells get 1’s for rows that adhere to both values. </span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<h3 style="margin-top:3px">
  <u><span style="font-size:12pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#1f4d78"><span style="font-weight:normal">Collection – Indices based on collection properties</span></span></span></span></span></u>
</h3>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Here we have property FavoriteColors defined as follows:</span></span></span>
</p>

<p style="margin-left:48px; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Property </span><span style="color:black">FavoriteColors </span><span style="color:navy">As list Of %String</span><span style="color:black">;</span></span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">With each of the following indices defined for demonstration purposes:</span></span></span>
</p>

<p style="margin-left:48px; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Index </span><span style="color:black">fcIDX1 On FavoriteColors(ELEMENTS);</span><br /><br /><span style="color:navy">Index </span><span style="color:black">fcIDX2 On FavoriteColors(KEYS);</span></span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Here I’m using ‘collection’ to refer more broadly to single-cell properties containing more than one value. List Of and Array Of properties are relevant here, and if you want, even delimited strings. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Collection properties are automatically parsed to build their indices. For delimited properties, say a phone number, you’d need to define this method, &lt;PropertyName>BuildValueArray(value, .valueArray), explicitly. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Given the above example for FavoriteColors, fcIDX1 would look something like this for a Person with favorite colors blue and white:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-left:48px; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("fcIDX1"," BLUE",100115)="~Sample.Employee~"</span></span></span>
</p>

<p style="margin-left:48px; margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">(…) </span></span></span>
</p>

<p style="margin-left:48px; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("fcIDX1"," WHITE",100115)="~Sample.Employee~"</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">fcIDX2 would look like:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">      <span style="font-family:Courier New,Courier,monospace;">   ^Sample.PersonI("fcIDX2",1,100115)="~Sample.Employee~"       </span></span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("fcIDX2",2,100115)="~Sample.Employee~"</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">In this case, since FavoriteColors is a List collection, an index based on its keys is less useful than an index based on its elements. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Please refer to our documentation for more in-depth considerations of creating and managing indices on collection properties:</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span class="MsoHyperlink" style="color:#0563c1"><span style="text-decoration:underline"><a href="https://docs.intersystems.com/latest/csp/docbook/DocBook.UI.Page.cls?KEY=GSQLOPT_indices#GSQLOPT_indices_collections">https://docs.intersystems.com/latest/csp/docbook/DocBook.UI.Page.cls?KEY=GSQLOPT_indices#GSQLOPT_indices_collections</a></span></span> </span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<h3 style="margin-top:3px">
  <u><span style="font-size:12pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#1f4d78"><span style="font-weight:normal">Bitslice – Bitmap representation of the bit string representation of numeric data</span></span></span></span></span></u>
</h3>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-left:24px; margin-bottom:11px">
  <br /><span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Index </span><span style="color:black">SalaryIDX On Salary [ </span><span style="color:navy">Type </span><span style="color:black">= bitslice ]; //In Sample.Employee</span></span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Unlike bitmap indices, which contain flags representing which rows contain a specific value, bitslice indices first convert numeric values from decimal to binary, then create a bitmap on each digit of the binary value. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Let’s take the example above and, for realism’s sake, simplify Salary as being in units of $1000 – so If an employee’s salary is stored as 65, it is understood to represent $65,000.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Say we have Employee with ID 1 who has Salary 15, ID 2 Salary 40, ID 3 Salary 64, and ID 4 Salary 130. The corresponding bit values are:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<table>
  <tr>
    <td>
      15
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
      1
    </td>
    
    <td>
      1
    </td>
    
    <td>
      1
    </td>
  </tr>
  
  <tr>
    <td>
      40
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
  </tr>
  
  <tr>
    <td>
      64
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
  </tr>
  
  <tr>
    <td>
      130
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
    </td>
    
    <td>
      1
    </td>
    
    <td>
    </td>
  </tr>
</table>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Our bit string spans over 8 digits. The corresponding bitmap representation – the bitslice index values – is essentially stored as follows:</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",1,1) = "1000" ; Row 1 has value in 1’s place</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",2,1) = "1001" ; Rows 1 and 4 have values in 2’s place</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",3,1) = "1000" ; Row 1 has value in 4’s place</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",4,1) = "1100" ; Rows 1 and 2 have values in 8’s place</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",5,1) = "0000" ; etc…</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",6,1) = "0100"</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",7,1) = "0010"</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("SalaryIDX",8,1) = "0001"</span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Note that operations modifying Sample.Employee or its rows’ salaries, i.e. INSERTs, UPDATES, and DELETEs, now require each of these global nodes, or bitslices, to be updated. Adding a bitslice index to multiple properties in a table or a frequently modified property can have performance risks. In general, maintaining a bitslice index is more costly than maintaining standard or bitmap indices. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Bitslice indices are highly specialized and thus have specific use cases: queries that need to perform aggregate calculations, e.g. SUM, COUNT, or AVG. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">In addition, they can only be effectively used on numeric values – character strings are converted to a binary 0.</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Note that if the data table, as opposed to indices, must be read to check a query’s condition, bitslice indices will not be chosen to execute the query. Let’s say Sample.Person does not have an index on Name. If we were to calculate the average salary of employees with the last name Smith – “<span style="font-family:Courier New,Courier,monospace;">SELECT AVG(Salary) FROM Sample.Employee WHERE Name %STARTSWITH 'Smith,' </span>“ – we would need to read data rows to apply the WHERE condition, and thus the bitslice index would not be used in practice. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">There are similar storage concerns for bitslice and bitmap indices on tables where rows are frequently created or removed. </span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<h3 style="margin-top:3px">
  <u><span style="font-size:12pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#1f4d78"><span style="font-weight:normal">Data - Indices with data stored at their global nodes. </span></span></span></span></span></u>
</h3>

<p style="margin-bottom:11px; margin-left:48px">
   
</p>

<p style="text-indent:.25in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%"><span style="color:navy">Index </span><span style="color:black">QuickSearchIDX On Name [ </span><span style="color:navy">Data </span><span style="color:black">= (SSN, DOB, Name) ];</span></span></span></span>
</p>

<p style="text-indent:.25in; margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">In several of the previous examples, you may have observed the string “~Sample.Employee~” stored as the value at the node itself. Recall that Sample.Employee inherits indices from Sample.Person. When we query on Employees in particular, we read the value at index nodes matching our property condition to check that said Person is also an Employee. </span></span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">We can also explicitly define what values to store. Having data defined at your index global nodes can save reads of the data global altogether; this can be useful for frequent selective or ordered queries. </span></span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span style="color:black">Take the above index as an example. If we wanted to pull identifying information about a person given all or part of their name (e.g. to search for clients’ information in a front-desk application), we could have a query such as “<span style="font-family:Courier New,Courier,monospace;">SELECT SSN, Name, DOB FROM Sample.Person WHERE Name %STARTSWITH 'Smith,J' ORDER BY Name</span>”. Since our query conditions on Name and the values we’re retrieving are all contained within the QuickSearchIDX global nodes, we only need to read our I global to execute this query. </span></span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Note that data values cannot be stored with bitmap or bitslice indices. </span></span></span>
</p>

<p style="text-indent:.5in; margin-bottom:11px">
  <span style="font-family:Courier New,Courier,monospace;"><span style="font-size:11pt"><span style="line-height:107%">^Sample.PersonI("QuickSearchIDX"," LARSON,KIRSTEN A.",100115)=$lb("~Sample.Employee~","555-55-5555",51274,"Larson,Kirsten A.")</span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<h3 style="margin-top:3px">
  <u><span style="font-size:12pt"><span style="line-height:107%"><span style='font-family:"Calibri Light",sans-serif'><span style="color:#1f4d78"><span style="font-weight:normal">iFind Indices</span></span></span></span></span></u>
</h3>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">Ever heard of these? Neither have I. iFind indices are used on stream properties, but to use them you need to specify their names with keywords in the query. </span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif">I could explain more, but Kyle Baxter already has a helpful article on this:</span></span></span>
</p>

<p style="margin-bottom:11px">
  <span style="font-size:11pt"><span style="line-height:107%"><span style="font-family:Calibri,sans-serif"><span class="MsoHyperlink" style="color:#0563c1"><span style="text-decoration:underline"><a href="https://community.intersystems.com/post/free-text-search-way-search-your-text-fields-sql-developers-are-hiding-you">https://community.intersystems.com/post/free-text-search-way-search-your-text-fields-sql-developers-are-hiding-you</a></span></span>  </span></span></span>
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  See Part 2, on managing defined indices, <a href="https://community.intersystems.com/post/index-handling">here</a>.
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
  [EDIT 04/16/2020:  Adjustments for readability.]
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
   
</p>

<p style="margin-bottom:11px">
   
</p>