Repository: jtablesaw/tablesaw
Pull request #1097 (2022-04-04 18:18:42)

Boolean optimizations
Thanks for contributing.

- [x] Tick to sign-off your agreement to the [Developer Certificate of Origin (DCO) 1.1](https://developercertificate.org)

## Description

- Separated the data representation inside a BooleanColumn from the column itself, introducing an API for the data
- Created an implementation of the BooleanData interface that uses java.util.BitSets to hold the data
- Updated the Saw code to work with the new representation
- Added LZ4 compression support to Saw.
- Added tests and docs

## Testing

Did you add a unit test? Yes



Patch:
diff --git a/core/src/main/java/tech/tablesaw/api/BooleanColumn.java b/core/src/main/java/tech/tablesaw/api/BooleanColumn.java
index 7142e2d2..3135a35f 100644
--- a/core/src/main/java/tech/tablesaw/api/BooleanColumn.java
+++ b/core/src/main/java/tech/tablesaw/api/BooleanColumn.java
@@ -23,9 +23,7 @@ import it.unimi.dsi.fastutil.booleans.BooleanSet;
 import it.unimi.dsi.fastutil.bytes.Byte2IntMap;
 import it.unimi.dsi.fastutil.bytes.Byte2IntOpenHashMap;
 import it.unimi.dsi.fastutil.bytes.ByteArrayList;
-import it.unimi.dsi.fastutil.bytes.ByteComparators;
 import it.unimi.dsi.fastutil.bytes.ByteIterator;
-import it.unimi.dsi.fastutil.bytes.ByteListIterator;
 import it.unimi.dsi.fastutil.bytes.ByteOpenHashSet;
 import it.unimi.dsi.fastutil.bytes.ByteSet;
 import it.unimi.dsi.fastutil.ints.IntComparator;
@@ -39,12 +37,7 @@ import java.util.stream.Stream;
 import tech.tablesaw.columns.AbstractColumn;
 import tech.tablesaw.columns.AbstractColumnParser;
 import tech.tablesaw.columns.Column;
-import tech.tablesaw.columns.booleans.BooleanColumnType;
-import tech.tablesaw.columns.booleans.BooleanColumnUtils;
-import tech.tablesaw.columns.booleans.BooleanFillers;
-import tech.tablesaw.columns.booleans.BooleanFilters;
-import tech.tablesaw.columns.booleans.BooleanFormatter;
-import tech.tablesaw.columns.booleans.BooleanMapUtils;
+import tech.tablesaw.columns.booleans.*;
 import tech.tablesaw.filtering.BooleanFilterSpec;
 import tech.tablesaw.filtering.predicates.BytePredicate;
 import tech.tablesaw.selection.BitmapBackedSelection;
@@ -59,7 +52,8 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
         BooleanFilters {
 
   /** The data held by this column */
-  protected ByteArrayList data;
+  // protected ByteArrayList data;
+  BooleanData data;
 
   /** An IntComparator. The ints are row indexes */
   private final IntComparator comparator =
@@ -80,7 +74,12 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
    */
   private BooleanColumn(String name, ByteArrayList values) {
     super(BooleanColumnType.instance(), name, BooleanColumnType.DEFAULT_PARSER);
-    data = values;
+    data = new BitSetBooleanData(values);
+  }
+
+  public BooleanColumn(String name, BooleanData data) {
+    super(BooleanColumnType.BOOLEAN, name, BooleanColumnType.DEFAULT_PARSER);
+    this.data = data;
   }
 
   /** Returns {@code true} if b is the missing value indicator for this column type */
@@ -228,23 +227,13 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
   /** Returns the count of missing values in this column */
   @Override
   public int countMissing() {
-    int count = 0;
-    for (int i = 0; i < size(); i++) {
-      if (valueIsMissing(getByte(i))) {
-        count++;
-      }
-    }
-    return count;
+    return data.countMissing();
   }
 
   /** {@inheritDoc} */
   @Override
   public int countUnique() {
-    ByteSet count = new ByteOpenHashSet(3);
-    for (byte next : data) {
-      count.add(next);
-    }
-    return count.size();
+    return data.countUnique();
   }
 
   /** {@inheritDoc} */
@@ -358,19 +347,19 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
   /** {@inheritDoc} */
   @Override
   public BooleanColumn copy() {
-    return new BooleanColumn(name(), data.clone());
+    return new BooleanColumn(name(), data.copy());
   }
 
   /** {@inheritDoc} */
   @Override
   public void sortAscending() {
-    data.sort(ByteComparators.NATURAL_COMPARATOR);
+    data.sortAscending();
   }
 
   /** {@inheritDoc} */
   @Override
   public void sortDescending() {
-    data.sort(ByteComparators.OPPOSITE_COMPARATOR);
+    data.sortDescending();
   }
 
   /** {@inheritDoc} */
@@ -420,24 +409,12 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
 
   /** Returns the number of {@code true} elements in this column */
   public int countTrue() {
-    int count = 0;
-    for (byte b : data) {
-      if (b == BooleanColumnType.BYTE_TRUE) {
-        count++;
-      }
-    }
-    return count;
+    return data.countTrue();
   }
 
   /** Returns the number of {@code false} elements in this column */
   public int countFalse() {
-    int count = 0;
-    for (byte b : data) {
-      if (b == BooleanColumnType.BYTE_FALSE) {
-        count++;
-      }
-    }
-    return count;
+    return data.countFalse();
   }
 
   /** Returns the proportion of non-missing row elements that contain true */
@@ -471,29 +448,13 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
   /** {@inheritDoc} */
   @Override
   public Selection isFalse() {
-    Selection results = new BitmapBackedSelection();
-    int i = 0;
-    for (byte next : data) {
-      if (next == BooleanColumnType.BYTE_FALSE) {
-        results.add(i);
-      }
-      i++;
-    }
-    return results;
+    return data.isFalse();
   }
 
   /** {@inheritDoc} */
   @Override
   public Selection isTrue() {
-    Selection results = new BitmapBackedSelection();
-    int i = 0;
-    for (byte next : data) {
-      if (next == BooleanColumnType.BYTE_TRUE) {
-        results.add(i);
-      }
-      i++;
-    }
-    return results;
+    return data.isTrue();
   }
 
   /** {@inheritDoc} */
@@ -512,7 +473,11 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
   }
 
   /** Returns a ByteArrayList containing 0 (false), 1 (true) or Byte.MIN_VALUE (missing) */
-  public ByteArrayList data() {
+  public ByteArrayList toByteArrayList() {
+    return data.toByteArrayList();
+  }
+
+  public BooleanData data() {
     return data;
   }
 
@@ -567,7 +532,7 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
     System.arraycopy(data.toByteArray(), srcPos, dest, destPos, length);
 
     BooleanColumn copy = emptyCopy(size());
-    copy.data = new ByteArrayList(dest);
+    copy.data = new BitSetBooleanData(new ByteArrayList(dest));
     copy.setName(name() + " lag(" + n + ")");
     return copy;
   }
@@ -674,14 +639,7 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
   /** {@inheritDoc} */
   @Override
   public Selection asSelection() {
-    Selection selection = new BitmapBackedSelection();
-    for (int i = 0; i < size(); i++) {
-      byte value = getByte(i);
-      if (value == 1) {
-        selection.add(i);
-      }
-    }
-    return selection;
+    return data.asSelection();
   }
 
   /** {@inheritDoc} */
@@ -749,7 +707,7 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
   @Override
   public BooleanColumn removeMissing() {
     BooleanColumn noMissing = emptyCopy();
-    ByteListIterator iterator = byteListIterator();
+    ByteIterator iterator = byteIterator();
     while (iterator.hasNext()) {
       byte b = iterator.nextByte();
       if (!valueIsMissing(b)) {
@@ -796,18 +754,12 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
     return selection;
   }
 
-  /** Returns a byteListIterator, which allows iteration by byte (value) and int (index) */
-  private ByteListIterator byteListIterator() {
-    return data.iterator();
-  }
-
   /**
    * Returns a DoubleColumn containing the elements in this column, with true as 1.0 and false as
    * 0.0.
    */
   public DoubleColumn asDoubleColumn() {
     DoubleColumn numberColumn = DoubleColumn.create(this.name(), size());
-    ByteArrayList data = data();
     for (int i = 0; i < size(); i++) {
       numberColumn.set(i, data.getByte(i));
     }
@@ -910,4 +862,58 @@ public class BooleanColumn extends AbstractColumn<BooleanColumn, Boolean>
     }
     return output;
   }
+
+  /**
+   * Returns a byte representation of the true values, encoded in the format specified in {@link
+   * java.util.BitSet#toByteArray()}
+   */
+  public byte[] trueBytes() {
+    return data.trueBytes();
+  }
+
+  /**
+   * Returns a byte representation of the false values, encoded in the format specified in {@link
+   * java.util.BitSet#toByteArray()}
+   */
+  public byte[] falseBytes() {
+    return data.falseBytes();
+  }
+
+  /**
+   * Returns a byte representation of the missing values, encoded in the format specified in {@link
+   * java.util.BitSet#toByteArray()}
+   */
+  public byte[] missingBytes() {
+    return data.missingBytes();
+  }
+
+  /**
+   * Sets the true values in the data from a byte[] encoding
+   *
+   * @param encodedValues The true values encoded in the format specified in {@link
+   *     java.util.BitSet}
+   */
+  public void trueBytes(byte[] encodedValues) {
+    data.setTrueBytes(encodedValues);
+  }
+
+  /**
+   * Sets the false values in the data from a byte[] encoding
+   *
+   * @param encodedValues The false values encoded in the format specified in {@link
+   *     java.util.BitSet}
+   */
+  public void falseBytes(byte[] encodedValues) {
+    data.setFalseBytes(encodedValues);
+  }
+
+  /**
+   * Sets the missing values in the data from a byte[] encoding
+   *
+   * @param encodedValues The missing values encoded in the format specified in {@link
+   *     java.util.BitSet}
+   */
+  public void missingBytes(byte[] encodedValues) {
+    data.setMissingBytes(encodedValues);
+  }
 }
diff --git a/core/src/main/java/tech/tablesaw/columns/ColumnStats.java b/core/src/main/java/tech/tablesaw/columns/ColumnStats.java
new file mode 100644
index 00000000..1acce749
--- /dev/null
+++ b/core/src/main/java/tech/tablesaw/columns/ColumnStats.java
@@ -0,0 +1,4 @@
+package tech.tablesaw.columns;
+
+/** Collects and holds column stats for optimizations */
+public class ColumnStats {}
diff --git a/core/src/main/java/tech/tablesaw/columns/booleans/BitSetBooleanData.java b/core/src/main/java/tech/tablesaw/columns/booleans/BitSetBooleanData.java
new file mode 100644
index 00000000..836a6e0c
--- /dev/null
+++ b/core/src/main/java/tech/tablesaw/columns/booleans/BitSetBooleanData.java
@@ -0,0 +1,332 @@
+package tech.tablesaw.columns.booleans;
+
+import static tech.tablesaw.columns.booleans.BooleanColumnType.*;
+
+import it.unimi.dsi.fastutil.bytes.ByteArrayList;
+import it.unimi.dsi.fastutil.bytes.ByteIterator;
+import java.util.BitSet;
+import tech.tablesaw.selection.BitmapBackedSelection;
+import tech.tablesaw.selection.Selection;
+
+/**
+ * An implementation of BooleanData where the underlying representation uses the Java BitSet class
+ */
+public class BitSetBooleanData implements BooleanData {
+
+  /** A BitSet indicating the position of the true values in the data */
+  private BitSet trueValues = new BitSet();
+
+  /** A BitSet indicating the position of the false values in the data */
+  private BitSet falseValues = new BitSet();
+
+  /** A BitSet indicating the position of the missing values in the data */
+  private BitSet missingValues = new BitSet();
+
+  /** Constructs a BitSetBoolean data from three BitSets, one for each possible value */
+  public BitSetBooleanData(BitSet trueValues, BitSet falseValues, BitSet missingValues) {
+    this.trueValues = trueValues;
+    this.falseValues = falseValues;
+    this.missingValues = missingValues;
+  }
+
+  /**
+   * Constructs a BitSetBoolean data from the given ByteArrayList
+   *
+   * @param values The values must be encoded as 0, 1, or -128 (for missing)
+   */
+  public BitSetBooleanData(ByteArrayList values) {
+    for (int i = 0; i < values.size(); i++) {
+      if (i == BYTE_TRUE) trueValues.set(i);
+      else if (i == BYTE_FALSE) falseValues.set(i);
+      else if (i == MISSING_VALUE) missingValues.set(i);
+    }
+  }
+
+  public BitSetBooleanData() {}
+
+  /** {@inheritDoc} */
+  @Override
+  public int size() {
+    return Math.max(Math.max(trueValues.length(), falseValues.length()), missingValues.length());
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void add(byte b) {
+    int size = size();
+    if (b == BYTE_TRUE) {
+      trueValues.set(size);
+    } else if (b == BYTE_FALSE) {
+      falseValues.set(size);
+    } else if (b == MISSING_VALUE) {
+      missingValues.set(size);
+    }
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void clear() {
+    trueValues.clear();
+    falseValues.clear();
+    missingValues.clear();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void sortAscending() {
+    int t = trueValues.cardinality();
+    int f = falseValues.cardinality();
+    int m = missingValues.cardinality();
+    trueValues.clear();
+    falseValues.clear();
+    missingValues.clear();
+    missingValues.set(0, m);
+    falseValues.set(m, m + f);
+    trueValues.set(m + f, m + f + t);
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void sortDescending() {
+    int t = trueValues.cardinality();
+    int f = falseValues.cardinality();
+    int m = missingValues.cardinality();
+    trueValues.clear();
+    falseValues.clear();
+    missingValues.clear();
+    trueValues.set(0, t);
+    falseValues.set(t, t + f);
+    missingValues.set(t + f, m + f + t);
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public BooleanData copy() {
+    return new BitSetBooleanData(
+        (BitSet) trueValues.clone(), (BitSet) falseValues.clone(), (BitSet) missingValues.clone());
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public byte getByte(int i) {
+    if (trueValues.get(i)) return BYTE_TRUE;
+    if (falseValues.get(i)) return BYTE_FALSE;
+    return MISSING_VALUE;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int countFalse() {
+    return falseValues.cardinality();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int countTrue() {
+    return trueValues.cardinality();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int countMissing() {
+    return missingValues.cardinality();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int countUnique() {
+    boolean t = !trueValues.isEmpty();
+    boolean f = !falseValues.isEmpty();
+    boolean m = !missingValues.isEmpty();
+    if (m && f && t) return 3;
+    if ((m && f) || (m && t) || (t && f)) return 2;
+    if (m || f || t) return 1;
+    return 0;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public byte[] toByteArray() {
+    return toByteArrayList().toByteArray();
+  }
+
+  @Override
+  public ByteArrayList toByteArrayList() {
+    ByteArrayList arrayList = new ByteArrayList(new byte[size()]);
+    for (int i = 0; i < size(); i++) {
+      if (trueValues.get(i)) arrayList.set(i, BYTE_TRUE);
+      else if (missingValues.get(i)) arrayList.set(i, MISSING_VALUE);
+    }
+    return arrayList;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void set(int i, byte b) {
+    if (b == BYTE_TRUE) {
+      trueValues.set(i);
+      falseValues.clear(i);
+      missingValues.clear(i);
+    } else if (b == BYTE_FALSE) {
+      trueValues.clear(i);
+      falseValues.set(i);
+      missingValues.clear(i);
+    } else if (b == MISSING_VALUE) {
+      trueValues.clear(i);
+      falseValues.clear(i);
+      missingValues.set(i);
+    }
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public boolean isEmpty() {
+    return trueValues.isEmpty() && falseValues.isEmpty();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public boolean contains(byte b) {
+    if (b == BYTE_TRUE) {
+      return !trueValues.isEmpty();
+    }
+    if (b == BYTE_FALSE) {
+      return !falseValues.isEmpty();
+    }
+    if (b == MISSING_VALUE) {
+      return !missingValues.isEmpty();
+    }
+    throw new IllegalArgumentException(
+        "The value "
+            + b
+            + " is not a legal byte representation of a boolean value. Only 0, 1, and -1 are valid.");
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Selection asSelection() {
+    return isTrue();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Selection isFalse() {
+    Selection results = new BitmapBackedSelection();
+    int i = 0;
+    for (byte next : this) {
+      if (next == BYTE_FALSE) {
+        results.add(i);
+      }
+      i++;
+    }
+    return results;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Selection isTrue() {
+    Selection results = new BitmapBackedSelection();
+    int i = 0;
+    for (byte next : this) {
+      if (next == BYTE_TRUE) {
+        results.add(i);
+      }
+      i++;
+    }
+    return results;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Selection isMissing() {
+    Selection results = new BitmapBackedSelection();
+    int i = 0;
+    for (byte next : this) {
+      if (next == BYTE_FALSE) {
+        results.add(i);
+      }
+      i++;
+    }
+    return results;
+  }
+
+  @Override
+  public String toString() {
+    return this.getClass().getSimpleName()
+        + "{ size: "
+        + size()
+        + ", true: "
+        + trueValues.cardinality()
+        + ", false: "
+        + falseValues.cardinality()
+        + ", missing: "
+        + missingValues.cardinality()
+        + "}";
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public byte[] falseBytes() {
+    return falseValues.toByteArray();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public byte[] trueBytes() {
+    return trueValues.toByteArray();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public byte[] missingBytes() {
+    return missingValues.toByteArray();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void setTrueBytes(byte[] bytes) {
+    trueValues = BitSet.valueOf(bytes);
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void setFalseBytes(byte[] bytes) {
+    falseValues = BitSet.valueOf(bytes);
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public void setMissingBytes(byte[] bytes) {
+    missingValues = BitSet.valueOf(bytes);
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public ByteIterator iterator() {
+    return new BitSetByteIterator(this);
+  }
+
+  static class BitSetByteIterator implements ByteIterator {
+
+    final BitSetBooleanData data;
+
+    int current = -1;
+
+    BitSetByteIterator(BitSetBooleanData data) {
+      this.data = data;
+    }
+
+    @Override
+    public byte nextByte() {
+      current++;
+      if (data.trueValues.get(current)) return BYTE_TRUE;
+      if (data.falseValues.get(current)) return BYTE_FALSE;
+      return MISSING_VALUE;
+    }
+
+    @Override
+    public boolean hasNext() {
+      return current < data.size() - 1;
+    }
+  }
+}
diff --git a/core/src/main/java/tech/tablesaw/columns/booleans/BooleanData.java b/core/src/main/java/tech/tablesaw/columns/booleans/BooleanData.java
new file mode 100644
index 00000000..3d698559
--- /dev/null
+++ b/core/src/main/java/tech/tablesaw/columns/booleans/BooleanData.java
@@ -0,0 +1,120 @@
+package tech.tablesaw.columns.booleans;
+
+import it.unimi.dsi.fastutil.bytes.ByteArrayList;
+import it.unimi.dsi.fastutil.bytes.ByteIterable;
+import tech.tablesaw.selection.Selection;
+
+/** A container for boolean data */
+public interface BooleanData extends ByteIterable {
+
+  /** Returns the number of values in the data, including missing values */
+  int size();
+
+  /** Adds a boolean value represented as a byte, where 0=false, 1=true, and -1=missing */
+  void add(byte booleanValue);
+
+  /** Removes all data values */
+  void clear();
+
+  /** Returns a copy of this BooleanData object */
+  BooleanData copy();
+
+  /** Returns the value at i as a byte, where -1 represents missing values */
+  byte getByte(int i);
+
+  /** Returns the number of false values in the data * */
+  int countFalse();
+
+  /** Returns the number of true values in the data * */
+  int countTrue();
+
+  /** Returns the number of missing values in the data * */
+  int countMissing();
+
+  /**
+   * Returns the number of unique values in the data. There can only be 3 (true, false, and missing)
+   * *
+   */
+  int countUnique();
+
+  /** Sorts the data in-place in ascending order, with missing values first */
+  void sortAscending();
+
+  /** Sorts the data in-place in descending order, with missing values last */
+  void sortDescending();
+
+  /** Returns the data as a byte[] containing 0 and 1, with any missing values encoded as -128 */
+  byte[] toByteArray();
+
+  /**
+   * Returns the data as a ByteArrayList containing 0 and 1, with any missing values encoded as -128
+   */
+  ByteArrayList toByteArrayList();
+
+  /**
+   * Sets the value at position i to byte b
+   *
+   * @param i the 0-based index of the element in the data
+   * @param b the value to set, should be 0, 1, or -128 only
+   */
+  void set(int i, byte b);
+
+  /**
+   * Returns true if the data is empty, and false otherwise. Empty here means only missing values
+   */
+  boolean isEmpty();
+
+  /** Returns true if the value at b is true. */
+  boolean contains(byte b);
+
+  /** Returns a selection matching all the true values in the data */
+  Selection asSelection();
+
+  /** Returns a selection matching all the false values in the data */
+  Selection isFalse();
+
+  /** Returns a selection matching all the true values in the data */
+  Selection isTrue();
+
+  /** Returns a selection matching all the missing values in the data */
+  Selection isMissing();
+
+  /**
+   * Returns a byte representation of the true values, encoded in the format specified in {@link
+   * java.util.BitSet#toByteArray()}
+   */
+  byte[] falseBytes();
+
+  /**
+   * Returns a byte representation of the false values, encoded in the format specified in {@link
+   * java.util.BitSet#toByteArray()}
+   */
+  byte[] trueBytes();
+
+  /**
+   * Returns a byte representation of the missing values, encoded in the format specified in {@link
+   * java.util.BitSet#toByteArray()}
+   */
+  byte[] missingBytes();
+
+  /**
+   * Sets the true values in the data from a byte[] encoding
+   *
+   * @param bytes The true values encoded in the format specified in {@link java.util.BitSet}
+   */
+  void setTrueBytes(byte[] bytes);
+
+  /**
+   * Sets the false values in the data from a byte[] encoding
+   *
+   * @param bytes The false values encoded in the format specified in {@link java.util.BitSet}
+   */
+  void setFalseBytes(byte[] bytes);
+
+  /**
+   * Sets the missing values in the data from a byte[] encoding
+   *
+   * @param bytes The missing values encoded in the format specified in {@link java.util.BitSet}
+   */
+  void setMissingBytes(byte[] bytes);
+}
diff --git a/core/src/main/java/tech/tablesaw/selection/BitmapBackedSelection.java b/core/src/main/java/tech/tablesaw/selection/BitmapBackedSelection.java
index 2a05f24d..2a4ff1ae 100644
--- a/core/src/main/java/tech/tablesaw/selection/BitmapBackedSelection.java
+++ b/core/src/main/java/tech/tablesaw/selection/BitmapBackedSelection.java
@@ -209,6 +209,11 @@ public class BitmapBackedSelection implements Selection {
     return selection;
   }
 
+  /** Returns a Selection containing all indexes in the array */
+  protected static Selection fromBitmap(RoaringBitmap bitmap) {
+    return new BitmapBackedSelection(bitmap);
+  }
+
   /**
    * Returns a Selection containing all indexes in the range start (inclusive) to end (exclusive),
    */
diff --git a/core/src/main/java/tech/tablesaw/selection/Selection.java b/core/src/main/java/tech/tablesaw/selection/Selection.java
index 6998d603..1be5df79 100644
--- a/core/src/main/java/tech/tablesaw/selection/Selection.java
+++ b/core/src/main/java/tech/tablesaw/selection/Selection.java
@@ -15,6 +15,7 @@
 package tech.tablesaw.selection;
 
 import it.unimi.dsi.fastutil.ints.IntIterable;
+import org.roaringbitmap.RoaringBitmap;
 
 /**
  * A selection maintains an ordered set of ints that can be used to filter rows from a table or
@@ -98,6 +99,11 @@ public interface Selection extends IntIterable {
     return BitmapBackedSelection.with(rows);
   }
 
+  /** */
+  static Selection fromBitmap(RoaringBitmap bitmap) {
+    return BitmapBackedSelection.fromBitmap(bitmap);
+  }
+
   /**
    * Returns a Selection containing all indexes in the range start (inclusive) to end (exclusive),
    */
diff --git a/saw/pom.xml b/saw/pom.xml
index a74707c4..f563d615 100644
--- a/saw/pom.xml
+++ b/saw/pom.xml
@@ -89,7 +89,6 @@
       <artifactId>jackson-databind</artifactId>
     </dependency>
     <dependency>
-      <!-- Compression -->
       <groupId>org.iq80.snappy</groupId>
       <artifactId>snappy</artifactId>
       <version>0.4</version>
diff --git a/saw/src/main/java/tech/tablesaw/io/saw/ColumnMetadata.java b/saw/src/main/java/tech/tablesaw/io/saw/ColumnMetadata.java
index f6015c45..bc7f6fd3 100644
--- a/saw/src/main/java/tech/tablesaw/io/saw/ColumnMetadata.java
+++ b/saw/src/main/java/tech/tablesaw/io/saw/ColumnMetadata.java
@@ -16,6 +16,7 @@ package tech.tablesaw.io.saw;
 
 import com.google.common.annotations.Beta;
 import com.google.common.base.Objects;
+import tech.tablesaw.api.BooleanColumn;
 import tech.tablesaw.api.StringColumn;
 import tech.tablesaw.columns.Column;
 import tech.tablesaw.columns.strings.ByteDictionaryMap;
@@ -38,6 +39,11 @@ public class ColumnMetadata {
   private String stringColumnKeySize;
   private int nextStringKey;
 
+  // these attributes are specific to boolean columns
+  private int trueBytesLength;
+  private int falseBytesLength;
+  private int missingBytesLength;
+
   ColumnMetadata(Column<?> column) {
     this.id = SawUtils.makeName(column.name());
     this.name = column.name();
@@ -58,6 +64,13 @@ public class ColumnMetadata {
       }
     } else {
       stringColumnKeySize = "";
+
+      if (column instanceof BooleanColumn) {
+        BooleanColumn bc = (BooleanColumn) column;
+        trueBytesLength = bc.trueBytes().length;
+        falseBytesLength = bc.falseBytes().length;
+        missingBytesLength = bc.missingBytes().length;
+      }
     }
   }
 
@@ -122,4 +135,28 @@ public class ColumnMetadata {
   public int getCardinality() {
     return cardinality;
   }
+
+  /**
+   * For BooleanColumn only Returns the length of the byte array used for true values before it is
+   * compressed
+   */
+  public int getTrueBytesLength() {
+    return trueBytesLength;
+  }
+
+  /**
+   * For BooleanColumn only Returns the length of the byte array used for false values before it is
+   * compressed
+   */
+  public int getFalseBytesLength() {
+    return falseBytesLength;
+  }
+
+  /**
+   * For BooleanColumn only Returns the length of the byte array used for missing values before it
+   * is compressed
+   */
+  public int getMissingBytesLength() {
+    return missingBytesLength;
+  }
 }
diff --git a/saw/src/main/java/tech/tablesaw/io/saw/SawMetadata.java b/saw/src/main/java/tech/tablesaw/io/saw/SawMetadata.java
index dfa2da5a..31bb825f 100644
--- a/saw/src/main/java/tech/tablesaw/io/saw/SawMetadata.java
+++ b/saw/src/main/java/tech/tablesaw/io/saw/SawMetadata.java
@@ -47,7 +47,7 @@ public class SawMetadata {
     return SawMetadata.fromJson(new String(encoded, StandardCharsets.UTF_8));
   }
 
-  public SawMetadata(Table table, WriteOptions options) {
+  public SawMetadata(Table table, SawWriteOptions options) {
     this.tableMetadata = new TableMetadata(table);
     this.version = SAW_VERSION;
     this.compressionType = options.getCompressionType();
diff --git a/saw/src/main/java/tech/tablesaw/io/saw/SawReader.java b/saw/src/main/java/tech/tablesaw/io/saw/SawReader.java
index f74b3677..c3f0ac96 100644
--- a/saw/src/main/java/tech/tablesaw/io/saw/SawReader.java
+++ b/saw/src/main/java/tech/tablesaw/io/saw/SawReader.java
@@ -46,7 +46,7 @@ import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import java.util.concurrent.Future;
 import java.util.stream.Collectors;
-import net.jpountz.lz4.LZ4BlockInputStream;
+import net.jpountz.lz4.*;
 import org.iq80.snappy.SnappyFramedInputStream;
 import tech.tablesaw.api.BooleanColumn;
 import tech.tablesaw.api.DateColumn;
@@ -232,6 +232,12 @@ public class SawReader {
     if (sawMetadata.getCompressionType().equals(CompressionType.NONE)) {
       return new DataInputStream(fis);
     } else if (sawMetadata.getCompressionType().equals(CompressionType.LZ4)) {
+      // TODO: Figure out how to provide the pre-compression size of the byte array
+      //  so we can use the fast decompressor
+      // LZ4Factory factory = LZ4Factory.fastestInstance();
+      // LZ4FastDecompressor decompressor = factory.fastDecompressor();
+      // final int decompressedLength = sawMetadata.getColumnMetadataList()..length;
+      // LZ4BlockInputStream lis = new LZ4BlockInputStream(fis, decompressor);
       LZ4BlockInputStream lis = new LZ4BlockInputStream(fis);
       return new DataInputStream(lis);
     } else {
@@ -492,10 +498,31 @@ public class SawReader {
       throws IOException {
 
     BooleanColumn column = BooleanColumn.create(metadata.getName());
+    int trueBytesLength = metadata.getTrueBytesLength();
+    int falseBytesLength = metadata.getFalseBytesLength();
+    int missingBytesLength = metadata.getMissingBytesLength();
+    int trueAndFalseLength = trueBytesLength + falseBytesLength;
+    int allBytesLength = trueAndFalseLength + missingBytesLength;
+    byte[] trueBytes = new byte[trueBytesLength];
+    byte[] falseBytes = new byte[falseBytesLength];
+    byte[] missingBytes = new byte[missingBytesLength];
     try (DataInputStream dis = inputStream(fileName)) {
-      for (int i = 0; i < rowcount; i++) {
-        column.append(dis.readByte());
+      for (int i = 0; i < trueBytesLength; i++) {
+        trueBytes[i] = dis.readByte();
+      }
+      column.trueBytes(trueBytes);
+      int j = 0;
+      for (int i = trueBytesLength; i < trueAndFalseLength; i++) {
+        falseBytes[j] = dis.readByte();
+        j++;
+      }
+      column.falseBytes(falseBytes);
+      int k = 0;
+      for (int i = trueAndFalseLength; i < allBytesLength; i++) {
+        missingBytes[k] = dis.readByte();
+        k++;
       }
+      column.missingBytes(missingBytes);
     }
     return column;
   }
diff --git a/saw/src/main/java/tech/tablesaw/io/saw/WriteOptions.java b/saw/src/main/java/tech/tablesaw/io/saw/SawWriteOptions.java
similarity index 75%
rename from saw/src/main/java/tech/tablesaw/io/saw/WriteOptions.java
rename to saw/src/main/java/tech/tablesaw/io/saw/SawWriteOptions.java
index a453c584..798c1a67 100644
--- a/saw/src/main/java/tech/tablesaw/io/saw/WriteOptions.java
+++ b/saw/src/main/java/tech/tablesaw/io/saw/SawWriteOptions.java
@@ -2,7 +2,7 @@ package tech.tablesaw.io.saw;
 
 import com.google.common.base.Preconditions;
 
-public class WriteOptions {
+public class SawWriteOptions {
 
   private static final int DEFAULT_POOL_SIZE = 10;
 
@@ -10,17 +10,17 @@ public class WriteOptions {
   private CompressionType compressionType = CompressionType.SNAPPY;
   private EncryptionType encryptionType = EncryptionType.NONE;
 
-  public static WriteOptions defaultOptions() {
-    return new WriteOptions();
+  public static SawWriteOptions defaultOptions() {
+    return new SawWriteOptions();
   }
 
-  public WriteOptions threadPoolSize(int size) {
+  public SawWriteOptions threadPoolSize(int size) {
     Preconditions.checkArgument(size > 0);
     this.threadPoolSize = size;
     return this;
   }
 
-  public WriteOptions compressionType(CompressionType compressionType) {
+  public SawWriteOptions compressionType(CompressionType compressionType) {
     this.compressionType = compressionType;
     return this;
   }
@@ -29,7 +29,7 @@ public class WriteOptions {
    * Sets the encryption type for the storage NOTE: This is a placeholder-only, to allow for adding
    * encryption support later without changing the format of the metadata file
    */
-  public WriteOptions encryptionType(EncryptionType type) {
+  public SawWriteOptions encryptionType(EncryptionType type) {
     this.encryptionType = type;
     return this;
   }
diff --git a/saw/src/main/java/tech/tablesaw/io/saw/SawWriter.java b/saw/src/main/java/tech/tablesaw/io/saw/SawWriter.java
index a3cd847b..78089d6c 100644
--- a/saw/src/main/java/tech/tablesaw/io/saw/SawWriter.java
+++ b/saw/src/main/java/tech/tablesaw/io/saw/SawWriter.java
@@ -18,7 +18,6 @@ import com.google.common.annotations.Beta;
 import com.google.common.base.Preconditions;
 import it.unimi.dsi.fastutil.bytes.Byte2IntMap;
 import it.unimi.dsi.fastutil.bytes.Byte2ObjectMap;
-import it.unimi.dsi.fastutil.bytes.ByteIterator;
 import it.unimi.dsi.fastutil.floats.FloatIterator;
 import it.unimi.dsi.fastutil.ints.Int2IntMap;
 import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
@@ -76,24 +75,24 @@ public class SawWriter {
 
   private final SawMetadata sawMetadata;
   private final Table table;
-  private final WriteOptions writeOptions;
+  private final SawWriteOptions writeOptions;
   private final Path path;
 
-  public SawWriter(Path path, Table table, WriteOptions options) {
+  public SawWriter(Path path, Table table, SawWriteOptions options) {
     this.path = path;
     this.sawMetadata = new SawMetadata(table, options);
     this.table = table;
     this.writeOptions = options;
   }
 
-  public SawWriter(String path, Table table, WriteOptions options) {
+  public SawWriter(String path, Table table, SawWriteOptions options) {
     this.path = setPath(path);
     this.sawMetadata = new SawMetadata(table, options);
     this.table = table;
     this.writeOptions = options;
   }
 
-  public SawWriter(File file, Table table, WriteOptions options) {
+  public SawWriter(File file, Table table, SawWriteOptions options) {
     this.path = file.toPath();
     this.sawMetadata = new SawMetadata(table, options);
     this.table = table;
@@ -103,21 +102,21 @@ public class SawWriter {
   public SawWriter(Path path, Table table) {
     this.path = path;
     this.table = table;
-    this.writeOptions = WriteOptions.defaultOptions();
+    this.writeOptions = SawWriteOptions.defaultOptions();
     this.sawMetadata = new SawMetadata(table, writeOptions);
   }
 
   public SawWriter(File file, Table table) {
     this.path = file.toPath();
     this.table = table;
-    this.writeOptions = WriteOptions.defaultOptions();
+    this.writeOptions = SawWriteOptions.defaultOptions();
     this.sawMetadata = new SawMetadata(table, writeOptions);
   }
 
   public SawWriter(String path, Table table) {
     this.path = setPath(path);
     this.table = table;
-    this.writeOptions = WriteOptions.defaultOptions();
+    this.writeOptions = SawWriteOptions.defaultOptions();
     this.sawMetadata = new SawMetadata(table, writeOptions);
   }
 
@@ -548,18 +547,23 @@ public class SawWriter {
     }
   }
 
-  // TODO(lwhite): save the column using compressed bitmap?
   private void writeColumn(String fileName, BooleanColumn column) throws IOException {
+
+    byte[] trueBytes = column.trueBytes();
+    byte[] falseBytes = column.falseBytes();
+    byte[] missingBytes = column.missingBytes();
+    // write the data out
     try (DataOutputStream dos = columnOutputStream(fileName)) {
-      int i = 0;
-      ByteIterator iterator = column.byteIterator();
-      while (iterator.hasNext()) {
-        dos.writeByte(iterator.nextByte());
-        i++;
-        if (i == FLUSH_AFTER_ITERATIONS) {
-          dos.flush();
-          i = 0;
-        }
+      for (byte trueByte : trueBytes) {
+        dos.writeByte(trueByte);
+      }
+      dos.flush();
+      for (byte falseByte : falseBytes) {
+        dos.writeByte(falseByte);
+      }
+      dos.flush();
+      for (byte missingByte : missingBytes) {
+        dos.writeByte(missingByte);
       }
       dos.flush();
     }


Test patch:
diff --git a/core/src/test/java/tech/tablesaw/api/BooleanColumnTest.java b/core/src/test/java/tech/tablesaw/api/BooleanColumnTest.java
index 2a7669b7..aee79230 100644
--- a/core/src/test/java/tech/tablesaw/api/BooleanColumnTest.java
+++ b/core/src/test/java/tech/tablesaw/api/BooleanColumnTest.java
@@ -14,14 +14,13 @@
 
 package tech.tablesaw.api;
 
-import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.assertFalse;
-import static org.junit.jupiter.api.Assertions.assertNull;
-import static org.junit.jupiter.api.Assertions.assertTrue;
+import static org.junit.jupiter.api.Assertions.*;
 
 import java.util.Collections;
+import java.util.Comparator;
 import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.Test;
+import tech.tablesaw.columns.booleans.BooleanColumnType;
 import tech.tablesaw.columns.booleans.BooleanFormatter;
 import tech.tablesaw.columns.booleans.BooleanParser;
 
@@ -109,6 +108,71 @@ public class BooleanColumnTest {
     assertEquals(2 * column.size(), column1.size());
   }
 
+  @Test
+  void testSortAscending() {
+    BooleanColumn column1 = BooleanColumn.create("t");
+    column1.append(false);
+    column1.append((byte) -128);
+    column1.append(false);
+    column1.append(false);
+    column1.append(true);
+    column1.append(true);
+    column1.append(false);
+
+    column1.sortAscending();
+    assertEquals(BooleanColumnType.MISSING_VALUE, column1.getByte(0));
+    assertEquals(false, column1.get(1));
+    assertEquals(false, column1.get(2));
+    assertEquals(false, column1.get(3));
+    assertEquals(false, column1.get(4));
+    assertEquals(true, column1.get(5));
+    assertEquals(true, column1.get(6));
+  }
+
+  @Test
+  void testSort() {
+    BooleanColumn column1 = BooleanColumn.create("t");
+    column1.append(false);
+    column1.append((byte) -128);
+    column1.append(false);
+    column1.append(false);
+    column1.append(true);
+    column1.append(true);
+    column1.append(false);
+
+    Comparator<Boolean> comparator = Boolean::compare;
+    Comparator<Boolean> c2 = Comparator.nullsFirst(comparator);
+    column1 = column1.sorted(c2);
+    assertEquals(BooleanColumnType.MISSING_VALUE, column1.getByte(0));
+    assertEquals(false, column1.get(1));
+    assertEquals(false, column1.get(2));
+    assertEquals(false, column1.get(3));
+    assertEquals(false, column1.get(4));
+    assertEquals(true, column1.get(5));
+    assertEquals(true, column1.get(6));
+  }
+
+  @Test
+  void testSortDescending() {
+    BooleanColumn column1 = BooleanColumn.create("t");
+    column1.append(false);
+    column1.append((byte) -128);
+    column1.append(false);
+    column1.append(false);
+    column1.append(true);
+    column1.append(true);
+    column1.append(false);
+
+    column1.sortDescending();
+    assertEquals(true, column1.get(0));
+    assertEquals(true, column1.get(1));
+    assertEquals(false, column1.get(2));
+    assertEquals(false, column1.get(3));
+    assertEquals(false, column1.get(4));
+    assertEquals(false, column1.get(5));
+    assertEquals(BooleanColumnType.MISSING_VALUE, column1.getByte(6));
+  }
+
   @Test
   public void testPrinting() {
     column.appendCell("");
@@ -214,11 +278,49 @@ public class BooleanColumnTest {
 
   @Test
   public void testCountUnique() {
-    column.appendMissing();
     int result = column.countUnique();
+    assertEquals(2, result);
+    column.appendMissing();
+    result = column.countUnique();
     assertEquals(3, result);
   }
 
+  @Test
+  public void testCountMissing() {
+    int result = column.countMissing();
+    assertEquals(0, result);
+    column.appendMissing();
+    result = column.countMissing();
+    assertEquals(1, result);
+  }
+
+  @Test
+  public void countTrue() {
+    int result = column.countTrue();
+    assertEquals(2, result);
+  }
+
+  @Test
+  public void toByteArray() {
+    column.appendMissing();
+    byte[] expected = new byte[8];
+    expected[0] = 0;
+    expected[1] = 0;
+    expected[2] = 0;
+    expected[3] = 0;
+    expected[4] = 1;
+    expected[5] = 1;
+    expected[6] = 0;
+    expected[7] = -128;
+    assertArrayEquals(expected, column.toByteArrayList().toByteArray());
+  }
+
+  @Test
+  public void countFalse() {
+    int result = column.countFalse();
+    assertEquals(5, result);
+  }
+
   @Test
   public void testToDoubleArray() {
     double[] result = column.asDoubleArray();
diff --git a/core/src/test/java/tech/tablesaw/perf/BooleanColumnPerf.java b/core/src/test/java/tech/tablesaw/perf/BooleanColumnPerf.java
new file mode 100644
index 00000000..9fc670f2
--- /dev/null
+++ b/core/src/test/java/tech/tablesaw/perf/BooleanColumnPerf.java
@@ -0,0 +1,41 @@
+package tech.tablesaw.perf;
+
+import tech.tablesaw.api.BooleanColumn;
+import tech.tablesaw.testutil.NanoBench;
+
+public class BooleanColumnPerf {
+
+  public static void main(String[] args) {
+
+    NanoBench bench = NanoBench.create();
+    bench.warmUps(50);
+    Runnable r = new BooleanColumnPerf.Runner();
+    bench.measure("test", r);
+  }
+
+  static class Runner extends Thread {
+
+    public void run() {
+      BooleanColumn booleanColumn = BooleanColumn.create("t");
+      for (int i = 0; i < 10_000_000; i++) {
+        booleanColumn.append(i % 2 == 0 ? Boolean.TRUE : Boolean.FALSE);
+      }
+      for (int i = 0; i < 1_000_000; i++) {
+        if (i % 4 == 0) {
+          booleanColumn.setMissing(i);
+        }
+        if (i % 5 == 0) {
+          booleanColumn.set(i, Boolean.FALSE);
+        }
+      }
+      booleanColumn.size();
+      booleanColumn.countMissing();
+      booleanColumn.countTrue();
+      booleanColumn.countFalse();
+      booleanColumn.sortAscending();
+      booleanColumn.sortDescending();
+      booleanColumn.asSelection();
+      booleanColumn.isFalse();
+    }
+  }
+}
diff --git a/saw/src/test/java/tech/tablesaw/io/saw/SawMetadataTest.java b/saw/src/test/java/tech/tablesaw/io/saw/SawMetadataTest.java
index bbaef5d3..0c4c359c 100644
--- a/saw/src/test/java/tech/tablesaw/io/saw/SawMetadataTest.java
+++ b/saw/src/test/java/tech/tablesaw/io/saw/SawMetadataTest.java
@@ -17,7 +17,7 @@ class SawMetadataTest {
   @BeforeEach
   void setUp() throws Exception {
     table1 = Table.read().csv("../data/bush.csv");
-    metadata1 = new SawMetadata(table1, new WriteOptions());
+    metadata1 = new SawMetadata(table1, new SawWriteOptions());
   }
 
   @Test
diff --git a/saw/src/test/java/tech/tablesaw/io/saw/SawStorageTest.java b/saw/src/test/java/tech/tablesaw/io/saw/SawStorageTest.java
index e1e1f088..a0d8f142 100644
--- a/saw/src/test/java/tech/tablesaw/io/saw/SawStorageTest.java
+++ b/saw/src/test/java/tech/tablesaw/io/saw/SawStorageTest.java
@@ -178,7 +178,6 @@ class SawStorageTest {
 
   @Test
   void saveBooleansOnly() {
-    System.out.println(boolsOnly);
     String path = new SawWriter(tempDir, boolsOnly).write();
     Table table = new SawReader(path).read();
     assertNotNull(table);
@@ -266,7 +265,7 @@ class SawStorageTest {
         new SawWriter(
                 "../testoutput/baseball",
                 baseball,
-                new WriteOptions().compressionType(CompressionType.NONE))
+                new SawWriteOptions().compressionType(CompressionType.NONE))
             .write();
     Table bb2 = new SawReader(path, new ReadOptions().selectedColumns("OBP", "SLG", "BA")).read();
     assertEquals(3, bb2.columnCount());
@@ -282,7 +281,7 @@ class SawStorageTest {
         new SawWriter(
                 "../testoutput/baseball",
                 baseball,
-                new WriteOptions().compressionType(CompressionType.LZ4))
+                new SawWriteOptions().compressionType(CompressionType.LZ4))
             .write();
     Table bb2 = new SawReader(path, new ReadOptions().selectedColumns("OBP", "SLG", "BA")).read();
     assertEquals(3, bb2.columnCount());