diff --git a/core/lib/Drupal/Core/Cache/DatabaseBackend.php b/core/lib/Drupal/Core/Cache/DatabaseBackend.php
index c579c06744..6468d39ab4 100644
--- a/core/lib/Drupal/Core/Cache/DatabaseBackend.php
+++ b/core/lib/Drupal/Core/Cache/DatabaseBackend.php
@@ -62,7 +62,7 @@ class DatabaseBackend implements CacheBackendInterface {
    * @param int $max_rows
    *   (optional) The maximum number of rows that are allowed in this cache bin table.
    */
-  public function __construct(Connection $connection, CacheTagsChecksumInterface $checksum_provider, $bin, $max_rows = 50000) {
+  public function __construct(Connection $connection, CacheTagsChecksumInterface $checksum_provider, $bin, $max_rows = 10000) {
     // All cache tables should be prefixed with 'cache_'.
     $bin = 'cache_' . $bin;
 
@@ -345,16 +345,16 @@ public function garbageCollection() {
     try {
       // Bounded size cache bin, using FIFO.
       if ($this->maxRows !== static::MAXIMUM_NONE) {
-        $first_invalid_cid = $this->connection->select($this->bin)
-          ->fields($this->bin, ['cid'])
-          ->orderBy("{$this->bin}.cid", 'ASC')
+        $first_invalid_create_time = $this->connection->select($this->bin)
+          ->fields($this->bin, ['created'])
+          ->orderBy("{$this->bin}.created", 'DESC')
           ->range($this->maxRows, $this->maxRows + 1)
           ->execute()
           ->fetchField();
 
-        if ($first_invalid_cid) {
+        if ($first_invalid_create_time) {
           $this->connection->delete($this->bin)
-            ->condition("{$this->bin}.cid", $first_invalid_cid, '<')
+            ->condition('created', $first_invalid_create_time, '<=')
             ->execute();
         }
       }
@@ -505,6 +505,7 @@ public function schemaDefinition() {
       ],
       'indexes' => [
         'expire' => ['expire'],
+         'created' => ['created'],
       ],
       'primary key' => ['cid'],
     ];
diff --git a/core/modules/system/system.install b/core/modules/system/system.install
index a4ffffabc5..48fd7f6e0d 100644
--- a/core/modules/system/system.install
+++ b/core/modules/system/system.install
@@ -10,6 +10,8 @@
 use Drupal\Component\FileSystem\FileSystem;
 use Drupal\Component\Utility\OpCodeCache;
 use Drupal\Component\Utility\Unicode;
+use Drupal\Core\Cache\Cache;
+use Drupal\Core\Cache\DatabaseBackend;
 use Drupal\Core\Path\AliasStorage;
 use Drupal\Core\Url;
 use Drupal\Core\Database\Database;
@@ -1984,3 +1986,20 @@ function system_update_8401() {
     ->clear('response')
     ->save();
 }
+
+
+/**
+* Delete all cache_* tables. They are recreated on demand with the new schema.
+*/
+function system_update_8402() {
+  foreach (Cache::getBins() as $bin => $cache_backend) {
+    if ($cache_backend instanceof DatabaseBackend) {
+      $table_name = "cache_$bin";
+      $schema = Database::getConnection()->schema();
+      if ($schema->tableExists($table_name)) {
+        $schema->dropTable($table_name);
+      }
+    }
+  }
+}
+