You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iceberg.apache.org by ao...@apache.org on 2020/09/04 05:48:10 UTC

[iceberg] branch master updated: API: Implement SortOrder (#1373)

This is an automated email from the ASF dual-hosted git repository.

aokolnychyi pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/iceberg.git


The following commit(s) were added to refs/heads/master by this push:
     new 454101c  API: Implement SortOrder (#1373)
454101c is described below

commit 454101c3573acb9cd94d6d9a306ed99a5a324ed9
Author: Anton Okolnychyi <ao...@apple.com>
AuthorDate: Thu Sep 3 22:48:01 2020 -0700

    API: Implement SortOrder (#1373)
    
    This commit extends Iceberg metadata with a sort order that defines how data and delete files should be ordered.
---
 .baseline/checkstyle/checkstyle.xml                |   2 +
 .../apache/iceberg/{Tables.java => NullOrder.java} |  34 +--
 .../iceberg/{Tables.java => SortDirection.java}    |  26 +-
 .../main/java/org/apache/iceberg/SortField.java    | 100 +++++++
 .../main/java/org/apache/iceberg/SortOrder.java    | 298 +++++++++++++++++++++
 api/src/main/java/org/apache/iceberg/Table.java    |  14 +
 api/src/main/java/org/apache/iceberg/Tables.java   |  15 +-
 .../java/org/apache/iceberg/catalog/Catalog.java   |   9 +
 .../apache/iceberg/expressions/Expressions.java    |  11 +-
 .../java/org/apache/iceberg/BaseMetadataTable.java |  13 +-
 .../org/apache/iceberg/BaseMetastoreCatalog.java   |  15 +-
 .../main/java/org/apache/iceberg/BaseTable.java    |  10 +
 .../java/org/apache/iceberg/BaseTransaction.java   |  10 +
 .../java/org/apache/iceberg/SortOrderParser.java   | 126 +++++++++
 .../java/org/apache/iceberg/TableMetadata.java     | 166 ++++++++++--
 .../org/apache/iceberg/TableMetadataParser.java    |  30 ++-
 .../org/apache/iceberg/hadoop/HadoopTables.java    |   8 +-
 .../org/apache/iceberg/TestReplaceTransaction.java |  48 ++++
 .../java/org/apache/iceberg/TestSortOrder.java     | 247 +++++++++++++++++
 .../org/apache/iceberg/TestSortOrderParser.java    |  56 ++++
 .../java/org/apache/iceberg/TestTableMetadata.java |  29 +-
 .../test/java/org/apache/iceberg/TestTables.java   |  25 +-
 .../apache/iceberg/hadoop/TestHadoopCatalog.java   |  43 +++
 .../iceberg/hadoop/TestHadoopTablesSortOrder.java  |  89 ++++++
 .../org/apache/iceberg/hive/TestHiveCatalog.java   |  56 ++++
 .../org/apache/iceberg/mr/hive/TestTables.java     |  11 +-
 26 files changed, 1384 insertions(+), 107 deletions(-)

diff --git a/.baseline/checkstyle/checkstyle.xml b/.baseline/checkstyle/checkstyle.xml
index 7b35311..f6ce651 100644
--- a/.baseline/checkstyle/checkstyle.xml
+++ b/.baseline/checkstyle/checkstyle.xml
@@ -93,6 +93,8 @@
                 org.apache.parquet.schema.PrimitiveType.PrimitiveTypeName.*,
                 org.apache.iceberg.types.Types.NestedField.*,
                 org.apache.iceberg.TableProperties.*,
+                org.apache.iceberg.NullOrder.*,
+                org.apache.iceberg.SortDirection.*,
                 org.apache.iceberg.types.Type.*,
                 org.junit.Assert.*,
                 org.apache.spark.sql.functions.*"/>
diff --git a/api/src/main/java/org/apache/iceberg/Tables.java b/api/src/main/java/org/apache/iceberg/NullOrder.java
similarity index 50%
copy from api/src/main/java/org/apache/iceberg/Tables.java
copy to api/src/main/java/org/apache/iceberg/NullOrder.java
index 3681ea6..195d4e9 100644
--- a/api/src/main/java/org/apache/iceberg/Tables.java
+++ b/api/src/main/java/org/apache/iceberg/NullOrder.java
@@ -19,28 +19,18 @@
 
 package org.apache.iceberg;
 
-import java.util.Map;
-import org.apache.iceberg.relocated.com.google.common.collect.ImmutableMap;
+public enum NullOrder {
+  NULLS_FIRST, NULLS_LAST;
 
-/**
- * Generic interface for creating and loading a table implementation.
- *
- * The 'tableIdentifier' field should be interpreted by the underlying
- * implementation (e.g. database.table_name)
- */
-public interface Tables {
-  default Table create(Schema schema, String tableIdentifier) {
-    return create(schema, PartitionSpec.unpartitioned(), ImmutableMap.of(), tableIdentifier);
-  }
-
-  default Table create(Schema schema, PartitionSpec spec, String tableIdentifier) {
-    return create(schema, spec, ImmutableMap.of(), tableIdentifier);
+  @Override
+  public String toString() {
+    switch (this) {
+      case NULLS_FIRST:
+        return "NULLS FIRST";
+      case NULLS_LAST:
+        return "NULLS LAST";
+      default:
+        throw new IllegalArgumentException("Unexpected null order: " + this);
+    }
   }
-
-  Table create(Schema schema,
-               PartitionSpec spec,
-               Map<String, String> properties,
-               String tableIdentifier);
-
-  Table load(String tableIdentifier);
 }
diff --git a/api/src/main/java/org/apache/iceberg/Tables.java b/api/src/main/java/org/apache/iceberg/SortDirection.java
similarity index 50%
copy from api/src/main/java/org/apache/iceberg/Tables.java
copy to api/src/main/java/org/apache/iceberg/SortDirection.java
index 3681ea6..3be60b6 100644
--- a/api/src/main/java/org/apache/iceberg/Tables.java
+++ b/api/src/main/java/org/apache/iceberg/SortDirection.java
@@ -19,28 +19,6 @@
 
 package org.apache.iceberg;
 
-import java.util.Map;
-import org.apache.iceberg.relocated.com.google.common.collect.ImmutableMap;
-
-/**
- * Generic interface for creating and loading a table implementation.
- *
- * The 'tableIdentifier' field should be interpreted by the underlying
- * implementation (e.g. database.table_name)
- */
-public interface Tables {
-  default Table create(Schema schema, String tableIdentifier) {
-    return create(schema, PartitionSpec.unpartitioned(), ImmutableMap.of(), tableIdentifier);
-  }
-
-  default Table create(Schema schema, PartitionSpec spec, String tableIdentifier) {
-    return create(schema, spec, ImmutableMap.of(), tableIdentifier);
-  }
-
-  Table create(Schema schema,
-               PartitionSpec spec,
-               Map<String, String> properties,
-               String tableIdentifier);
-
-  Table load(String tableIdentifier);
+public enum SortDirection {
+  ASC, DESC
 }
diff --git a/api/src/main/java/org/apache/iceberg/SortField.java b/api/src/main/java/org/apache/iceberg/SortField.java
new file mode 100644
index 0000000..d045a62
--- /dev/null
+++ b/api/src/main/java/org/apache/iceberg/SortField.java
@@ -0,0 +1,100 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iceberg;
+
+import java.io.Serializable;
+import java.util.Objects;
+import org.apache.iceberg.transforms.Transform;
+
+/**
+ * A field in a {@link SortOrder}.
+ */
+public class SortField implements Serializable {
+
+  private final Transform<?, ?> transform;
+  private final int sourceId;
+  private final SortDirection direction;
+  private final NullOrder nullOrder;
+
+  SortField(Transform<?, ?> transform, int sourceId, SortDirection direction, NullOrder nullOrder) {
+    this.transform = transform;
+    this.sourceId = sourceId;
+    this.direction = direction;
+    this.nullOrder = nullOrder;
+  }
+
+  /**
+   * Returns the transform used to produce sort values from source values.
+   *
+   * @param <S> the Java type of values transformed by the transform function
+   * @param <T> the Java type of values returned by the transform function
+   * @return the transform
+   */
+  @SuppressWarnings("unchecked")
+  public <S, T> Transform<S, T> transform() {
+    return (Transform<S, T>) transform;
+  }
+
+  /**
+   * @return the field id of the source field in the {@link SortOrder sort order's} table schema
+   */
+  public int sourceId() {
+    return sourceId;
+  }
+
+  /**
+   * @return the sort direction
+   */
+  public SortDirection direction() {
+    return direction;
+  }
+
+  /**
+   * @return the null order
+   */
+  public NullOrder nullOrder() {
+    return nullOrder;
+  }
+
+  @Override
+  public String toString() {
+    return transform + "(" + sourceId + ") " + direction + " " + nullOrder;
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    } else if (other == null || getClass() != other.getClass()) {
+      return false;
+    }
+
+    SortField that = (SortField) other;
+    return transform.equals(that.transform) &&
+        sourceId == that.sourceId &&
+        direction == that.direction &&
+        nullOrder == that.nullOrder;
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(transform, sourceId, direction, nullOrder);
+  }
+}
diff --git a/api/src/main/java/org/apache/iceberg/SortOrder.java b/api/src/main/java/org/apache/iceberg/SortOrder.java
new file mode 100644
index 0000000..be7553e
--- /dev/null
+++ b/api/src/main/java/org/apache/iceberg/SortOrder.java
@@ -0,0 +1,298 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iceberg;
+
+import java.io.Serializable;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.stream.IntStream;
+import org.apache.iceberg.exceptions.ValidationException;
+import org.apache.iceberg.expressions.BoundReference;
+import org.apache.iceberg.expressions.BoundTerm;
+import org.apache.iceberg.expressions.BoundTransform;
+import org.apache.iceberg.expressions.Expressions;
+import org.apache.iceberg.expressions.Term;
+import org.apache.iceberg.expressions.UnboundTerm;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.transforms.Transform;
+import org.apache.iceberg.transforms.Transforms;
+import org.apache.iceberg.types.Type;
+import org.apache.iceberg.types.Types;
+
+/**
+ * A sort order that defines how data and delete files should be ordered in a table.
+ */
+public class SortOrder implements Serializable {
+  private static final SortOrder UNSORTED_ORDER = new SortOrder(new Schema(), 0, Collections.emptyList());
+
+  private final Schema schema;
+  private final int orderId;
+  private final SortField[] fields;
+
+  private transient volatile List<SortField> fieldList;
+
+  private SortOrder(Schema schema, int orderId, List<SortField> fields) {
+    this.schema = schema;
+    this.orderId = orderId;
+    this.fields = fields.toArray(new SortField[0]);
+  }
+
+  /**
+   * @return the {@link Schema} for this sort order
+   */
+  public Schema schema() {
+    return schema;
+  }
+
+  /**
+   * @return the ID of this sort order
+   */
+  public int orderId() {
+    return orderId;
+  }
+
+  /**
+   * @return the list of {@link SortField sort fields} for this sort order
+   */
+  public List<SortField> fields() {
+    return lazyFieldList();
+  }
+
+  /**
+   * @return true if the sort order is unsorted
+   */
+  public boolean isUnsorted() {
+    return fields.length < 1;
+  }
+
+  /**
+   * Checks whether this order satisfies another order.
+   *
+   * @param anotherSortOrder a different sort order
+   * @return true if this order satisfies the given order
+   */
+  public boolean satisfies(SortOrder anotherSortOrder) {
+    // any ordering satisfies an unsorted ordering
+    if (anotherSortOrder.isUnsorted()) {
+      return true;
+    }
+
+    // this ordering cannot satisfy an ordering with more sort fields
+    if (anotherSortOrder.fields.length > fields.length) {
+      return false;
+    }
+
+    // this ordering has either more or the same number of sort fields
+    return IntStream.range(0, anotherSortOrder.fields.length)
+        .allMatch(index -> fields[index].equals(anotherSortOrder.fields[index]));
+  }
+
+  /**
+   * Checks whether this order is equivalent to another order while ignoring the order id.
+   *
+   * @param anotherSortOrder a different sort order
+   * @return true if this order is equivalent to the given order
+   */
+  public boolean sameOrder(SortOrder anotherSortOrder) {
+    return Arrays.equals(fields, anotherSortOrder.fields);
+  }
+
+  private List<SortField> lazyFieldList() {
+    if (fieldList == null) {
+      synchronized (this) {
+        if (fieldList == null) {
+          this.fieldList = ImmutableList.copyOf(fields);
+        }
+      }
+    }
+    return fieldList;
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder sb = new StringBuilder();
+    sb.append("[");
+    for (SortField field : fields) {
+      sb.append("\n");
+      sb.append("  ").append(field);
+    }
+    if (fields.length > 0) {
+      sb.append("\n");
+    }
+    sb.append("]");
+    return sb.toString();
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    } else if (other == null || getClass() != other.getClass()) {
+      return false;
+    }
+
+    SortOrder that = (SortOrder) other;
+    return orderId == that.orderId && sameOrder(that);
+  }
+
+  @Override
+  public int hashCode() {
+    return 31 * Integer.hashCode(orderId) + Arrays.hashCode(fields);
+  }
+
+  /**
+   * Returns a sort order for unsorted tables.
+   *
+   * @return an unsorted order
+   */
+  public static SortOrder unsorted() {
+    return UNSORTED_ORDER;
+  }
+
+  /**
+   * Creates a new {@link Builder sort order builder} for the given {@link Schema}.
+   *
+   * @param schema a schema
+   * @return a sort order builder for the given schema
+   */
+  public static Builder builderFor(Schema schema) {
+    return new Builder(schema);
+  }
+
+  /**
+   * A builder used to create valid {@link SortOrder sort orders}.
+   * <p>
+   * Call {@link #builderFor(Schema)} to create a new builder.
+   */
+  public static class Builder {
+    private final Schema schema;
+    private final List<SortField> fields = Lists.newArrayList();
+    // default ID to 1 as 0 is reserved for unsorted order
+    private int orderId = 1;
+    private boolean caseSensitive = true;
+
+    private Builder(Schema schema) {
+      this.schema = schema;
+    }
+
+    public Builder asc(String name) {
+      return asc(name, NullOrder.NULLS_FIRST);
+    }
+
+    public Builder asc(String name, NullOrder nullOrder) {
+      return addSortField(Expressions.ref(name), SortDirection.ASC, nullOrder);
+    }
+
+    public Builder asc(Term term) {
+      return asc(term, NullOrder.NULLS_FIRST);
+    }
+
+    public Builder asc(Term term, NullOrder nullOrder) {
+      return addSortField(term, SortDirection.ASC, nullOrder);
+    }
+
+    public Builder desc(String name) {
+      return desc(name, NullOrder.NULLS_LAST);
+    }
+
+    public Builder desc(String name, NullOrder nullOrder) {
+      return addSortField(Expressions.ref(name), SortDirection.DESC, nullOrder);
+    }
+
+    public Builder desc(Term term) {
+      return desc(term, NullOrder.NULLS_LAST);
+    }
+
+    public Builder desc(Term term, NullOrder nullOrder) {
+      return addSortField(term, SortDirection.DESC, nullOrder);
+    }
+
+    public Builder withOrderId(int newOrderId) {
+      this.orderId = newOrderId;
+      return this;
+    }
+
+    public Builder caseSensitive(boolean sortCaseSensitive) {
+      this.caseSensitive = sortCaseSensitive;
+      return this;
+    }
+
+    Builder addSortField(Term term, SortDirection direction, NullOrder nullOrder) {
+      Preconditions.checkArgument(term instanceof UnboundTerm, "Term must be unbound");
+      // ValidationException is thrown by bind if binding fails so we assume that boundTerm is correct
+      BoundTerm<?> boundTerm = ((UnboundTerm<?>) term).bind(schema.asStruct(), caseSensitive);
+      int sourceId = boundTerm.ref().fieldId();
+      SortField sortField = new SortField(toTransform(boundTerm), sourceId, direction, nullOrder);
+      fields.add(sortField);
+      return this;
+    }
+
+    Builder addSortField(String transformAsString, int sourceId, SortDirection direction, NullOrder nullOrder) {
+      Types.NestedField column = schema.findField(sourceId);
+      Preconditions.checkNotNull(column, "Cannot find source column: %s", sourceId);
+      Transform<?, ?> transform = Transforms.fromString(column.type(), transformAsString);
+      SortField sortField = new SortField(transform, sourceId, direction, nullOrder);
+      fields.add(sortField);
+      return this;
+    }
+
+    public SortOrder build() {
+      if (orderId == 0 && fields.size() != 0) {
+        throw new IllegalArgumentException("Sort order ID 0 is reserved for unsorted order");
+      }
+      if (fields.size() == 0 && orderId != 0) {
+        throw new IllegalArgumentException("Unsorted order ID must be 0");
+      }
+
+      SortOrder sortOrder = new SortOrder(schema, orderId, fields);
+      checkCompatibility(sortOrder, schema);
+      return sortOrder;
+    }
+
+    private Transform<?, ?> toTransform(BoundTerm<?> term) {
+      if (term instanceof BoundReference) {
+        return Transforms.identity(term.type());
+      } else if (term instanceof BoundTransform) {
+        return ((BoundTransform<?, ?>) term).transform();
+      } else {
+        throw new ValidationException("Invalid term: %s, expected either a bound reference or transform", term);
+      }
+    }
+  }
+
+  static void checkCompatibility(SortOrder sortOrder, Schema schema) {
+    for (SortField field : sortOrder.fields) {
+      Type sourceType = schema.findType(field.sourceId());
+      ValidationException.check(
+          sourceType != null,
+          "Cannot find source column for sort field: %s", field);
+      ValidationException.check(
+          sourceType.isPrimitiveType(),
+          "Cannot sort by non-primitive source field: %s", sourceType);
+      ValidationException.check(
+          field.transform().canTransform(sourceType),
+          "Invalid source type %s for transform: %s",
+          sourceType, field.transform());
+    }
+  }
+}
diff --git a/api/src/main/java/org/apache/iceberg/Table.java b/api/src/main/java/org/apache/iceberg/Table.java
index 4536bb2..e881e21 100644
--- a/api/src/main/java/org/apache/iceberg/Table.java
+++ b/api/src/main/java/org/apache/iceberg/Table.java
@@ -66,6 +66,20 @@ public interface Table {
   Map<Integer, PartitionSpec> specs();
 
   /**
+   * Return the {@link SortOrder sort order} for this table.
+   *
+   * @return this table's sort order
+   */
+  SortOrder sortOrder();
+
+  /**
+   * Return a map of sort order IDs to {@link SortOrder sort orders} for this table.
+   *
+   * @return this table's sort orders map
+   */
+  Map<Integer, SortOrder> sortOrders();
+
+  /**
    * Return a map of string properties for this table.
    *
    * @return this table's properties map
diff --git a/api/src/main/java/org/apache/iceberg/Tables.java b/api/src/main/java/org/apache/iceberg/Tables.java
index 3681ea6..e88ece0 100644
--- a/api/src/main/java/org/apache/iceberg/Tables.java
+++ b/api/src/main/java/org/apache/iceberg/Tables.java
@@ -37,10 +37,17 @@ public interface Tables {
     return create(schema, spec, ImmutableMap.of(), tableIdentifier);
   }
 
-  Table create(Schema schema,
-               PartitionSpec spec,
-               Map<String, String> properties,
-               String tableIdentifier);
+  default Table create(Schema schema, PartitionSpec spec, Map<String, String> properties, String tableIdentifier) {
+    return create(schema, spec, SortOrder.unsorted(), properties, tableIdentifier);
+  }
+
+  default Table create(Schema schema,
+                       PartitionSpec spec,
+                       SortOrder order,
+                       Map<String, String> properties,
+                       String tableIdentifier) {
+    throw new UnsupportedOperationException(this.getClass().getName() + " does not implement create with a sort order");
+  }
 
   Table load(String tableIdentifier);
 }
diff --git a/api/src/main/java/org/apache/iceberg/catalog/Catalog.java b/api/src/main/java/org/apache/iceberg/catalog/Catalog.java
index 709c871..a8c10da 100644
--- a/api/src/main/java/org/apache/iceberg/catalog/Catalog.java
+++ b/api/src/main/java/org/apache/iceberg/catalog/Catalog.java
@@ -23,6 +23,7 @@ import java.util.List;
 import java.util.Map;
 import org.apache.iceberg.PartitionSpec;
 import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortOrder;
 import org.apache.iceberg.Table;
 import org.apache.iceberg.Transaction;
 import org.apache.iceberg.exceptions.AlreadyExistsException;
@@ -330,6 +331,14 @@ public interface Catalog {
     TableBuilder withPartitionSpec(PartitionSpec spec);
 
     /**
+     * Sets a sort order for the table.
+     *
+     * @param sortOrder a sort order
+     * @return this for method chaining
+     */
+    TableBuilder withSortOrder(SortOrder sortOrder);
+
+    /**
      * Sets a location for the table.
      *
      * @param location a location
diff --git a/api/src/main/java/org/apache/iceberg/expressions/Expressions.java b/api/src/main/java/org/apache/iceberg/expressions/Expressions.java
index 9be2710..bd2639a 100644
--- a/api/src/main/java/org/apache/iceberg/expressions/Expressions.java
+++ b/api/src/main/java/org/apache/iceberg/expressions/Expressions.java
@@ -251,7 +251,16 @@ public class Expressions {
     return ExpressionVisitors.visit(expr, RewriteNot.get());
   }
 
-  static <T> NamedReference<T> ref(String name) {
+  /**
+   * Constructs a reference for a given column.
+   * <p>
+   * The following are equivalent: equals("a", 5) and equals(ref("a"), 5).
+   *
+   * @param name a column name
+   * @param <T> the Java type of this reference
+   * @return a named reference
+   */
+  public static <T> NamedReference<T> ref(String name) {
     return new NamedReference<>(name);
   }
 }
diff --git a/core/src/main/java/org/apache/iceberg/BaseMetadataTable.java b/core/src/main/java/org/apache/iceberg/BaseMetadataTable.java
index 009cfbd..be44c3b 100644
--- a/core/src/main/java/org/apache/iceberg/BaseMetadataTable.java
+++ b/core/src/main/java/org/apache/iceberg/BaseMetadataTable.java
@@ -27,7 +27,8 @@ import org.apache.iceberg.io.LocationProvider;
 import org.apache.iceberg.relocated.com.google.common.collect.ImmutableMap;
 
 abstract class BaseMetadataTable implements Table {
-  private PartitionSpec spec = PartitionSpec.unpartitioned();
+  private final PartitionSpec spec = PartitionSpec.unpartitioned();
+  private final SortOrder sortOrder = SortOrder.unsorted();
 
   abstract Table table();
   abstract String metadataTableName();
@@ -68,6 +69,16 @@ abstract class BaseMetadataTable implements Table {
   }
 
   @Override
+  public SortOrder sortOrder() {
+    return sortOrder;
+  }
+
+  @Override
+  public Map<Integer, SortOrder> sortOrders() {
+    return ImmutableMap.of(sortOrder.orderId(), sortOrder);
+  }
+
+  @Override
   public Map<String, String> properties() {
     return ImmutableMap.of();
   }
diff --git a/core/src/main/java/org/apache/iceberg/BaseMetastoreCatalog.java b/core/src/main/java/org/apache/iceberg/BaseMetastoreCatalog.java
index c9dd934..76b343b 100644
--- a/core/src/main/java/org/apache/iceberg/BaseMetastoreCatalog.java
+++ b/core/src/main/java/org/apache/iceberg/BaseMetastoreCatalog.java
@@ -194,6 +194,7 @@ public abstract class BaseMetastoreCatalog implements Catalog {
     private final Schema schema;
     private final ImmutableMap.Builder<String, String> propertiesBuilder = ImmutableMap.builder();
     private PartitionSpec spec = PartitionSpec.unpartitioned();
+    private SortOrder sortOrder = SortOrder.unsorted();
     private String location = null;
 
     public BaseMetastoreCatalogTableBuilder(TableIdentifier identifier, Schema schema) {
@@ -210,6 +211,12 @@ public abstract class BaseMetastoreCatalog implements Catalog {
     }
 
     @Override
+    public TableBuilder withSortOrder(SortOrder newSortOrder) {
+      this.sortOrder = newSortOrder != null ? newSortOrder : SortOrder.unsorted();
+      return this;
+    }
+
+    @Override
     public TableBuilder withLocation(String newLocation) {
       this.location = newLocation;
       return this;
@@ -238,7 +245,7 @@ public abstract class BaseMetastoreCatalog implements Catalog {
 
       String baseLocation = location != null ? location : defaultWarehouseLocation(identifier);
       Map<String, String> properties = propertiesBuilder.build();
-      TableMetadata metadata = TableMetadata.newTableMetadata(schema, spec, baseLocation, properties);
+      TableMetadata metadata = TableMetadata.newTableMetadata(schema, spec, sortOrder, baseLocation, properties);
 
       try {
         ops.commit(null, metadata);
@@ -258,7 +265,7 @@ public abstract class BaseMetastoreCatalog implements Catalog {
 
       String baseLocation = location != null ? location : defaultWarehouseLocation(identifier);
       Map<String, String> properties = propertiesBuilder.build();
-      TableMetadata metadata = TableMetadata.newTableMetadata(schema, spec, baseLocation, properties);
+      TableMetadata metadata = TableMetadata.newTableMetadata(schema, spec, sortOrder, baseLocation, properties);
       return Transactions.createTableTransaction(identifier.toString(), ops, metadata);
     }
 
@@ -281,10 +288,10 @@ public abstract class BaseMetastoreCatalog implements Catalog {
       TableMetadata metadata;
       if (ops.current() != null) {
         String baseLocation = location != null ? location : ops.current().location();
-        metadata = ops.current().buildReplacement(schema, spec, baseLocation, propertiesBuilder.build());
+        metadata = ops.current().buildReplacement(schema, spec, sortOrder, baseLocation, propertiesBuilder.build());
       } else {
         String baseLocation = location != null ? location : defaultWarehouseLocation(identifier);
-        metadata = TableMetadata.newTableMetadata(schema, spec, baseLocation, propertiesBuilder.build());
+        metadata = TableMetadata.newTableMetadata(schema, spec, sortOrder, baseLocation, propertiesBuilder.build());
       }
 
       if (orCreate) {
diff --git a/core/src/main/java/org/apache/iceberg/BaseTable.java b/core/src/main/java/org/apache/iceberg/BaseTable.java
index 15b8742..5058d51 100644
--- a/core/src/main/java/org/apache/iceberg/BaseTable.java
+++ b/core/src/main/java/org/apache/iceberg/BaseTable.java
@@ -70,6 +70,16 @@ public class BaseTable implements Table, HasTableOperations {
   }
 
   @Override
+  public SortOrder sortOrder() {
+    return ops.current().sortOrder();
+  }
+
+  @Override
+  public Map<Integer, SortOrder> sortOrders() {
+    return ops.current().sortOrdersById();
+  }
+
+  @Override
   public Map<String, String> properties() {
     return ops.current().properties();
   }
diff --git a/core/src/main/java/org/apache/iceberg/BaseTransaction.java b/core/src/main/java/org/apache/iceberg/BaseTransaction.java
index 5f19f15..744f6e3 100644
--- a/core/src/main/java/org/apache/iceberg/BaseTransaction.java
+++ b/core/src/main/java/org/apache/iceberg/BaseTransaction.java
@@ -509,6 +509,16 @@ class BaseTransaction implements Transaction {
     }
 
     @Override
+    public SortOrder sortOrder() {
+      return current.sortOrder();
+    }
+
+    @Override
+    public Map<Integer, SortOrder> sortOrders() {
+      return current.sortOrdersById();
+    }
+
+    @Override
     public Map<String, String> properties() {
       return current.properties();
     }
diff --git a/core/src/main/java/org/apache/iceberg/SortOrderParser.java b/core/src/main/java/org/apache/iceberg/SortOrderParser.java
new file mode 100644
index 0000000..418486e
--- /dev/null
+++ b/core/src/main/java/org/apache/iceberg/SortOrderParser.java
@@ -0,0 +1,126 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iceberg;
+
+import com.fasterxml.jackson.core.JsonGenerator;
+import com.fasterxml.jackson.databind.JsonNode;
+import java.io.IOException;
+import java.io.UncheckedIOException;
+import java.util.Iterator;
+import java.util.Locale;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.JsonUtil;
+
+import static org.apache.iceberg.NullOrder.NULLS_FIRST;
+import static org.apache.iceberg.NullOrder.NULLS_LAST;
+
+public class SortOrderParser {
+  private static final String ORDER_ID = "order-id";
+  private static final String FIELDS = "fields";
+  private static final String DIRECTION = "direction";
+  private static final String NULL_ORDER = "null-order";
+  private static final String TRANSFORM = "transform";
+  private static final String SOURCE_ID = "source-id";
+
+  private SortOrderParser() {
+  }
+
+  public static void toJson(SortOrder sortOrder, JsonGenerator generator) throws IOException {
+    generator.writeStartObject();
+    generator.writeNumberField(ORDER_ID, sortOrder.orderId());
+    generator.writeFieldName(FIELDS);
+    toJsonFields(sortOrder, generator);
+    generator.writeEndObject();
+  }
+
+  private static String toJson(SortDirection direction) {
+    return direction.toString().toLowerCase(Locale.ROOT);
+  }
+
+  private static String toJson(NullOrder nullOrder) {
+    return nullOrder == NULLS_FIRST ? "nulls-first" : "nulls-last";
+  }
+
+  private static void toJsonFields(SortOrder sortOrder, JsonGenerator generator) throws IOException {
+    generator.writeStartArray();
+    for (SortField field : sortOrder.fields()) {
+      generator.writeStartObject();
+      generator.writeStringField(TRANSFORM, field.transform().toString());
+      generator.writeNumberField(SOURCE_ID, field.sourceId());
+      generator.writeStringField(DIRECTION, toJson(field.direction()));
+      generator.writeStringField(NULL_ORDER, toJson(field.nullOrder()));
+      generator.writeEndObject();
+    }
+    generator.writeEndArray();
+  }
+
+  public static SortOrder fromJson(Schema schema, String json) {
+    try {
+      return fromJson(schema, JsonUtil.mapper().readValue(json, JsonNode.class));
+    } catch (IOException e) {
+      throw new UncheckedIOException(e);
+    }
+  }
+
+  public static SortOrder fromJson(Schema schema, JsonNode json) {
+    Preconditions.checkArgument(json.isObject(), "Cannot parse sort order from non-object: %s", json);
+    int orderId = JsonUtil.getInt(ORDER_ID, json);
+    SortOrder.Builder builder = SortOrder.builderFor(schema).withOrderId(orderId);
+    buildFromJsonFields(builder, json.get(FIELDS));
+    return builder.build();
+  }
+
+  private static void buildFromJsonFields(SortOrder.Builder builder, JsonNode json) {
+    Preconditions.checkArgument(json != null, "Cannot parse null sort order fields");
+    Preconditions.checkArgument(json.isArray(), "Cannot parse sort order fields, not an array: %s", json);
+
+    Iterator<JsonNode> elements = json.elements();
+    while (elements.hasNext()) {
+      JsonNode element = elements.next();
+      Preconditions.checkArgument(element.isObject(), "Cannot parse sort field, not an object: %s", element);
+
+      String transform = JsonUtil.getString(TRANSFORM, element);
+      int sourceId = JsonUtil.getInt(SOURCE_ID, element);
+
+      String directionAsString = JsonUtil.getString(DIRECTION, element);
+      SortDirection direction = toDirection(directionAsString);
+
+      String nullOrderingAsString = JsonUtil.getString(NULL_ORDER, element);
+      NullOrder nullOrder = toNullOrder(nullOrderingAsString);
+
+      builder.addSortField(transform, sourceId, direction, nullOrder);
+    }
+  }
+
+  private static SortDirection toDirection(String directionAsString) {
+    return SortDirection.valueOf(directionAsString.toUpperCase(Locale.ROOT));
+  }
+
+  private static NullOrder toNullOrder(String nullOrderingAsString) {
+    switch (nullOrderingAsString) {
+      case "nulls-first":
+        return NULLS_FIRST;
+      case "nulls-last":
+        return NULLS_LAST;
+      default:
+        throw new IllegalArgumentException("Unexpected null order: " + nullOrderingAsString);
+    }
+  }
+}
diff --git a/core/src/main/java/org/apache/iceberg/TableMetadata.java b/core/src/main/java/org/apache/iceberg/TableMetadata.java
index b7fb7cb..3115577 100644
--- a/core/src/main/java/org/apache/iceberg/TableMetadata.java
+++ b/core/src/main/java/org/apache/iceberg/TableMetadata.java
@@ -22,6 +22,8 @@ package org.apache.iceberg;
 import java.io.Serializable;
 import java.util.List;
 import java.util.Map;
+import java.util.Optional;
+import java.util.OptionalInt;
 import java.util.Set;
 import java.util.UUID;
 import java.util.concurrent.TimeUnit;
@@ -49,6 +51,7 @@ public class TableMetadata implements Serializable {
   static final int DEFAULT_TABLE_FORMAT_VERSION = 1;
   static final int SUPPORTED_TABLE_FORMAT_VERSION = 2;
   static final int INITIAL_SPEC_ID = 0;
+  static final int INITIAL_SORT_ORDER_ID = 1;
 
   private static final long ONE_MINUTE = TimeUnit.MINUTES.toMillis(1);
 
@@ -61,18 +64,27 @@ public class TableMetadata implements Serializable {
                                                PartitionSpec spec,
                                                String location,
                                                Map<String, String> properties) {
-    return newTableMetadata(schema, spec, location, properties, DEFAULT_TABLE_FORMAT_VERSION);
+    return newTableMetadata(schema, spec, SortOrder.unsorted(), location, properties, DEFAULT_TABLE_FORMAT_VERSION);
   }
 
   public static TableMetadata newTableMetadata(Schema schema,
                                                PartitionSpec spec,
+                                               SortOrder sortOrder,
                                                String location,
                                                Map<String, String> properties) {
-    return newTableMetadata(schema, spec, location, properties, DEFAULT_TABLE_FORMAT_VERSION);
+    return newTableMetadata(schema, spec, sortOrder, location, properties, DEFAULT_TABLE_FORMAT_VERSION);
+  }
+
+  public static TableMetadata newTableMetadata(Schema schema,
+                                               PartitionSpec spec,
+                                               String location,
+                                               Map<String, String> properties) {
+    return newTableMetadata(schema, spec, SortOrder.unsorted(), location, properties, DEFAULT_TABLE_FORMAT_VERSION);
   }
 
   static TableMetadata newTableMetadata(Schema schema,
                                         PartitionSpec spec,
+                                        SortOrder sortOrder,
                                         String location,
                                         Map<String, String> properties,
                                         int formatVersion) {
@@ -94,9 +106,14 @@ public class TableMetadata implements Serializable {
     }
     PartitionSpec freshSpec = specBuilder.build();
 
+    // rebuild the sort order using the new column ids
+    int freshSortOrderId = sortOrder.isUnsorted() ? sortOrder.orderId() : INITIAL_SORT_ORDER_ID;
+    SortOrder freshSortOrder = freshSortOrder(freshSortOrderId, freshSchema, sortOrder);
+
     return new TableMetadata(null, formatVersion, UUID.randomUUID().toString(), location,
         INITIAL_SEQUENCE_NUMBER, System.currentTimeMillis(),
         lastColumnId.get(), freshSchema, INITIAL_SPEC_ID, ImmutableList.of(freshSpec),
+        freshSortOrderId, ImmutableList.of(freshSortOrder),
         ImmutableMap.copyOf(properties), -1, ImmutableList.of(),
         ImmutableList.of(), ImmutableList.of());
   }
@@ -201,14 +218,18 @@ public class TableMetadata implements Serializable {
   private final Schema schema;
   private final int defaultSpecId;
   private final List<PartitionSpec> specs;
+  private final int defaultSortOrderId;
+  private final List<SortOrder> sortOrders;
   private final Map<String, String> properties;
   private final long currentSnapshotId;
   private final List<Snapshot> snapshots;
   private final Map<Long, Snapshot> snapshotsById;
   private final Map<Integer, PartitionSpec> specsById;
+  private final Map<Integer, SortOrder> sortOrdersById;
   private final List<HistoryEntry> snapshotLog;
   private final List<MetadataLogEntry> previousFiles;
 
+  @SuppressWarnings("checkstyle:CyclomaticComplexity")
   TableMetadata(InputFile file,
                 int formatVersion,
                 String uuid,
@@ -219,12 +240,15 @@ public class TableMetadata implements Serializable {
                 Schema schema,
                 int defaultSpecId,
                 List<PartitionSpec> specs,
+                int defaultSortOrderId,
+                List<SortOrder> sortOrders,
                 Map<String, String> properties,
                 long currentSnapshotId,
                 List<Snapshot> snapshots,
                 List<HistoryEntry> snapshotLog,
                 List<MetadataLogEntry> previousFiles) {
     Preconditions.checkArgument(specs != null && !specs.isEmpty(), "Partition specs cannot be null or empty");
+    Preconditions.checkArgument(sortOrders != null && !sortOrders.isEmpty(), "Sort orders cannot be null or empty");
     Preconditions.checkArgument(formatVersion <= SUPPORTED_TABLE_FORMAT_VERSION,
         "Unsupported format version: v%s", formatVersion);
     Preconditions.checkArgument(formatVersion == 1 || uuid != null,
@@ -243,6 +267,8 @@ public class TableMetadata implements Serializable {
     this.schema = schema;
     this.specs = specs;
     this.defaultSpecId = defaultSpecId;
+    this.defaultSortOrderId = defaultSortOrderId;
+    this.sortOrders = sortOrders;
     this.properties = properties;
     this.currentSnapshotId = currentSnapshotId;
     this.snapshots = snapshots;
@@ -251,6 +277,7 @@ public class TableMetadata implements Serializable {
 
     this.snapshotsById = indexAndValidateSnapshots(snapshots, lastSequenceNumber);
     this.specsById = indexSpecs(specs);
+    this.sortOrdersById = indexSortOrders(sortOrders);
 
     HistoryEntry last = null;
     for (HistoryEntry logEntry : snapshotLog) {
@@ -348,6 +375,22 @@ public class TableMetadata implements Serializable {
     return defaultSpecId;
   }
 
+  public int defaultSortOrderId() {
+    return defaultSortOrderId;
+  }
+
+  public SortOrder sortOrder() {
+    return sortOrdersById.get(defaultSortOrderId);
+  }
+
+  public List<SortOrder> sortOrders() {
+    return sortOrders;
+  }
+
+  public Map<Integer, SortOrder> sortOrdersById() {
+    return sortOrdersById;
+  }
+
   public String location() {
     return location;
   }
@@ -397,19 +440,22 @@ public class TableMetadata implements Serializable {
       return this;
     } else {
       return new TableMetadata(null, formatVersion, UUID.randomUUID().toString(), location,
-          lastSequenceNumber, lastUpdatedMillis, lastColumnId, schema, defaultSpecId, specs, properties,
-          currentSnapshotId, snapshots, snapshotLog, addPreviousFile(file, lastUpdatedMillis));
+          lastSequenceNumber, lastUpdatedMillis, lastColumnId, schema, defaultSpecId, specs,
+          defaultSortOrderId, sortOrders, properties, currentSnapshotId, snapshots, snapshotLog,
+          addPreviousFile(file, lastUpdatedMillis));
     }
   }
 
   public TableMetadata updateSchema(Schema newSchema, int newLastColumnId) {
     PartitionSpec.checkCompatibility(spec(), newSchema);
-    // rebuild all of the partition specs for the new current schema
-    List<PartitionSpec> updatedSpecs = Lists.transform(specs,
-        spec -> updateSpecSchema(newSchema, spec));
+    SortOrder.checkCompatibility(sortOrder(), newSchema);
+    // rebuild all of the partition specs and sort orders for the new current schema
+    List<PartitionSpec> updatedSpecs = Lists.transform(specs, spec -> updateSpecSchema(newSchema, spec));
+    List<SortOrder> updatedSortOrders = Lists.transform(sortOrders, order -> updateSortOrderSchema(newSchema, order));
     return new TableMetadata(null, formatVersion, uuid, location,
         lastSequenceNumber, System.currentTimeMillis(), newLastColumnId, newSchema, defaultSpecId, updatedSpecs,
-        properties, currentSnapshotId, snapshots, snapshotLog, addPreviousFile(file, lastUpdatedMillis));
+        defaultSortOrderId, updatedSortOrders, properties, currentSnapshotId, snapshots, snapshotLog,
+        addPreviousFile(file, lastUpdatedMillis));
   }
 
   // The caller is responsible to pass a newPartitionSpec with correct partition field IDs
@@ -441,7 +487,7 @@ public class TableMetadata implements Serializable {
 
     return new TableMetadata(null, formatVersion, uuid, location,
         lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, newDefaultSpecId,
-        builder.build(), properties,
+        builder.build(), defaultSortOrderId, sortOrders, properties,
         currentSnapshotId, snapshots, snapshotLog, addPreviousFile(file, lastUpdatedMillis));
   }
 
@@ -456,8 +502,9 @@ public class TableMetadata implements Serializable {
         .build();
 
     return new TableMetadata(null, formatVersion, uuid, location,
-        snapshot.sequenceNumber(), snapshot.timestampMillis(), lastColumnId, schema, defaultSpecId, specs, properties,
-        currentSnapshotId, newSnapshots, snapshotLog, addPreviousFile(file, lastUpdatedMillis));
+        snapshot.sequenceNumber(), snapshot.timestampMillis(), lastColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, properties, currentSnapshotId, newSnapshots, snapshotLog,
+        addPreviousFile(file, lastUpdatedMillis));
   }
 
   public TableMetadata replaceCurrentSnapshot(Snapshot snapshot) {
@@ -480,8 +527,9 @@ public class TableMetadata implements Serializable {
         .build();
 
     return new TableMetadata(null, formatVersion, uuid, location,
-        snapshot.sequenceNumber(), snapshot.timestampMillis(), lastColumnId, schema, defaultSpecId, specs, properties,
-        snapshot.snapshotId(), newSnapshots, newSnapshotLog, addPreviousFile(file, lastUpdatedMillis));
+        snapshot.sequenceNumber(), snapshot.timestampMillis(), lastColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, properties, snapshot.snapshotId(), newSnapshots, newSnapshotLog,
+        addPreviousFile(file, lastUpdatedMillis));
   }
 
   public TableMetadata removeSnapshotsIf(Predicate<Snapshot> removeIf) {
@@ -511,9 +559,9 @@ public class TableMetadata implements Serializable {
     }
 
     return new TableMetadata(null, formatVersion, uuid, location,
-        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs, properties,
-        currentSnapshotId, filtered, ImmutableList.copyOf(newSnapshotLog),
-        addPreviousFile(file, lastUpdatedMillis));
+        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, properties, currentSnapshotId, filtered,
+        ImmutableList.copyOf(newSnapshotLog), addPreviousFile(file, lastUpdatedMillis));
   }
 
   private TableMetadata setCurrentSnapshotTo(Snapshot snapshot) {
@@ -535,15 +583,17 @@ public class TableMetadata implements Serializable {
         .build();
 
     return new TableMetadata(null, formatVersion, uuid, location,
-        lastSequenceNumber, nowMillis, lastColumnId, schema, defaultSpecId, specs, properties,
-        snapshot.snapshotId(), snapshots, newSnapshotLog, addPreviousFile(file, lastUpdatedMillis));
+        lastSequenceNumber, nowMillis, lastColumnId, schema, defaultSpecId, specs, defaultSortOrderId,
+        sortOrders, properties, snapshot.snapshotId(), snapshots, newSnapshotLog,
+        addPreviousFile(file, lastUpdatedMillis));
   }
 
   public TableMetadata replaceProperties(Map<String, String> newProperties) {
     ValidationException.check(newProperties != null, "Cannot set properties to null");
     return new TableMetadata(null, formatVersion, uuid, location,
-        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs, newProperties,
-        currentSnapshotId, snapshots, snapshotLog, addPreviousFile(file, lastUpdatedMillis, newProperties));
+        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, newProperties, currentSnapshotId, snapshots, snapshotLog,
+        addPreviousFile(file, lastUpdatedMillis, newProperties));
   }
 
   public TableMetadata removeSnapshotLogEntries(Set<Long> snapshotIds) {
@@ -560,13 +610,15 @@ public class TableMetadata implements Serializable {
         "Cannot set invalid snapshot log: latest entry is not the current snapshot");
 
     return new TableMetadata(null, formatVersion, uuid, location,
-        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs, properties,
-        currentSnapshotId, snapshots, newSnapshotLog, addPreviousFile(file, lastUpdatedMillis));
+        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, properties, currentSnapshotId, snapshots, newSnapshotLog,
+        addPreviousFile(file, lastUpdatedMillis));
   }
 
   // The caller is responsible to pass a updatedPartitionSpec with correct partition field IDs
   public TableMetadata buildReplacement(Schema updatedSchema, PartitionSpec updatedPartitionSpec,
-                                        String newLocation, Map<String, String> updatedProperties) {
+                                        SortOrder updatedSortOrder, String newLocation,
+                                        Map<String, String> updatedProperties) {
     ValidationException.check(formatVersion > 1 || PartitionSpec.hasSequentialIds(updatedPartitionSpec),
         "Spec does not use sequential IDs that are required in v1: %s", updatedPartitionSpec);
 
@@ -598,20 +650,40 @@ public class TableMetadata implements Serializable {
       builder.add(freshSpec);
     }
 
+    // determine the next order id
+    OptionalInt maxOrderId = sortOrders.stream().mapToInt(SortOrder::orderId).max();
+    int nextOrderId = maxOrderId.isPresent() ? maxOrderId.getAsInt() + 1 : INITIAL_SORT_ORDER_ID;
+
+    // rebuild the sort order using new column ids
+    int freshSortOrderId = updatedSortOrder.isUnsorted() ? updatedSortOrder.orderId() : nextOrderId;
+    SortOrder freshSortOrder = freshSortOrder(freshSortOrderId, freshSchema, updatedSortOrder);
+
+    // if the order already exists, use the same ID. otherwise, use the fresh order ID
+    Optional<SortOrder> sameSortOrder = sortOrders.stream()
+        .filter(sortOrder -> sortOrder.sameOrder(freshSortOrder))
+        .findAny();
+    int orderId = sameSortOrder.map(SortOrder::orderId).orElse(freshSortOrderId);
+
+    ImmutableList.Builder<SortOrder> sortOrdersBuilder = ImmutableList.<SortOrder>builder().addAll(sortOrders);
+    if (!sortOrdersById.containsKey(orderId)) {
+      sortOrdersBuilder.add(freshSortOrder);
+    }
+
     Map<String, String> newProperties = Maps.newHashMap();
     newProperties.putAll(this.properties);
     newProperties.putAll(updatedProperties);
 
     return new TableMetadata(null, formatVersion, uuid, newLocation,
         lastSequenceNumber, System.currentTimeMillis(), nextLastColumnId.get(), freshSchema,
-        specId, builder.build(), ImmutableMap.copyOf(newProperties),
+        specId, builder.build(), orderId, sortOrdersBuilder.build(), ImmutableMap.copyOf(newProperties),
         -1, snapshots, ImmutableList.of(), addPreviousFile(file, lastUpdatedMillis, newProperties));
   }
 
   public TableMetadata updateLocation(String newLocation) {
     return new TableMetadata(null, formatVersion, uuid, newLocation,
-        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs, properties,
-        currentSnapshotId, snapshots, snapshotLog, addPreviousFile(file, lastUpdatedMillis));
+        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, properties, currentSnapshotId, snapshots, snapshotLog,
+        addPreviousFile(file, lastUpdatedMillis));
   }
 
   public TableMetadata upgradeToFormatVersion(int newFormatVersion) {
@@ -626,8 +698,9 @@ public class TableMetadata implements Serializable {
     }
 
     return new TableMetadata(null, newFormatVersion, uuid, location,
-        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs, properties,
-        currentSnapshotId, snapshots, snapshotLog, addPreviousFile(file, lastUpdatedMillis));
+        lastSequenceNumber, System.currentTimeMillis(), lastColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, properties, currentSnapshotId, snapshots, snapshotLog,
+        addPreviousFile(file, lastUpdatedMillis));
   }
 
   private List<MetadataLogEntry> addPreviousFile(InputFile previousFile, long timestampMillis) {
@@ -667,6 +740,17 @@ public class TableMetadata implements Serializable {
     return specBuilder.build();
   }
 
+  private static SortOrder updateSortOrderSchema(Schema schema, SortOrder sortOrder) {
+    SortOrder.Builder builder = SortOrder.builderFor(schema).withOrderId(sortOrder.orderId());
+
+    // add all of the fields to the builder. IDs should not change.
+    for (SortField field : sortOrder.fields()) {
+      builder.addSortField(field.transform().toString(), field.sourceId(), field.direction(), field.nullOrder());
+    }
+
+    return builder.build();
+  }
+
   private static PartitionSpec freshSpec(int specId, Schema schema, PartitionSpec partitionSpec) {
     PartitionSpec.Builder specBuilder = PartitionSpec.builderFor(schema)
         .withSpecId(specId);
@@ -684,6 +768,24 @@ public class TableMetadata implements Serializable {
     return specBuilder.build();
   }
 
+  private static SortOrder freshSortOrder(int orderId, Schema schema, SortOrder sortOrder) {
+    SortOrder.Builder builder = SortOrder.builderFor(schema).withOrderId(orderId);
+
+    for (SortField field : sortOrder.fields()) {
+      // look up the name of the source field in the old schema to get the new schema's id
+      String sourceName = sortOrder.schema().findColumnName(field.sourceId());
+      // reassign all sort fields with fresh sort field IDs
+      int newSourceId = schema.findField(sourceName).fieldId();
+      builder.addSortField(
+          field.transform().toString(),
+          newSourceId,
+          field.direction(),
+          field.nullOrder());
+    }
+
+    return builder.build();
+  }
+
   private static Map<Long, Snapshot> indexAndValidateSnapshots(List<Snapshot> snapshots, long lastSequenceNumber) {
     ImmutableMap.Builder<Long, Snapshot> builder = ImmutableMap.builder();
     for (Snapshot snap : snapshots) {
@@ -702,4 +804,12 @@ public class TableMetadata implements Serializable {
     }
     return builder.build();
   }
+
+  private static Map<Integer, SortOrder> indexSortOrders(List<SortOrder> sortOrders) {
+    ImmutableMap.Builder<Integer, SortOrder> builder = ImmutableMap.builder();
+    for (SortOrder sortOrder : sortOrders) {
+      builder.put(sortOrder.orderId(), sortOrder);
+    }
+    return builder.build();
+  }
 }
diff --git a/core/src/main/java/org/apache/iceberg/TableMetadataParser.java b/core/src/main/java/org/apache/iceberg/TableMetadataParser.java
index 0c9d05c..805c299 100644
--- a/core/src/main/java/org/apache/iceberg/TableMetadataParser.java
+++ b/core/src/main/java/org/apache/iceberg/TableMetadataParser.java
@@ -91,6 +91,8 @@ public class TableMetadataParser {
   static final String PARTITION_SPEC = "partition-spec";
   static final String PARTITION_SPECS = "partition-specs";
   static final String DEFAULT_SPEC_ID = "default-spec-id";
+  static final String DEFAULT_SORT_ORDER_ID = "default-sort-order-id";
+  static final String SORT_ORDERS = "sort-orders";
   static final String PROPERTIES = "properties";
   static final String CURRENT_SNAPSHOT_ID = "current-snapshot-id";
   static final String SNAPSHOTS = "snapshots";
@@ -176,6 +178,13 @@ public class TableMetadataParser {
     }
     generator.writeEndArray();
 
+    generator.writeNumberField(DEFAULT_SORT_ORDER_ID, metadata.defaultSortOrderId());
+    generator.writeArrayFieldStart(SORT_ORDERS);
+    for (SortOrder sortOrder : metadata.sortOrders()) {
+      SortOrderParser.toJson(sortOrder, generator);
+    }
+    generator.writeEndArray();
+
     generator.writeObjectFieldStart(PROPERTIES);
     for (Map.Entry<String, String> keyValue : metadata.properties().entrySet()) {
       generator.writeStringField(keyValue.getKey(), keyValue.getValue());
@@ -277,6 +286,22 @@ public class TableMetadataParser {
           schema, TableMetadata.INITIAL_SPEC_ID, node.get(PARTITION_SPEC)));
     }
 
+    JsonNode sortOrderArray = node.get(SORT_ORDERS);
+    List<SortOrder> sortOrders;
+    int defaultSortOrderId;
+    if (sortOrderArray != null) {
+      defaultSortOrderId = JsonUtil.getInt(DEFAULT_SORT_ORDER_ID, node);
+      ImmutableList.Builder<SortOrder> sortOrdersBuilder = ImmutableList.builder();
+      for (JsonNode sortOrder : sortOrderArray) {
+        sortOrdersBuilder.add(SortOrderParser.fromJson(schema, sortOrder));
+      }
+      sortOrders = sortOrdersBuilder.build();
+    } else {
+      SortOrder defaultSortOrder = SortOrder.unsorted();
+      sortOrders = ImmutableList.of(defaultSortOrder);
+      defaultSortOrderId = defaultSortOrder.orderId();
+    }
+
     Map<String, String> properties = JsonUtil.getStringMap(PROPERTIES, node);
     long currentVersionId = JsonUtil.getLong(CURRENT_SNAPSHOT_ID, node);
     long lastUpdatedMillis = JsonUtil.getLong(LAST_UPDATED_MILLIS, node);
@@ -312,7 +337,8 @@ public class TableMetadataParser {
     }
 
     return new TableMetadata(file, formatVersion, uuid, location,
-        lastSequenceNumber, lastUpdatedMillis, lastAssignedColumnId, schema, defaultSpecId, specs, properties,
-        currentVersionId, snapshots, entries.build(), metadataEntries.build());
+        lastSequenceNumber, lastUpdatedMillis, lastAssignedColumnId, schema, defaultSpecId, specs,
+        defaultSortOrderId, sortOrders, properties, currentVersionId, snapshots, entries.build(),
+        metadataEntries.build());
   }
 }
diff --git a/core/src/main/java/org/apache/iceberg/hadoop/HadoopTables.java b/core/src/main/java/org/apache/iceberg/hadoop/HadoopTables.java
index 1e5d6e4..e7a7665 100644
--- a/core/src/main/java/org/apache/iceberg/hadoop/HadoopTables.java
+++ b/core/src/main/java/org/apache/iceberg/hadoop/HadoopTables.java
@@ -36,6 +36,7 @@ import org.apache.iceberg.PartitionSpec;
 import org.apache.iceberg.PartitionsTable;
 import org.apache.iceberg.Schema;
 import org.apache.iceberg.SnapshotsTable;
+import org.apache.iceberg.SortOrder;
 import org.apache.iceberg.StaticTableOperations;
 import org.apache.iceberg.Table;
 import org.apache.iceberg.TableMetadata;
@@ -155,8 +156,8 @@ public class HadoopTables implements Tables, Configurable {
    * @return newly created table implementation
    */
   @Override
-  public Table create(Schema schema, PartitionSpec spec, Map<String, String> properties,
-                      String location) {
+  public Table create(Schema schema, PartitionSpec spec, SortOrder order,
+                      Map<String, String> properties, String location) {
     Preconditions.checkNotNull(schema, "A table schema is required");
 
     TableOperations ops = newTableOps(location);
@@ -166,7 +167,8 @@ public class HadoopTables implements Tables, Configurable {
 
     Map<String, String> tableProps = properties == null ? ImmutableMap.of() : properties;
     PartitionSpec partitionSpec = spec == null ? PartitionSpec.unpartitioned() : spec;
-    TableMetadata metadata = TableMetadata.newTableMetadata(schema, partitionSpec, location, tableProps);
+    SortOrder sortOrder = order == null ? SortOrder.unsorted() : order;
+    TableMetadata metadata = TableMetadata.newTableMetadata(schema, partitionSpec, sortOrder, location, tableProps);
     ops.commit(null, metadata);
 
     return new BaseTable(ops, location);
diff --git a/core/src/test/java/org/apache/iceberg/TestReplaceTransaction.java b/core/src/test/java/org/apache/iceberg/TestReplaceTransaction.java
index c6c46ed..f2b8243 100644
--- a/core/src/test/java/org/apache/iceberg/TestReplaceTransaction.java
+++ b/core/src/test/java/org/apache/iceberg/TestReplaceTransaction.java
@@ -21,10 +21,14 @@ package org.apache.iceberg;
 
 import java.io.File;
 import java.io.IOException;
+import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicInteger;
 import org.apache.iceberg.exceptions.CommitFailedException;
+import org.apache.iceberg.relocated.com.google.common.collect.Maps;
 import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.apache.iceberg.transforms.Transform;
+import org.apache.iceberg.transforms.Transforms;
 import org.apache.iceberg.types.TypeUtil;
 import org.apache.iceberg.types.Types;
 import org.junit.Assert;
@@ -32,7 +36,9 @@ import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
 
+import static org.apache.iceberg.NullOrder.NULLS_FIRST;
 import static org.apache.iceberg.PartitionSpec.unpartitioned;
+import static org.apache.iceberg.SortDirection.ASC;
 import static org.apache.iceberg.types.Types.NestedField.required;
 
 @RunWith(Parameterized.class)
@@ -50,6 +56,45 @@ public class TestReplaceTransaction extends TableTestBase {
   }
 
   @Test
+  public void testReplaceTransactionWithCustomSortOrder() {
+    Snapshot start = table.currentSnapshot();
+    Schema schema = table.schema();
+
+    table.newAppend()
+        .appendFile(FILE_A)
+        .commit();
+
+    Assert.assertEquals("Version should be 1", 1L, (long) version());
+
+    validateSnapshot(start, table.currentSnapshot(), FILE_A);
+
+    SortOrder newSortOrder = SortOrder.builderFor(schema)
+        .asc("id", NULLS_FIRST)
+        .build();
+
+    Map<String, String> props = Maps.newHashMap();
+    Transaction replace = TestTables.beginReplace(tableDir, "test", schema, unpartitioned(), newSortOrder, props);
+    replace.commitTransaction();
+
+    table.refresh();
+
+    Assert.assertEquals("Version should be 2", 2L, (long) version());
+    Assert.assertNull("Table should not have a current snapshot", table.currentSnapshot());
+    Assert.assertEquals("Schema should match previous schema",
+        schema.asStruct(), table.schema().asStruct());
+    Assert.assertEquals("Partition spec should have no fields",
+        0, table.spec().fields().size());
+    Assert.assertEquals("Table should have 2 orders", 2, table.sortOrders().size());
+    SortOrder sortOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must match", 1, sortOrder.orderId());
+    Assert.assertEquals("Order must have 1 field", 1, sortOrder.fields().size());
+    Assert.assertEquals("Direction must match ", ASC, sortOrder.fields().get(0).direction());
+    Assert.assertEquals("Null order must match ", NULLS_FIRST, sortOrder.fields().get(0).nullOrder());
+    Transform<?, ?> transform = Transforms.identity(Types.IntegerType.get());
+    Assert.assertEquals("Transform must match", transform, sortOrder.fields().get(0).transform());
+  }
+
+  @Test
   public void testReplaceTransaction() {
     Schema newSchema = new Schema(
         required(4, "id", Types.IntegerType.get()),
@@ -77,6 +122,9 @@ public class TestReplaceTransaction extends TableTestBase {
         schema.asStruct(), table.schema().asStruct());
     Assert.assertEquals("Partition spec should have no fields",
         0, table.spec().fields().size());
+    Assert.assertEquals("Table should have 1 order", 1, table.sortOrders().size());
+    Assert.assertEquals("Table order ID should match", 0, table.sortOrder().orderId());
+    Assert.assertTrue("Table should be unsorted", table.sortOrder().isUnsorted());
   }
 
   @Test
diff --git a/core/src/test/java/org/apache/iceberg/TestSortOrder.java b/core/src/test/java/org/apache/iceberg/TestSortOrder.java
new file mode 100644
index 0000000..abb1200
--- /dev/null
+++ b/core/src/test/java/org/apache/iceberg/TestSortOrder.java
@@ -0,0 +1,247 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iceberg;
+
+import java.io.File;
+import java.io.IOException;
+import org.apache.iceberg.exceptions.ValidationException;
+import org.apache.iceberg.types.Types;
+import org.junit.After;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import static org.apache.iceberg.NullOrder.NULLS_FIRST;
+import static org.apache.iceberg.NullOrder.NULLS_LAST;
+import static org.apache.iceberg.expressions.Expressions.truncate;
+import static org.apache.iceberg.types.Types.NestedField.optional;
+import static org.apache.iceberg.types.Types.NestedField.required;
+
+@RunWith(Parameterized.class)
+public class TestSortOrder {
+
+  // column ids will be reassigned during table creation
+  private static final Schema SCHEMA = new Schema(
+      required(10, "id", Types.IntegerType.get()),
+      required(11, "data", Types.StringType.get()),
+      optional(12, "s", Types.StructType.of(
+          required(17, "id", Types.IntegerType.get()),
+          optional(18, "b", Types.ListType.ofOptional(3, Types.StructType.of(
+              optional(19, "i", Types.IntegerType.get()),
+              optional(20, "s", Types.StringType.get())
+          )))
+      )),
+      required(30, "ext", Types.StringType.get()));
+
+  @Rule
+  public TemporaryFolder temp = new TemporaryFolder();
+  private File tableDir = null;
+
+  @Parameterized.Parameters
+  public static Object[][] parameters() {
+    return new Object[][] {
+        new Object[] { 1 },
+        new Object[] { 2 },
+    };
+  }
+
+  private final int formatVersion;
+
+  public TestSortOrder(int formatVersion) {
+    this.formatVersion = formatVersion;
+  }
+
+  @Before
+  public void setupTableDir() throws IOException {
+    this.tableDir = temp.newFolder();
+  }
+
+  @After
+  public void cleanupTables() {
+    TestTables.clearTables();
+  }
+
+  @Test
+  public void testSortOrderBuilder() {
+    Assert.assertEquals("Should be able to build unsorted order",
+        SortOrder.unsorted(),
+        SortOrder.builderFor(SCHEMA).withOrderId(0).build());
+
+    AssertHelpers.assertThrows("Should not allow sort orders ID 0",
+        IllegalArgumentException.class, "order ID 0 is reserved for unsorted order",
+        () -> SortOrder.builderFor(SCHEMA).asc("data").withOrderId(0).build());
+    AssertHelpers.assertThrows("Should not allow unsorted orders with arbitrary IDs",
+        IllegalArgumentException.class, "order ID must be 0",
+        () -> SortOrder.builderFor(SCHEMA).withOrderId(1).build());
+  }
+
+  @Test
+  public void testDefaultOrder() {
+    PartitionSpec spec = PartitionSpec.unpartitioned();
+    TestTables.TestTable table = TestTables.create(tableDir, "test", SCHEMA, spec, formatVersion);
+    Assert.assertEquals("Expected 1 sort order", 1, table.sortOrders().size());
+
+    SortOrder actualOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must match", 0, actualOrder.orderId());
+    Assert.assertTrue("Order must unsorted", actualOrder.isUnsorted());
+  }
+
+  @Test
+  public void testFreshIds() {
+    PartitionSpec spec = PartitionSpec.builderFor(SCHEMA)
+        .withSpecId(5)
+        .identity("data")
+        .build();
+    SortOrder order = SortOrder.builderFor(SCHEMA)
+        .withOrderId(10)
+        .asc("s.id", NULLS_LAST)
+        .desc(truncate("data", 10), NULLS_FIRST)
+        .build();
+    TestTables.TestTable table = TestTables.create(tableDir, "test", SCHEMA, spec, order, formatVersion);
+
+    Assert.assertEquals("Expected 1 sort order", 1, table.sortOrders().size());
+    Assert.assertTrue("Order ID must be fresh", table.sortOrders().containsKey(TableMetadata.INITIAL_SORT_ORDER_ID));
+
+    SortOrder actualOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must be fresh", TableMetadata.INITIAL_SORT_ORDER_ID, actualOrder.orderId());
+    Assert.assertEquals("Order must have 2 fields", 2, actualOrder.fields().size());
+    Assert.assertEquals("Field id must be fresh", 5, actualOrder.fields().get(0).sourceId());
+    Assert.assertEquals("Field id must be fresh", 2, actualOrder.fields().get(1).sourceId());
+  }
+
+  @Test
+  public void testCompatibleOrders() {
+    SortOrder order1 = SortOrder.builderFor(SCHEMA)
+        .withOrderId(9)
+        .asc("s.id", NULLS_LAST)
+        .build();
+
+    SortOrder order2 = SortOrder.builderFor(SCHEMA)
+        .withOrderId(10)
+        .asc("s.id", NULLS_LAST)
+        .desc(truncate("data", 10), NULLS_FIRST)
+        .build();
+
+    SortOrder order3 = SortOrder.builderFor(SCHEMA)
+        .withOrderId(11)
+        .asc("s.id", NULLS_LAST)
+        .desc(truncate("data", 10), NULLS_LAST)
+        .build();
+
+    SortOrder order4 = SortOrder.builderFor(SCHEMA)
+        .withOrderId(11)
+        .asc("s.id", NULLS_LAST)
+        .asc(truncate("data", 10), NULLS_FIRST)
+        .build();
+
+    SortOrder order5 = SortOrder.builderFor(SCHEMA)
+        .withOrderId(11)
+        .desc("s.id", NULLS_LAST)
+        .build();
+
+    // an unsorted order satisfies only itself
+    Assert.assertTrue(SortOrder.unsorted().satisfies(SortOrder.unsorted()));
+    Assert.assertFalse(SortOrder.unsorted().satisfies(order1));
+    Assert.assertFalse(SortOrder.unsorted().satisfies(order2));
+    Assert.assertFalse(SortOrder.unsorted().satisfies(order3));
+    Assert.assertFalse(SortOrder.unsorted().satisfies(order4));
+    Assert.assertFalse(SortOrder.unsorted().satisfies(order5));
+
+    // any ordering satisfies an unsorted ordering
+    Assert.assertTrue(order1.satisfies(SortOrder.unsorted()));
+    Assert.assertTrue(order2.satisfies(SortOrder.unsorted()));
+    Assert.assertTrue(order3.satisfies(SortOrder.unsorted()));
+    Assert.assertTrue(order4.satisfies(SortOrder.unsorted()));
+    Assert.assertTrue(order5.satisfies(SortOrder.unsorted()));
+
+    // order1 has the same fields but different sort direction compared to order5
+    Assert.assertFalse(order1.satisfies(order5));
+
+    // order2 has more fields than order1 and is compatible
+    Assert.assertTrue(order2.satisfies(order1));
+    // order2 has more fields than order5 but is incompatible
+    Assert.assertFalse(order2.satisfies(order5));
+    // order2 has the same fields but different null order compared to order3
+    Assert.assertFalse(order2.satisfies(order3));
+    // order2 has the same fields but different sort direction compared to order4
+    Assert.assertFalse(order2.satisfies(order4));
+
+    // order1 has fewer fields than order2 and is incompatible
+    Assert.assertFalse(order1.satisfies(order2));
+  }
+
+  @Test
+  public void testSameOrder() {
+    SortOrder order1 = SortOrder.builderFor(SCHEMA)
+        .withOrderId(9)
+        .asc("s.id", NULLS_LAST)
+        .build();
+
+    SortOrder order2 = SortOrder.builderFor(SCHEMA)
+        .withOrderId(10)
+        .asc("s.id", NULLS_LAST)
+        .build();
+
+    // orders have different ids but are logically the same
+    Assert.assertNotEquals("Orders must not be equal", order1, order2);
+    Assert.assertTrue("Orders must be equivalent", order1.sameOrder(order2));
+    Assert.assertTrue("Orders must be equivalent", order2.sameOrder(order1));
+  }
+
+  @Test
+  public void testSchemaEvolutionWithSortOrder() {
+    PartitionSpec spec = PartitionSpec.unpartitioned();
+    SortOrder order = SortOrder.builderFor(SCHEMA)
+        .withOrderId(10)
+        .asc("s.id")
+        .desc(truncate("data", 10))
+        .build();
+    TestTables.TestTable table = TestTables.create(tableDir, "test", SCHEMA, spec, order, formatVersion);
+
+    table.updateSchema()
+        .renameColumn("s.id", "s.id2")
+        .commit();
+
+    SortOrder actualOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must match", TableMetadata.INITIAL_SORT_ORDER_ID, actualOrder.orderId());
+    Assert.assertEquals("Order must have 2 fields", 2, actualOrder.fields().size());
+    Assert.assertEquals("Field id must match", 5, actualOrder.fields().get(0).sourceId());
+    Assert.assertEquals("Field id must match", 2, actualOrder.fields().get(1).sourceId());
+  }
+
+  @Test
+  public void testIncompatibleSchemaEvolutionWithSortOrder() {
+    PartitionSpec spec = PartitionSpec.unpartitioned();
+    SortOrder order = SortOrder.builderFor(SCHEMA)
+        .withOrderId(10)
+        .asc("s.id")
+        .desc(truncate("data", 10))
+        .build();
+    TestTables.TestTable table = TestTables.create(tableDir, "test", SCHEMA, spec, order, formatVersion);
+
+    AssertHelpers.assertThrows("Should reject deletion of sort columns",
+        ValidationException.class, "Cannot find source column",
+        () -> table.updateSchema().deleteColumn("s.id").commit());
+  }
+}
diff --git a/core/src/test/java/org/apache/iceberg/TestSortOrderParser.java b/core/src/test/java/org/apache/iceberg/TestSortOrderParser.java
new file mode 100644
index 0000000..0af850f
--- /dev/null
+++ b/core/src/test/java/org/apache/iceberg/TestSortOrderParser.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iceberg;
+
+import org.apache.iceberg.transforms.UnknownTransform;
+import org.junit.Assert;
+import org.junit.Test;
+
+import static org.apache.iceberg.NullOrder.NULLS_FIRST;
+import static org.apache.iceberg.SortDirection.DESC;
+
+public class TestSortOrderParser extends TableTestBase {
+  public TestSortOrderParser() {
+    super(1);
+  }
+
+  @Test
+  public void testUnknownTransforms() {
+    String jsonString = "{\n" +
+        "  \"order-id\" : 10,\n" +
+        "  \"fields\" : [ {\n" +
+        "    \"transform\" : \"custom_transform\",\n" +
+        "    \"source-id\" : 2,\n" +
+        "    \"direction\" : \"desc\",\n" +
+        "    \"null-order\" : \"nulls-first\"\n" +
+        "  } ]\n" +
+        "}";
+
+    SortOrder order = SortOrderParser.fromJson(table.schema(), jsonString);
+
+    Assert.assertEquals(10, order.orderId());
+    Assert.assertEquals(1, order.fields().size());
+    Assert.assertTrue(order.fields().get(0).transform() instanceof UnknownTransform);
+    Assert.assertEquals("custom_transform", order.fields().get(0).transform().toString());
+    Assert.assertEquals(2, order.fields().get(0).sourceId());
+    Assert.assertEquals(DESC, order.fields().get(0).direction());
+    Assert.assertEquals(NULLS_FIRST, order.fields().get(0).nullOrder());
+  }
+}
diff --git a/core/src/test/java/org/apache/iceberg/TestTableMetadata.java b/core/src/test/java/org/apache/iceberg/TestTableMetadata.java
index ac139e9..38512de 100644
--- a/core/src/test/java/org/apache/iceberg/TestTableMetadata.java
+++ b/core/src/test/java/org/apache/iceberg/TestTableMetadata.java
@@ -35,6 +35,7 @@ import java.util.UUID;
 import org.apache.iceberg.TableMetadata.MetadataLogEntry;
 import org.apache.iceberg.TableMetadata.SnapshotLogEntry;
 import org.apache.iceberg.exceptions.ValidationException;
+import org.apache.iceberg.expressions.Expressions;
 import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
 import org.apache.iceberg.relocated.com.google.common.collect.ImmutableMap;
 import org.apache.iceberg.relocated.com.google.common.collect.Lists;
@@ -71,6 +72,11 @@ public class TestTableMetadata {
   private static final int LAST_ASSIGNED_COLUMN_ID = 3;
 
   private static final PartitionSpec SPEC_5 = PartitionSpec.builderFor(TEST_SCHEMA).withSpecId(5).build();
+  private static final SortOrder SORT_ORDER_3 = SortOrder.builderFor(TEST_SCHEMA)
+      .withOrderId(3)
+      .asc("y", NullOrder.NULLS_FIRST)
+      .desc(Expressions.bucket("z", 4), NullOrder.NULLS_LAST)
+      .build();
 
   @Rule
   public TemporaryFolder temp = new TemporaryFolder();
@@ -95,7 +101,7 @@ public class TestTableMetadata {
 
     TableMetadata expected = new TableMetadata(null, 2, UUID.randomUUID().toString(), TEST_LOCATION,
         SEQ_NO, System.currentTimeMillis(), 3, TEST_SCHEMA, 5, ImmutableList.of(SPEC_5),
-        ImmutableMap.of("property", "value"), currentSnapshotId,
+        3, ImmutableList.of(SORT_ORDER_3), ImmutableMap.of("property", "value"), currentSnapshotId,
         Arrays.asList(previousSnapshot, currentSnapshot), snapshotLog, ImmutableList.of());
 
     String asJson = TableMetadataParser.toJson(expected);
@@ -140,6 +146,7 @@ public class TestTableMetadata {
   @Test
   public void testBackwardCompat() throws Exception {
     PartitionSpec spec = PartitionSpec.builderFor(TEST_SCHEMA).identity("x").withSpecId(6).build();
+    SortOrder sortOrder = SortOrder.unsorted();
 
     long previousSnapshotId = System.currentTimeMillis() - new Random(1234).nextInt(3600);
     Snapshot previousSnapshot = new BaseSnapshot(
@@ -152,8 +159,8 @@ public class TestTableMetadata {
 
     TableMetadata expected = new TableMetadata(null, 1, null, TEST_LOCATION,
         0, System.currentTimeMillis(), 3, TEST_SCHEMA, 6, ImmutableList.of(spec),
-        ImmutableMap.of("property", "value"), currentSnapshotId,
-        Arrays.asList(previousSnapshot, currentSnapshot), ImmutableList.of(), ImmutableList.of());
+        TableMetadata.INITIAL_SORT_ORDER_ID, ImmutableList.of(sortOrder), ImmutableMap.of("property", "value"),
+        currentSnapshotId, Arrays.asList(previousSnapshot, currentSnapshot), ImmutableList.of(), ImmutableList.of());
 
     String asJson = toJsonWithoutSpecList(expected);
     TableMetadata metadata = TableMetadataParser
@@ -262,7 +269,7 @@ public class TestTableMetadata {
 
     TableMetadata base = new TableMetadata(null, 1, UUID.randomUUID().toString(), TEST_LOCATION,
         0, System.currentTimeMillis(), 3, TEST_SCHEMA, 5, ImmutableList.of(SPEC_5),
-        ImmutableMap.of("property", "value"), currentSnapshotId,
+        3, ImmutableList.of(SORT_ORDER_3), ImmutableMap.of("property", "value"), currentSnapshotId,
         Arrays.asList(previousSnapshot, currentSnapshot), reversedSnapshotLog,
         ImmutableList.copyOf(previousMetadataLog));
 
@@ -297,7 +304,7 @@ public class TestTableMetadata {
 
     TableMetadata base = new TableMetadata(localInput(latestPreviousMetadata.file()), 1, UUID.randomUUID().toString(),
         TEST_LOCATION, 0, currentTimestamp - 80, 3, TEST_SCHEMA, 5, ImmutableList.of(SPEC_5),
-        ImmutableMap.of("property", "value"), currentSnapshotId,
+        3, ImmutableList.of(SORT_ORDER_3), ImmutableMap.of("property", "value"), currentSnapshotId,
         Arrays.asList(previousSnapshot, currentSnapshot), reversedSnapshotLog,
         ImmutableList.copyOf(previousMetadataLog));
 
@@ -342,7 +349,8 @@ public class TestTableMetadata {
 
     TableMetadata base = new TableMetadata(localInput(latestPreviousMetadata.file()), 1, UUID.randomUUID().toString(),
         TEST_LOCATION, 0, currentTimestamp - 50, 3, TEST_SCHEMA, 5,
-        ImmutableList.of(SPEC_5), ImmutableMap.of("property", "value"), currentSnapshotId,
+        ImmutableList.of(SPEC_5), 3, ImmutableList.of(SORT_ORDER_3),
+        ImmutableMap.of("property", "value"), currentSnapshotId,
         Arrays.asList(previousSnapshot, currentSnapshot), reversedSnapshotLog,
         ImmutableList.copyOf(previousMetadataLog));
 
@@ -392,7 +400,8 @@ public class TestTableMetadata {
 
     TableMetadata base = new TableMetadata(localInput(latestPreviousMetadata.file()), 1, UUID.randomUUID().toString(),
         TEST_LOCATION, 0, currentTimestamp - 50, 3, TEST_SCHEMA, 2,
-        ImmutableList.of(SPEC_5), ImmutableMap.of("property", "value"), currentSnapshotId,
+        ImmutableList.of(SPEC_5), TableMetadata.INITIAL_SORT_ORDER_ID, ImmutableList.of(SortOrder.unsorted()),
+        ImmutableMap.of("property", "value"), currentSnapshotId,
         Arrays.asList(previousSnapshot, currentSnapshot), reversedSnapshotLog,
         ImmutableList.copyOf(previousMetadataLog));
 
@@ -417,7 +426,8 @@ public class TestTableMetadata {
     AssertHelpers.assertThrows("Should reject v2 metadata without a UUID",
         IllegalArgumentException.class, "UUID is required in format v2",
         () -> new TableMetadata(null, 2, null, TEST_LOCATION, SEQ_NO, System.currentTimeMillis(),
-            LAST_ASSIGNED_COLUMN_ID, TEST_SCHEMA, SPEC_5.specId(), ImmutableList.of(SPEC_5), ImmutableMap.of(), -1L,
+            LAST_ASSIGNED_COLUMN_ID, TEST_SCHEMA, SPEC_5.specId(), ImmutableList.of(SPEC_5),
+            3, ImmutableList.of(SORT_ORDER_3), ImmutableMap.of(), -1L,
             ImmutableList.of(), ImmutableList.of(), ImmutableList.of())
     );
   }
@@ -429,7 +439,8 @@ public class TestTableMetadata {
         IllegalArgumentException.class, "Unsupported format version: v" + unsupportedVersion,
         () -> new TableMetadata(null, unsupportedVersion, null, TEST_LOCATION, SEQ_NO,
             System.currentTimeMillis(), LAST_ASSIGNED_COLUMN_ID, TEST_SCHEMA, SPEC_5.specId(), ImmutableList.of(SPEC_5),
-            ImmutableMap.of(), -1L, ImmutableList.of(), ImmutableList.of(), ImmutableList.of())
+            3, ImmutableList.of(SORT_ORDER_3), ImmutableMap.of(), -1L,
+            ImmutableList.of(), ImmutableList.of(), ImmutableList.of())
     );
   }
 
diff --git a/core/src/test/java/org/apache/iceberg/TestTables.java b/core/src/test/java/org/apache/iceberg/TestTables.java
index 9ed1e63..2e0ecd6 100644
--- a/core/src/test/java/org/apache/iceberg/TestTables.java
+++ b/core/src/test/java/org/apache/iceberg/TestTables.java
@@ -48,41 +48,52 @@ public class TestTables {
   }
 
   public static TestTable create(File temp, String name, Schema schema, PartitionSpec spec, int formatVersion) {
+    return create(temp, name, schema, spec, SortOrder.unsorted(), formatVersion);
+  }
+
+  public static TestTable create(File temp, String name, Schema schema, PartitionSpec spec,
+                                 SortOrder sortOrder, int formatVersion) {
     TestTableOperations ops = new TestTableOperations(name, temp);
     if (ops.current() != null) {
       throw new AlreadyExistsException("Table %s already exists at location: %s", name, temp);
     }
-    ops.commit(null, TableMetadata.newTableMetadata(schema, spec, temp.toString(), ImmutableMap.of(), formatVersion));
+
+    ops.commit(null, newTableMetadata(schema, spec, sortOrder, temp.toString(), ImmutableMap.of(), formatVersion));
+
     return new TestTable(ops, name);
   }
 
   public static Transaction beginCreate(File temp, String name, Schema schema, PartitionSpec spec) {
+    return beginCreate(temp, name, schema, spec, SortOrder.unsorted());
+  }
+
+  public static Transaction beginCreate(File temp, String name, Schema schema,
+                                        PartitionSpec spec, SortOrder sortOrder) {
     TableOperations ops = new TestTableOperations(name, temp);
     if (ops.current() != null) {
       throw new AlreadyExistsException("Table %s already exists at location: %s", name, temp);
     }
 
-    TableMetadata metadata = TableMetadata.newTableMetadata(
-        schema, spec, temp.toString(), ImmutableMap.of(), 1);
+    TableMetadata metadata = newTableMetadata(schema, spec, sortOrder, temp.toString(), ImmutableMap.of(), 1);
 
     return Transactions.createTableTransaction(name, ops, metadata);
   }
 
   public static Transaction beginReplace(File temp, String name, Schema schema, PartitionSpec spec) {
-    return beginReplace(temp, name, schema, spec, ImmutableMap.of());
+    return beginReplace(temp, name, schema, spec, SortOrder.unsorted(), ImmutableMap.of());
   }
 
   public static Transaction beginReplace(File temp, String name, Schema schema, PartitionSpec spec,
-                                         Map<String, String> properties) {
+                                         SortOrder sortOrder, Map<String, String> properties) {
     TestTableOperations ops = new TestTableOperations(name, temp);
     TableMetadata current = ops.current();
 
     TableMetadata metadata;
     if (current != null) {
-      metadata = current.buildReplacement(schema, spec, current.location(), properties);
+      metadata = current.buildReplacement(schema, spec, sortOrder, current.location(), properties);
       return Transactions.replaceTableTransaction(name, ops, metadata);
     } else {
-      metadata = newTableMetadata(schema, spec, temp.toString(), properties);
+      metadata = newTableMetadata(schema, spec, sortOrder, temp.toString(), properties);
       return Transactions.createTableTransaction(name, ops, metadata);
     }
   }
diff --git a/core/src/test/java/org/apache/iceberg/hadoop/TestHadoopCatalog.java b/core/src/test/java/org/apache/iceberg/hadoop/TestHadoopCatalog.java
index 5d427d5..3494a91 100644
--- a/core/src/test/java/org/apache/iceberg/hadoop/TestHadoopCatalog.java
+++ b/core/src/test/java/org/apache/iceberg/hadoop/TestHadoopCatalog.java
@@ -27,6 +27,7 @@ import org.apache.hadoop.fs.FileSystem;
 import org.apache.hadoop.fs.Path;
 import org.apache.iceberg.AssertHelpers;
 import org.apache.iceberg.PartitionSpec;
+import org.apache.iceberg.SortOrder;
 import org.apache.iceberg.Table;
 import org.apache.iceberg.Transaction;
 import org.apache.iceberg.catalog.Namespace;
@@ -36,9 +37,15 @@ import org.apache.iceberg.exceptions.NoSuchNamespaceException;
 import org.apache.iceberg.relocated.com.google.common.collect.ImmutableMap;
 import org.apache.iceberg.relocated.com.google.common.collect.Lists;
 import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.apache.iceberg.transforms.Transform;
+import org.apache.iceberg.transforms.Transforms;
+import org.apache.iceberg.types.Types;
 import org.junit.Assert;
 import org.junit.Test;
 
+import static org.apache.iceberg.NullOrder.NULLS_FIRST;
+import static org.apache.iceberg.SortDirection.ASC;
+
 public class TestHadoopCatalog extends HadoopTableTestBase {
   private static ImmutableMap<String, String> meta = ImmutableMap.of();
 
@@ -131,6 +138,42 @@ public class TestHadoopCatalog extends HadoopTableTestBase {
   }
 
   @Test
+  public void testCreateTableDefaultSortOrder() throws Exception {
+    Configuration conf = new Configuration();
+    String warehousePath = temp.newFolder().getAbsolutePath();
+    HadoopCatalog catalog = new HadoopCatalog(conf, warehousePath);
+    TableIdentifier tableIdent = TableIdentifier.of("db", "ns1", "ns2", "tbl");
+    Table table = catalog.createTable(tableIdent, SCHEMA, SPEC);
+
+    SortOrder sortOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must match", 0, sortOrder.orderId());
+    Assert.assertTrue("Order must unsorted", sortOrder.isUnsorted());
+  }
+
+  @Test
+  public void testCreateTableCustomSortOrder() throws Exception {
+    Configuration conf = new Configuration();
+    String warehousePath = temp.newFolder().getAbsolutePath();
+    HadoopCatalog catalog = new HadoopCatalog(conf, warehousePath);
+    TableIdentifier tableIdent = TableIdentifier.of("db", "ns1", "ns2", "tbl");
+    SortOrder order = SortOrder.builderFor(SCHEMA)
+        .asc("id", NULLS_FIRST)
+        .build();
+    Table table = catalog.buildTable(tableIdent, SCHEMA)
+        .withPartitionSpec(SPEC)
+        .withSortOrder(order)
+        .create();
+
+    SortOrder sortOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must match", 1, sortOrder.orderId());
+    Assert.assertEquals("Order must have 1 field", 1, sortOrder.fields().size());
+    Assert.assertEquals("Direction must match ", ASC, sortOrder.fields().get(0).direction());
+    Assert.assertEquals("Null order must match ", NULLS_FIRST, sortOrder.fields().get(0).nullOrder());
+    Transform<?, ?> transform = Transforms.identity(Types.IntegerType.get());
+    Assert.assertEquals("Transform must match", transform, sortOrder.fields().get(0).transform());
+  }
+
+  @Test
   public void testBasicCatalog() throws Exception {
     Configuration conf = new Configuration();
     String warehousePath = temp.newFolder().getAbsolutePath();
diff --git a/core/src/test/java/org/apache/iceberg/hadoop/TestHadoopTablesSortOrder.java b/core/src/test/java/org/apache/iceberg/hadoop/TestHadoopTablesSortOrder.java
new file mode 100644
index 0000000..0b4e714
--- /dev/null
+++ b/core/src/test/java/org/apache/iceberg/hadoop/TestHadoopTablesSortOrder.java
@@ -0,0 +1,89 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iceberg.hadoop;
+
+import java.io.File;
+import org.apache.iceberg.PartitionSpec;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.collect.Maps;
+import org.apache.iceberg.transforms.Transform;
+import org.apache.iceberg.transforms.Transforms;
+import org.apache.iceberg.types.Types;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+import static org.apache.iceberg.NullOrder.NULLS_FIRST;
+import static org.apache.iceberg.SortDirection.ASC;
+import static org.apache.iceberg.types.Types.NestedField.required;
+
+public class TestHadoopTablesSortOrder {
+
+  private static final HadoopTables TABLES = new HadoopTables();
+  private static final Schema SCHEMA = new Schema(
+      required(1, "id", Types.IntegerType.get(), "unique ID"),
+      required(2, "data", Types.StringType.get())
+  );
+
+  @Rule
+  public TemporaryFolder temp = new TemporaryFolder();
+  private String tableLocation = null;
+
+  @Before
+  public void setupTableLocation() throws Exception {
+    File tableDir = temp.newFolder();
+    this.tableLocation = tableDir.toURI().toString();
+  }
+
+  @Test
+  public void testDefaultSortOrder() {
+    PartitionSpec spec = PartitionSpec.builderFor(SCHEMA)
+        .bucket("data", 16)
+        .build();
+    Table table = TABLES.create(SCHEMA, spec, tableLocation);
+
+    SortOrder sortOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must match", 0, sortOrder.orderId());
+    Assert.assertTrue("Order must unsorted", sortOrder.isUnsorted());
+  }
+
+  @Test
+  public void testCustomSortOrder() {
+    PartitionSpec spec = PartitionSpec.builderFor(SCHEMA)
+        .bucket("data", 16)
+        .build();
+    SortOrder order = SortOrder.builderFor(SCHEMA)
+        .asc("id", NULLS_FIRST)
+        .build();
+    Table table = TABLES.create(SCHEMA, spec, order, Maps.newHashMap(), tableLocation);
+
+    SortOrder sortOrder = table.sortOrder();
+    Assert.assertEquals("Order ID must match", 1, sortOrder.orderId());
+    Assert.assertEquals("Order must have 1 field", 1, sortOrder.fields().size());
+    Assert.assertEquals("Direction must match ", ASC, sortOrder.fields().get(0).direction());
+    Assert.assertEquals("Null order must match ", NULLS_FIRST, sortOrder.fields().get(0).nullOrder());
+    Transform<?, ?> transform = Transforms.identity(Types.IntegerType.get());
+    Assert.assertEquals("Transform must match", transform, sortOrder.fields().get(0).transform());
+  }
+}
diff --git a/hive-metastore/src/test/java/org/apache/iceberg/hive/TestHiveCatalog.java b/hive-metastore/src/test/java/org/apache/iceberg/hive/TestHiveCatalog.java
index 061c437..f1cdade 100644
--- a/hive-metastore/src/test/java/org/apache/iceberg/hive/TestHiveCatalog.java
+++ b/hive-metastore/src/test/java/org/apache/iceberg/hive/TestHiveCatalog.java
@@ -27,6 +27,7 @@ import org.apache.iceberg.AssertHelpers;
 import org.apache.iceberg.CachingCatalog;
 import org.apache.iceberg.PartitionSpec;
 import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortOrder;
 import org.apache.iceberg.Table;
 import org.apache.iceberg.Transaction;
 import org.apache.iceberg.catalog.Catalog;
@@ -37,6 +38,8 @@ import org.apache.iceberg.exceptions.NamespaceNotEmptyException;
 import org.apache.iceberg.exceptions.NoSuchNamespaceException;
 import org.apache.iceberg.relocated.com.google.common.collect.ImmutableMap;
 import org.apache.iceberg.relocated.com.google.common.collect.ImmutableSet;
+import org.apache.iceberg.transforms.Transform;
+import org.apache.iceberg.transforms.Transforms;
 import org.apache.iceberg.types.Types;
 import org.apache.thrift.TException;
 import org.junit.Assert;
@@ -44,6 +47,8 @@ import org.junit.Rule;
 import org.junit.Test;
 import org.junit.rules.TemporaryFolder;
 
+import static org.apache.iceberg.NullOrder.NULLS_FIRST;
+import static org.apache.iceberg.SortDirection.ASC;
 import static org.apache.iceberg.types.Types.NestedField.required;
 
 public class TestHiveCatalog extends HiveMetastoreTest {
@@ -180,6 +185,57 @@ public class TestHiveCatalog extends HiveMetastoreTest {
   }
 
   @Test
+  public void testCreateTableDefaultSortOrder() {
+    Schema schema = new Schema(
+        required(1, "id", Types.IntegerType.get(), "unique ID"),
+        required(2, "data", Types.StringType.get())
+    );
+    PartitionSpec spec = PartitionSpec.builderFor(schema)
+        .bucket("data", 16)
+        .build();
+    TableIdentifier tableIdent = TableIdentifier.of(DB_NAME, "tbl");
+
+    try {
+      Table table = catalog.createTable(tableIdent, schema, spec);
+      Assert.assertEquals("Order ID must match", 0, table.sortOrder().orderId());
+      Assert.assertTrue("Order must unsorted", table.sortOrder().isUnsorted());
+    } finally {
+      catalog.dropTable(tableIdent);
+    }
+  }
+
+  @Test
+  public void testCreateTableCustomSortOrder() {
+    Schema schema = new Schema(
+        required(1, "id", Types.IntegerType.get(), "unique ID"),
+        required(2, "data", Types.StringType.get())
+    );
+    PartitionSpec spec = PartitionSpec.builderFor(schema)
+        .bucket("data", 16)
+        .build();
+    SortOrder order = SortOrder.builderFor(schema)
+        .asc("id", NULLS_FIRST)
+        .build();
+    TableIdentifier tableIdent = TableIdentifier.of(DB_NAME, "tbl");
+
+    try {
+      Table table = catalog.buildTable(tableIdent, schema)
+          .withPartitionSpec(spec)
+          .withSortOrder(order)
+          .create();
+      SortOrder sortOrder = table.sortOrder();
+      Assert.assertEquals("Order ID must match", 1, sortOrder.orderId());
+      Assert.assertEquals("Order must have 1 field", 1, sortOrder.fields().size());
+      Assert.assertEquals("Direction must match ", ASC, sortOrder.fields().get(0).direction());
+      Assert.assertEquals("Null order must match ", NULLS_FIRST, sortOrder.fields().get(0).nullOrder());
+      Transform<?, ?> transform = Transforms.identity(Types.IntegerType.get());
+      Assert.assertEquals("Transform must match", transform, sortOrder.fields().get(0).transform());
+    } finally {
+      catalog.dropTable(tableIdent);
+    }
+  }
+
+  @Test
   public void testCreateNamespace() throws TException {
     Namespace namespace1 = Namespace.of("noLocation");
     catalog.createNamespace(namespace1, meta);
diff --git a/mr/src/test/java/org/apache/iceberg/mr/hive/TestTables.java b/mr/src/test/java/org/apache/iceberg/mr/hive/TestTables.java
index 0828a6f..db7642a 100644
--- a/mr/src/test/java/org/apache/iceberg/mr/hive/TestTables.java
+++ b/mr/src/test/java/org/apache/iceberg/mr/hive/TestTables.java
@@ -27,6 +27,7 @@ import java.util.Map;
 import org.apache.hadoop.conf.Configuration;
 import org.apache.iceberg.PartitionSpec;
 import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortOrder;
 import org.apache.iceberg.Table;
 import org.apache.iceberg.Tables;
 import org.apache.iceberg.catalog.Catalog;
@@ -79,8 +80,14 @@ abstract class TestTables {
     }
 
     @Override
-    public Table create(Schema schema, PartitionSpec spec, Map<String, String> properties, String tableIdentifier) {
-      return catalog.createTable(TableIdentifier.parse(tableIdentifier), schema, spec, properties);
+    public Table create(Schema schema, PartitionSpec spec, SortOrder sortOrder,
+                        Map<String, String> properties, String tableIdentifier) {
+      TableIdentifier tableIdent = TableIdentifier.parse(tableIdentifier);
+      return catalog.buildTable(tableIdent, schema)
+          .withPartitionSpec(spec)
+          .withSortOrder(sortOrder)
+          .withProperties(properties)
+          .create();
     }
 
     @Override