NLU is re-trained when stories change
Whenever you change a story, the NLU model will also be re-trained. This is likely caused by [these lines](https://github.com/RasaHQ/rasa/blob/dcb9b5659ab7a2a87417a7b9af603a37ed30888f/rasa/shared/importers/importer.py#L488).

In addition we should de-duplicate the messages which are added to the NLU training data (sorting would also be great to avoid having diffs in the training data just because a new story was added)
diff --git a/rasa/shared/core/events.py b/rasa/shared/core/events.py
index a778d100e9b..3e0852f263c 100644
--- a/rasa/shared/core/events.py
+++ b/rasa/shared/core/events.py
@@ -278,13 +278,7 @@ class UserUttered(Event):
         )
 
     def __hash__(self) -> int:
-        return hash(
-            (
-                self.text,
-                self.intent.get(INTENT_NAME_KEY),
-                jsonpickle.encode(self.entities),
-            )
-        )
+        return hash((self.text, self.intent_name, jsonpickle.encode(self.entities)))
 
     @property
     def intent_name(self) -> Optional[Text]:
diff --git a/rasa/shared/importers/importer.py b/rasa/shared/importers/importer.py
index acaf5305a27..fca5764a978 100644
--- a/rasa/shared/importers/importer.py
+++ b/rasa/shared/importers/importer.py
@@ -1,6 +1,6 @@
 import asyncio
 from functools import reduce
-from typing import Text, Optional, List, Dict, Set, Any
+from typing import Text, Optional, List, Dict, Set, Any, Tuple
 import logging
 
 import rasa.shared.constants
@@ -8,7 +8,7 @@ import rasa.shared.utils.common
 import rasa.shared.core.constants
 import rasa.shared.utils.io
 from rasa.shared.core.domain import Domain
-from rasa.shared.core.events import ActionExecuted, UserUttered, Event
+from rasa.shared.core.events import ActionExecuted, UserUttered
 from rasa.shared.nlu.interpreter import NaturalLanguageInterpreter, RegexInterpreter
 from rasa.shared.core.training_data.structures import StoryGraph
 from rasa.shared.nlu.training_data.message import Message
@@ -488,12 +488,21 @@ class E2EImporter(TrainingDataImporter):
     async def _additional_training_data_from_stories(self) -> TrainingData:
         stories = await self.get_stories()
 
