diff --git a/daemon/table/cs-entry-impl.cpp b/daemon/table/cs-entry-impl.cpp
index c97d692..9e1c1cd 100644
--- a/daemon/table/cs-entry-impl.cpp
+++ b/daemon/table/cs-entry-impl.cpp
@@ -61,6 +61,38 @@
   this->setData(this->getData(), false);
 }
 
+int
+compareQueryWithData(const Name& queryName, const Data& data)
+{
+  bool queryIsFullName = !queryName.empty() && queryName[-1].isImplicitSha256Digest();
+
+  int cmp = queryIsFullName ?
+            queryName.compare(0, queryName.size() - 1, data.getName()) :
+            queryName.compare(data.getName());
+
+  if (cmp != 0) { // Name without digest differs
+    return cmp;
+  }
+
+  if (queryIsFullName) { // Name without digest equals, compare digest
+    return queryName[-1].compare(data.getFullName()[-1]);
+  }
+  else { // queryName is a proper prefix of Data fullName
+    return -1;
+  }
+}
+
+int
+compareDataWithData(const Data& lhs, const Data& rhs)
+{
+  int cmp = lhs.getName().compare(rhs.getName());
+  if (cmp != 0) {
+    return cmp;
+  }
+
+  return lhs.getFullName()[-1].compare(rhs.getFullName()[-1]);
+}
+
 bool
 EntryImpl::operator<(const EntryImpl& other) const
 {
@@ -69,15 +101,15 @@
       return m_queryName < other.m_queryName;
     }
     else {
-      return m_queryName < other.m_queryName;
+      return compareQueryWithData(m_queryName, other.getData()) < 0;
     }
   }
   else {
     if (other.isQuery()) {
-      return this->getFullName() < other.m_queryName;
+      return compareQueryWithData(other.m_queryName, this->getData()) > 0;
     }
     else {
-      return this->getFullName() < other.getFullName();
+      return compareDataWithData(this->getData(), other.getData()) < 0;
     }
   }
 }
diff --git a/tests/other/cs-benchmark.cpp b/tests/other/cs-benchmark.cpp
index 71c9e10..78f7c1b 100644
--- a/tests/other/cs-benchmark.cpp
+++ b/tests/other/cs-benchmark.cpp
@@ -110,43 +110,47 @@
 // find miss, then insert
 BOOST_AUTO_TEST_CASE(FindMissInsert)
 {
-  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(CS_CAPACITY);
+  const size_t N_WORKLOAD = CS_CAPACITY * 2;
   const size_t REPEAT = 4;
+
+  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_WORKLOAD);
   std::vector<shared_ptr<Data>> dataWorkload[REPEAT];
   for (size_t j = 0; j < REPEAT; ++j) {
-    dataWorkload[j] = makeDataWorkload(CS_CAPACITY);
+    dataWorkload[j] = makeDataWorkload(N_WORKLOAD);
   }
 
   time::microseconds d = timedRun([&] {
     for (size_t j = 0; j < REPEAT; ++j) {
-      for (size_t i = 0; i < CS_CAPACITY; ++i) {
+      for (size_t i = 0; i < N_WORKLOAD; ++i) {
         cs.find(*interestWorkload[i]);
         cs.insert(*dataWorkload[j][i], false);
       }
     }
   });
-  BOOST_TEST_MESSAGE("find(miss)-insert " << (CS_CAPACITY * REPEAT) << ": " << d);
+  BOOST_TEST_MESSAGE("find(miss)-insert " << (N_WORKLOAD * REPEAT) << ": " << d);
 }
 
 // insert, then find hit
 BOOST_AUTO_TEST_CASE(InsertFindHit)
 {
-  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(CS_CAPACITY);
+  const size_t N_WORKLOAD = CS_CAPACITY * 2;
   const size_t REPEAT = 4;
+
+  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_WORKLOAD);
   std::vector<shared_ptr<Data>> dataWorkload[REPEAT];
   for (size_t j = 0; j < REPEAT; ++j) {
-    dataWorkload[j] = makeDataWorkload(CS_CAPACITY);
+    dataWorkload[j] = makeDataWorkload(N_WORKLOAD);
   }
 
   time::microseconds d = timedRun([&] {
     for (size_t j = 0; j < REPEAT; ++j) {
-      for (size_t i = 0; i < CS_CAPACITY; ++i) {
+      for (size_t i = 0; i < N_WORKLOAD; ++i) {
         cs.insert(*dataWorkload[j][i], false);
         cs.find(*interestWorkload[i]);
       }
     }
   });
-  BOOST_TEST_MESSAGE("insert-find(hit) " << (CS_CAPACITY * REPEAT) << ": " << d);
+  BOOST_TEST_MESSAGE("insert-find(hit) " << (N_WORKLOAD * REPEAT) << ": " << d);
 }
 
 // find(leftmost) hit