diff -u b/core/lib/Drupal/Core/Config/Entity/Query/Condition.php b/core/lib/Drupal/Core/Config/Entity/Query/Condition.php
--- b/core/lib/Drupal/Core/Config/Entity/Query/Condition.php
+++ b/core/lib/Drupal/Core/Config/Entity/Query/Condition.php
@@ -7,7 +7,6 @@
 
 namespace Drupal\Core\Config\Entity\Query;
 
-use Drupal\Component\Utility\NestedArray;
 use Drupal\Core\Entity\Query\ConditionBase;
 use Drupal\Core\Entity\Query\ConditionInterface;
 
@@ -18,36 +17,24 @@
    */
   public function compile($configs) {
     $and = strtoupper($this->conjunction) == 'AND';
-    $simple_conditions = array();
-    $complex_conditions = array();
+    $single_conditions = array();
+    $condition_groups = array();
     foreach ($this->conditions as $condition) {
       if ($condition['field'] instanceOf ConditionInterface) {
-        // Complex conditions contain a group of conditions and are handled
-        // by recursive calls.
-        $complex_conditions[] = $condition;
+        $condition_groups[] = $condition;
       }
       else {
-        // Simple conditions just contain a field, a value and an operator and
-        // handled without an extra function call.
-        // The field might contain a wildcard.
-        $condition['wildcard'] = strpos($condition['field'], '*') !== FALSE;
-        $simple_conditions[] = $condition;
+        if (!isset($condition['operator'])) {
+          $condition['operator'] = is_array($condition['value']) ? 'IN' : '=';
+        }
+        $single_conditions[] = $condition;
       }
     }
     $return = array();
-    if ($simple_conditions) {
+    if ($single_conditions) {
       foreach ($configs as $config_name => $config) {
-        foreach ($simple_conditions as &$condition) {
-          if (!isset($condition['operator'])) {
-            $condition['operator'] = is_array($condition['value']) ? 'IN' : '=';
-          }
-          if ($condition['wildcard']) {
-            $match = $this->matchWildcard($condition, $config, explode('.', $condition['field']));
-          }
-          else {
-            $key = $condition['field'];
-            $match = $this->match($condition, isset($config[$key]) ? $config[$key] : NULL);
-          }
+        foreach ($single_conditions as $condition) {
+          $match = $this->matchArray($condition, $config, explode('.', $condition['field']));
           // If AND and it's not matching, then the rest of conditions do not
           // matter and this config object does not match.
           // If OR and it is matching, then the rest of conditions do not
@@ -61,15 +48,15 @@
         }
       }
     }
-    elseif (!$complex_conditions || $and) {
-      // If there were no simple conditions then either:
+    elseif (!$condition_groups || $and) {
+      // If there were no single conditions then either:
       // - Complex conditions, OR: need to start from no entities.
       // - Complex conditions, AND: need to start from all entities.
       // - No complex conditions (AND/OR doesn't matter): need to return all
       //   entities.
       $return = $configs;
     }
-    foreach ($complex_conditions as $condition) {
+    foreach ($condition_groups as $condition) {
       $group_entities = $condition['field']->compile($configs);
       if ($and) {
         $return = array_intersect_key($return, $group_entities);
@@ -83,46 +70,6 @@
   }
 
   /**
-   * Do the actual matching.
-   *
-   * @param $condition
-   *   The condition array as created by the condition() method.
-   * @param $value
-   *   The value to match against.
-   * @return bool
-   *   TRUE when matches.
-   */
-  function match($condition, $value) {
-    if (isset($value)) {
-      switch ($condition['operator']) {
-        case '=':
-          return $value == $condition['value'];
-        case '>':
-          return $value > $condition['value'];
-        case '<':
-          return $value < $condition['value'];
-        case '>=':
-          return $value >= $condition['value'];
-        case '<=':
-          return $value <= $condition['value'];
-        case 'IN':
-          return array_search($value, $condition['value']) !== FALSE;
-        case 'NOT IN':
-          return array_search($value, $condition['value']) === FALSE;
-        case 'STARTS_WITH':
-          return strpos($value, $condition['value']) === 0;
-        case 'CONTAINS':
-          return strpos($value, $condition['value']) !== FALSE;
-        case 'ENDS_WITH':
-          return substr($value, -strlen($condition['value'])) === (string) $condition['value'];
-        case 'IS NOT NULL':
-          return TRUE;
-      }
-    }
-    return $condition['operator'] === 'IS NULL';
-  }
-
-  /**
    * Implements \Drupal\Core\Entity\Query\ConditionInterface::exists().
    */
   public function exists($field, $langcode = NULL) {
@@ -137,20 +84,21 @@
   }
 
   /**
-   * Match when the condition field contains a wildcard.
+   * Match for an array representing one or more config paths.
    *
    * @param $condition
    *   The condition array as created by the condition() method.
    * @param array $data
    *   The config array or part of it.
    * @param array $needs_matching
-   *   The list of config array keys needing a match.
+   *   The list of config array keys needing a match. Can contain config keys
+   *   and the * wildcard.
    * @param array $parents
    *   The current list of parents.
    * @return bool
    *   TRUE when matched.
    */
-  function matchWildcard($condition, array $data, array $needs_matching, array $parents = array()) {
+  protected function matchArray($condition, array $data, array $needs_matching, array $parents = array()) {
     $parent = array_shift($needs_matching);
     $candidates = array();
     if ($parent === '*') {
@@ -160,10 +108,12 @@
       $candidates = array($parent);
     }
     foreach ($candidates as $key) {
-      $new_parents = $parents;
-      $new_parents[] = $key;
-      if (is_array($data[$key]) && $needs_matching) {
-        return $this->matchWildcard($condition, $data[$key], $needs_matching, $new_parents);
+      if ($needs_matching && is_array($data[$key])) {
+        $new_parents = $parents;
+        $new_parents[] = $key;
+        if ($this->matchArray($condition, $data[$key], $needs_matching, $new_parents)) {
+          return TRUE;
+        }
       }
       elseif ($this->match($condition, $data[$key])) {
         return TRUE;
@@ -174,2 +124,42 @@
 
+  /**
+   * Do the actual matching.
+   *
+   * @param $condition
+   *   The condition array as created by the condition() method.
+   * @param $value
+   *   The value to match against.
+   * @return bool
+   *   TRUE when matches.
+   */
+  function match($condition, $value) {
+    if (isset($value)) {
+      switch ($condition['operator']) {
+        case '=':
+          return $value == $condition['value'];
+        case '>':
+          return $value > $condition['value'];
+        case '<':
+          return $value < $condition['value'];
+        case '>=':
+          return $value >= $condition['value'];
+        case '<=':
+          return $value <= $condition['value'];
+        case 'IN':
+          return array_search($value, $condition['value']) !== FALSE;
+        case 'NOT IN':
+          return array_search($value, $condition['value']) === FALSE;
+        case 'STARTS_WITH':
+          return strpos($value, $condition['value']) === 0;
+        case 'CONTAINS':
+          return strpos($value, $condition['value']) !== FALSE;
+        case 'ENDS_WITH':
+          return substr($value, -strlen($condition['value'])) === (string) $condition['value'];
+        case 'IS NOT NULL':
+          return TRUE;
+      }
+    }
+    return $condition['operator'] === 'IS NULL';
+  }
+
 }
diff -u b/core/lib/Drupal/Core/Config/Entity/Query/Query.php b/core/lib/Drupal/Core/Config/Entity/Query/Query.php
--- b/core/lib/Drupal/Core/Config/Entity/Query/Query.php
+++ b/core/lib/Drupal/Core/Config/Entity/Query/Query.php
@@ -27,7 +27,7 @@
   /**
    * The config storage used by the config entity query.
    *
-   * @var \Drupal\Core\Cache\CacheBackendInterface
+   * @var \Drupal\Core\Config\StorageInterface
    */
   protected $configStorage;
 
@@ -48,18 +48,38 @@
   }
 
   /**
+   * Overrides \Drupal\Core\Entity\Query\QueryBase::condition().
+   *
+   * Additional to the syntax defined in the QueryInterface you can use
+   * placeholders (*) to match all keys of an subarray. Let's take the follow
+   * yaml file as example:
+   * @code
+   *  level1:
+   *    level2a:
+   *      level3: 1
+   *    level2b:
+   *      level3: 2
+   * @endcode
+   * Then you can filter out via $query->condition('level1.*.level3', 1).
+   */
+  public function condition($property, $value = NULL, $operator = NULL, $langcode = NULL) {
+    return parent::condition($property, $value, $operator, $langcode);
+  }
+
+  /**
    * Implements \Drupal\Core\Entity\Query\QueryInterface::execute().
    */
   public function execute() {
     // Load all config files.
     $entity_info = $this->entityManager->getDefinition($this->getEntityType());
     $prefix = $entity_info['config_prefix'];
-
+    $prefix_length = strlen($prefix) + 1;
     $names = $this->configStorage->listAll($prefix);
     $configs = array();
     foreach ($names as $name) {
-      $configs[$name] = config($name)->get();
+      $configs[substr($name, $prefix_length)] = config($name)->get();
     }
+
     $result = $this->condition->compile($configs);
 
     // Apply sort settings.
@@ -80,13 +100,12 @@
       return count($result);
     }
 
-    $return = array();
-    $prefix_length = strlen($prefix) + 1;
-    foreach ($result as $config_name => $data) {
-      $id = substr($config_name, $prefix_length);
-      $return[$id] = $id;
+    // Create the expected structure of entity_id => entity_id. Config
+    // entities have string entity IDs.
+    foreach ($result as $key => &$value) {
+      $value = (string) $key;
     }
-    return $return;
+    return $result;
   }
 
 }
diff -u b/core/modules/system/lib/Drupal/system/Tests/Entity/ConfigEntityQueryTest.php b/core/modules/system/lib/Drupal/system/Tests/Entity/ConfigEntityQueryTest.php
--- b/core/modules/system/lib/Drupal/system/Tests/Entity/ConfigEntityQueryTest.php
+++ b/core/modules/system/lib/Drupal/system/Tests/Entity/ConfigEntityQueryTest.php
@@ -58,7 +58,12 @@
     $this->enableModules(array('entity'), TRUE);
     $this->factory = $this->container->get('entity.query');
 
-    $array['level1']['level2']['level3'] = 1;
+    // These two are here to make sure that matchArray needs to go over several
+    // non-matches on every levels.
+    $array['level1']['level2a'] = 9;
+    $array['level1a']['level2'] = 9;
+    // The tests match array.level1.level2.
+    $array['level1']['level2'] = 1;
     $entity = entity_create('config_query_test', array(
       'label' => $this->randomName(),
       'id' => '1',
@@ -69,7 +74,7 @@
     $entity->enforceIsNew();
     $entity->save();
 
-    $array['level1']['level2']['level3'] = 2;
+    $array['level1']['level2'] = 2;
     $entity = entity_create('config_query_test', array(
       'label' => $this->randomName(),
       'id' => '2',
@@ -80,7 +85,7 @@
     $entity->enforceIsNew();
     $entity->save();
 
-    $array['level1']['level2']['level3'] = 1;
+    $array['level1']['level2'] = 1;
     $entity = entity_create('config_query_test', array(
       'label' => 'test_prefix_' . $this->randomName(),
       'id' => '3',
@@ -91,7 +96,7 @@
     $entity->enforceIsNew();
     $entity->save();
 
-    $array['level1']['level2']['level3'] = 2;
+    $array['level1']['level2'] = 2;
     $entity = entity_create('config_query_test', array(
       'label' => $this->randomName() . '_test_suffix',
       'id' => '4',
@@ -102,7 +107,7 @@
     $entity->enforceIsNew();
     $entity->save();
 
-    $array['level1']['level2']['level3'] = 3;
+    $array['level1']['level2'] = 3;
     $entity = entity_create('config_query_test', array(
       'label' => $this->randomName() . '_test_contains_' . $this->randomName(),
       'id' => '5',
@@ -400,19 +405,23 @@
   }
 
   /**
-   * Test wildcard matching.
+   * Test dotted path matching.
    */
-  function testWildcards() {
+  function testDotted() {
     $this->queryResults = $this->factory->get('config_query_test')
-      ->condition('array.level1.*.level3', 1)
+      ->condition('array.level1.*', 1)
       ->execute();
     $this->assertResults(array('1', '3'));
     $this->queryResults = $this->factory->get('config_query_test')
-      ->condition('*.level1.level2.level3', 2)
+      ->condition('*.level1.level2', 2)
       ->execute();
     $this->assertResults(array('2', '4'));
     $this->queryResults = $this->factory->get('config_query_test')
-      ->condition('array.level1.level2.*', 3)
+      ->condition('array.level1.*', 3)
+      ->execute();
+    $this->assertResults(array('5'));
+    $this->queryResults = $this->factory->get('config_query_test')
+      ->condition('array.level1.level2', 3)
       ->execute();
     $this->assertResults(array('5'));
   }