-        additional_messages_from_stories = []
-        for story_step in stories.story_steps:
-            for event in story_step.events:
-                message = _message_from_conversation_event(event)
-                if message:
-                    additional_messages_from_stories.append(message)
+        utterances, actions = _unique_events_from_stories(stories)
+
+        # Sort events to guarantee deterministic behavior and to avoid that the NLU
+        # model has to be retrained due to changes in the event order within
+        # the stories.
+        sorted_utterances = sorted(
+            utterances, key=lambda user: user.intent_name or user.text
+        )
+        sorted_actions = sorted(
+            actions, key=lambda action: action.action_name or action.action_text
+        )
+
+        additional_messages_from_stories = [
+            _messages_from_action(action) for action in sorted_actions
+        ] + [_messages_from_user_utterance(user) for user in sorted_utterances]
 
         logger.debug(
             f"Added {len(additional_messages_from_stories)} training data examples "
@@ -502,13 +511,20 @@ class E2EImporter(TrainingDataImporter):
         return TrainingData(additional_messages_from_stories)
 
 
-def _message_from_conversation_event(event: Event) -> Optional[Message]:
-    if isinstance(event, UserUttered):
-        return _messages_from_user_utterance(event)
-    elif isinstance(event, ActionExecuted):
-        return _messages_from_action(event)
+def _unique_events_from_stories(
+    stories: StoryGraph,
+) -> Tuple[Set[UserUttered], Set[ActionExecuted]]:
+    action_events = set()
+    user_events = set()
+
+    for story_step in stories.story_steps:
+        for event in story_step.events:
+            if isinstance(event, ActionExecuted):
+                action_events.add(event)
+            elif isinstance(event, UserUttered):
+                user_events.add(event)
 
-    return None
+    return user_events, action_events
 
 
 def _messages_from_user_utterance(event: UserUttered) -> Message:
diff --git a/tests/shared/importers/test_importer.py b/tests/shared/importers/test_importer.py
index 41192cd05c8..d1d61430aaf 100644
--- a/tests/shared/importers/test_importer.py
+++ b/tests/shared/importers/test_importer.py
@@ -1,7 +1,6 @@
-import asyncio
 import os
 from pathlib import Path
-from typing import Text, Dict, Type, List
+from typing import Text, Dict, Type, List, Any
 
 import pytest
 
@@ -28,6 +27,17 @@ from rasa.shared.nlu.constants import ACTION_TEXT, ACTION_NAME, INTENT_NAME, TEX
 from rasa.shared.nlu.training_data.message import Message
 
 
+@pytest.fixture()
+def default_importer(project: Text) -> TrainingDataImporter:
+    config_path = os.path.join(project, DEFAULT_CONFIG_PATH)
+    domain_path = os.path.join(project, DEFAULT_DOMAIN_PATH)
+    default_data_path = os.path.join(project, DEFAULT_DATA_PATH)
+
+    return TrainingDataImporter.load_from_dict(
+        {}, config_path, domain_path, [default_data_path]
+    )
+
+
 async def test_use_of_interface():
     importer = TrainingDataImporter()
 
@@ -168,17 +178,12 @@ async def test_core_only(project: Text):
     assert nlu_data.is_empty()
 
 
-async def test_import_nlu_training_data_from_e2e_stories(project: Text):
-    config_path = os.path.join(project, DEFAULT_CONFIG_PATH)
-    domain_path = os.path.join(project, DEFAULT_DOMAIN_PATH)
-    default_data_path = os.path.join(project, DEFAULT_DATA_PATH)
-    importer = TrainingDataImporter.load_from_dict(
-        {}, config_path, domain_path, [default_data_path]
-    )
-
+async def test_import_nlu_training_data_from_e2e_stories(
+    default_importer: TrainingDataImporter,
+):
     # The `E2EImporter` correctly wraps the underlying `CombinedDataImporter`
-    assert isinstance(importer, E2EImporter)
-    importer_without_e2e = importer.importer
+    assert isinstance(default_importer, E2EImporter)
+    importer_without_e2e = default_importer.importer
 
     stories = StoryGraph(
         [
@@ -198,17 +203,22 @@ async def test_import_nlu_training_data_from_e2e_stories(project: Text):
         ]
     )
 
+    async def mocked_stories(*_: Any, **__: Any) -> StoryGraph:
+        return stories
+
     # Patch to return our test stories
-    importer_without_e2e.get_stories = asyncio.coroutine(lambda *args: stories)
+    importer_without_e2e.get_stories = mocked_stories
 
     # The wrapping `E2EImporter` simply forwards these method calls
     assert (await importer_without_e2e.get_stories()).as_story_string() == (
-        await importer.get_stories()
+        await default_importer.get_stories()
     ).as_story_string()
-    assert (await importer_without_e2e.get_config()) == (await importer.get_config())
+    assert (await importer_without_e2e.get_config()) == (
+        await default_importer.get_config()
+    )
 
     # Check additional NLU training data from stories was added
-    nlu_data = await importer.get_nlu_data()
+    nlu_data = await default_importer.get_nlu_data()
 
     # The `E2EImporter` adds NLU training data based on our training stories
     assert len(nlu_data.training_examples) > len(
@@ -228,25 +238,61 @@ async def test_import_nlu_training_data_from_e2e_stories(project: Text):
     assert all(m in nlu_data.training_examples for m in expected_additional_messages)
 
 
-async def test_import_nlu_training_data_with_default_actions(project: Text):
-    config_path = os.path.join(project, DEFAULT_CONFIG_PATH)
-    domain_path = os.path.join(project, DEFAULT_DOMAIN_PATH)
-    default_data_path = os.path.join(project, DEFAULT_DATA_PATH)
-    importer = TrainingDataImporter.load_from_dict(
-        {}, config_path, domain_path, [default_data_path]
-    )
+async def test_different_story_order_doesnt_change_nlu_training_data(
+    default_importer: E2EImporter,
+):
+    stories = [
+        StoryStep(
+            events=[
+                UserUttered(intent={"name": "greet"}),
+                ActionExecuted("utter_greet_from_stories"),
+                ActionExecuted("hi", action_text="hi"),
+            ]
+        ),
+        StoryStep(
+            events=[
+                UserUttered("bye", {"name": "bye"}),
+                ActionExecuted("utter_greet"),
+                ActionExecuted("hi", action_text="hi"),
+                ActionExecuted("bye", action_text="bye"),
+            ]
+        ),
+    ]
 
-    assert isinstance(importer, E2EImporter)
-    importer_without_e2e = importer.importer
+    async def mocked_stories(*_: Any, **__: Any) -> StoryGraph:
+        return StoryGraph(stories)
+
+    # Patch to return our test stories
+    default_importer.importer.get_stories = mocked_stories
+
+    training_data = await default_importer.get_nlu_data()
+
+    # Pretend the order of  the stories changed. This should have no
+    # effect on the NLU training data
+    stories = list(reversed(stories))
+
+    # Make sure importer doesn't cache stories
+    default_importer._cached_stories = None
+
+    training_data2 = await default_importer.get_nlu_data()
+
+    assert hash(training_data) == hash(training_data2)
+
+
+async def test_import_nlu_training_data_with_default_actions(
+    default_importer: TrainingDataImporter,
+):
+    assert isinstance(default_importer, E2EImporter)
+    importer_without_e2e = default_importer.importer
 
     # Check additional NLU training data from domain was added
-    nlu_data = await importer.get_nlu_data()
+    nlu_data = await default_importer.get_nlu_data()
 
     assert len(nlu_data.training_examples) > len(
         (await importer_without_e2e.get_nlu_data()).training_examples
     )
 
-    extended_training_data = await importer.get_nlu_data()
+    extended_training_data = await default_importer.get_nlu_data()
     assert all(
         Message(data={ACTION_NAME: action_name, ACTION_TEXT: ""})
         in extended_training_data.training_examples
@@ -254,14 +300,7 @@ async def test_import_nlu_training_data_with_default_actions(project: Text):
     )
 
 
-async def test_adding_e2e_actions_to_domain(project: Text):
-    config_path = os.path.join(project, DEFAULT_CONFIG_PATH)
-    domain_path = os.path.join(project, DEFAULT_DOMAIN_PATH)
-    default_data_path = os.path.join(project, DEFAULT_DATA_PATH)
-    existing = TrainingDataImporter.load_from_dict(
-        {}, config_path, domain_path, [default_data_path]
-    )
-
+async def test_adding_e2e_actions_to_domain(default_importer: E2EImporter):
     additional_actions = ["Hi Joey.", "it's sunny outside."]
     stories = StoryGraph(
         [
@@ -288,11 +327,13 @@ async def test_adding_e2e_actions_to_domain(project: Text):
         ]
     )
 
+    async def mocked_stories(*_: Any, **__: Any) -> StoryGraph:
+        return stories
+
     # Patch to return our test stories
-    existing.get_stories = asyncio.coroutine(lambda *args: stories)
+    default_importer.importer.get_stories = mocked_stories
 
-    importer = E2EImporter(existing)
-    domain = await importer.get_domain()
+    domain = await default_importer.get_domain()
 
     assert all(action_name in domain.action_names for action_name in additional_actions)
 
['rasa/shared/core/events.py', 'tests/shared/importers/test_importer.py', 'rasa/shared/importers/importer.py']