diff --git a/bindings/python/rhythmdb.override b/bindings/python/rhythmdb.override
index 0464527..7500aca 100644
--- a/bindings/python/rhythmdb.override
+++ b/bindings/python/rhythmdb.override
@@ -467,11 +467,13 @@ _wrap_rhythmdb_query_model_new (PyGObject *self, PyObject *args, PyObject *kwarg
 
 	if (data->func) {
 		query_model = rhythmdb_query_model_new (RHYTHMDB (self->obj), pyg_boxed_get (py_query, RhythmDBQuery),
+							RHYTHMDB_QUERY_MODEL_ORDER_SORTED,
 							(GCompareDataFunc) _rhythmdb_query_model_sort_func,
 							data, (GDestroyNotify) _rhythmdb_query_model_sort_data_free,
 							(reverse != 0));
 	} else {
 		query_model = rhythmdb_query_model_new (RHYTHMDB (self->obj), pyg_boxed_get (py_query, RhythmDBQuery),
+							RHYTHMDB_QUERY_MODEL_ORDER_MANUAL,
 							NULL, NULL, NULL, FALSE);
 	}
 
diff --git a/plugins/generic-player/rb-psp-source.c b/plugins/generic-player/rb-psp-source.c
index d61eaf3..0022216 100644
--- a/plugins/generic-player/rb-psp-source.c
+++ b/plugins/generic-player/rb-psp-source.c
@@ -184,6 +184,7 @@ visit_playlist_dirs (const gchar *rel_path,
 	playlist = rb_auto_playlist_source_new (shell, rel_path, FALSE);
 	rb_auto_playlist_source_set_query (RB_AUTO_PLAYLIST_SOURCE (playlist), query,
 					   RHYTHMDB_QUERY_MODEL_LIMIT_NONE, NULL,
+					   RHYTHMDB_QUERY_MODEL_ORDER_MANUAL,
 					   NULL, 0);
 	rb_generic_player_source_add_playlist (RB_GENERIC_PLAYER_SOURCE (source), shell, RB_SOURCE (playlist));
 	rhythmdb_query_free (query);
diff --git a/rhythmdb/rhythmdb-query-model.c b/rhythmdb/rhythmdb-query-model.c
index 0808942..42960ec 100644
--- a/rhythmdb/rhythmdb-query-model.c
+++ b/rhythmdb/rhythmdb-query-model.c
@@ -89,8 +89,8 @@ static void rhythmdb_query_model_entry_changed_cb (RhythmDB *db, RhythmDBEntry *
 static void rhythmdb_query_model_entry_deleted_cb (RhythmDB *db, RhythmDBEntry *entry,
 						   RhythmDBQueryModel *model);
 
-static void rhythmdb_query_model_filter_out_entry (RhythmDBQueryModel *model,
-						   RhythmDBEntry *entry);
+static gboolean rhythmdb_query_model_filter_out_entry (RhythmDBQueryModel *model,
+						       RhythmDBEntry *entry);
 static gboolean rhythmdb_query_model_do_reorder (RhythmDBQueryModel *model, RhythmDBEntry *entry);
 static gboolean rhythmdb_query_model_emit_reorder (RhythmDBQueryModel *model, gint old_pos, gint new_pos);
 static gboolean rhythmdb_query_model_drag_data_get (RbTreeDragSource *dragsource,
@@ -216,6 +216,7 @@ struct RhythmDBQueryModelPrivate
 
 	RhythmDBQueryModel *base_model;
 
+	RhythmDBQueryModelOrderType order_type;
 	GCompareDataFunc sort_func;
 	gpointer sort_data;
 	GDestroyNotify sort_data_destroy;
@@ -261,6 +262,7 @@ enum
 	PROP_LIMIT_VALUE,
 	PROP_SHOW_HIDDEN,
 	PROP_BASE_MODEL,
+	PROP_ORDER_TYPE,
 };
 
 enum
@@ -359,6 +361,14 @@ rhythmdb_query_model_class_init (RhythmDBQueryModelClass *klass)
 							      "base RhythmDBQueryModel",
 							      RHYTHMDB_TYPE_QUERY_MODEL,
 							      G_PARAM_READWRITE | G_PARAM_CONSTRUCT));
+	g_object_class_install_property (object_class,
+					 PROP_ORDER_TYPE,
+					 g_param_spec_enum ("order-type",
+						 	    "order-type",
+							    "ordering type",
+							    RHYTHMDB_TYPE_QUERY_MODEL_ORDER_TYPE,
+							    RHYTHMDB_QUERY_MODEL_ORDER_MANUAL,
+							    G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
 
 	rhythmdb_query_model_signals[ENTRY_PROP_CHANGED] =
 		g_signal_new ("entry-prop-changed",
@@ -522,6 +532,9 @@ rhythmdb_query_model_set_property (GObject *object,
 	case PROP_BASE_MODEL:
 		rhythmdb_query_model_chain (model, g_value_get_object (value), TRUE);
 		break;
+	case PROP_ORDER_TYPE:
+		model->priv->order_type = g_value_get_enum (value);
+		break;
 	default:
 		G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 		break;
@@ -567,6 +580,9 @@ rhythmdb_query_model_get_property (GObject *object,
 	case PROP_BASE_MODEL:
 		g_value_set_object (value, model->priv->base_model);
 		break;
+	case PROP_ORDER_TYPE:
+		g_value_set_enum (value, model->priv->order_type);
+		break;
 	default:
 		G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 		break;
@@ -713,6 +729,7 @@ rhythmdb_query_model_finalize (GObject *object)
 RhythmDBQueryModel *
 rhythmdb_query_model_new (RhythmDB *db,
 			  GPtrArray *query,
+			  RhythmDBQueryModelOrderType order_type,
 			  GCompareDataFunc sort_func,
 			  gpointer sort_data,
 			  GDestroyNotify sort_data_destroy,
@@ -720,6 +737,7 @@ rhythmdb_query_model_new (RhythmDB *db,
 {
 	RhythmDBQueryModel *model = g_object_new (RHYTHMDB_TYPE_QUERY_MODEL,
 						  "db", db, "query", query,
+						  "order-type", order_type,
 						  "sort-func", sort_func,
 						  "sort-data", sort_data,
 						  "sort-data-destroy", sort_data_destroy,
@@ -1139,34 +1157,45 @@ rhythmdb_query_model_insert_into_main_list (RhythmDBQueryModel *model,
 	/* take reference; released when removed from hash */
 	rhythmdb_entry_ref (entry);
 
-	if (model->priv->sort_func) {
-		GCompareDataFunc sort_func;
-		gpointer sort_data;
-		struct ReverseSortData reverse_data;
+	switch (model->priv->order_type) {
+	case RHYTHMDB_QUERY_MODEL_ORDER_SORTED:
+		{
+			GCompareDataFunc sort_func;
+			gpointer sort_data;
+			struct ReverseSortData reverse_data;
+
+			if (model->priv->sort_reverse) {
+				sort_func = (GCompareDataFunc) _reverse_sorting_func;
+				sort_data = &reverse_data;
+				reverse_data.func = model->priv->sort_func;
+				reverse_data.data = model->priv->sort_data;
+			} else {
+				sort_func = model->priv->sort_func;
+				sort_data = model->priv->sort_data;
+			}
 
-		if (model->priv->sort_reverse) {
-			sort_func = (GCompareDataFunc) _reverse_sorting_func;
-			sort_data = &reverse_data;
-			reverse_data.func = model->priv->sort_func;
-			reverse_data.data = model->priv->sort_data;
-		} else {
-			sort_func = model->priv->sort_func;
-			sort_data = model->priv->sort_data;
+			ptr = g_sequence_insert_sorted (model->priv->entries,
+							entry,
+							sort_func,
+							sort_data);
 		}
+		break;
 
-		ptr = g_sequence_insert_sorted (model->priv->entries,
-						entry,
-						sort_func,
-						sort_data);
-	} else {
-		if (index == -1) {
-			ptr = g_sequence_get_end_iter (model->priv->entries);
-		} else {
-			ptr = g_sequence_get_iter_at_pos (model->priv->entries, index);
-		}
+	case RHYTHMDB_QUERY_MODEL_ORDER_MANUAL:
+	case RHYTHMDB_QUERY_MODEL_ORDER_RANDOM:
+		{
+			if (index == -1) {
+				ptr = g_sequence_get_end_iter (model->priv->entries);
+			} else {
+				ptr = g_sequence_get_iter_at_pos (model->priv->entries, index);
+			}
 
-		g_sequence_insert_before (ptr, entry);
-		ptr = g_sequence_iter_prev (ptr);
+			g_sequence_insert_before (ptr, entry);
+			ptr = g_sequence_iter_prev (ptr);
+		}
+		break;
+	default:
+		g_assert_not_reached ();
 	}
 
 	/* the hash now owns this reference to the entry */
@@ -1178,35 +1207,61 @@ rhythmdb_query_model_insert_into_main_list (RhythmDBQueryModel *model,
 
 static void
 rhythmdb_query_model_insert_into_limited_list (RhythmDBQueryModel *model,
-					       RhythmDBEntry *entry)
+					       RhythmDBEntry *entry,
+					       int index)
 {
 	GSequenceIter *ptr;
 
 	/* take reference; released when removed from hash */
 	rhythmdb_entry_ref (entry);
 
-	if (model->priv->sort_func) {
-		GCompareDataFunc sort_func;
-		gpointer sort_data;
-		struct ReverseSortData reverse_data;
+	switch (model->priv->order_type) {
+	case RHYTHMDB_QUERY_MODEL_ORDER_RANDOM:
+		{
+			if (index == -1) {
+				/* insert at random */
+				int count = g_hash_table_size (model->priv->limited_reverse_map);
+				if (count > 1) {
+					index = g_random_int_range (0, count + 1);
+				}
+			}
 
-		if (model->priv->sort_reverse) {
-			sort_func = (GCompareDataFunc) _reverse_sorting_func;
-			sort_data = &reverse_data;
-			reverse_data.func = model->priv->sort_func;
-			reverse_data.data = model->priv->sort_data;
-		} else {
-			sort_func = model->priv->sort_func;
-			sort_data = model->priv->sort_data;
+			ptr = g_sequence_get_iter_at_pos (model->priv->limited_entries, index);
+			g_sequence_insert_before (ptr, entry);
+			ptr = g_sequence_iter_prev (ptr);
+		}
+		break;
+	case RHYTHMDB_QUERY_MODEL_ORDER_SORTED:
+		{
+			GCompareDataFunc sort_func;
+			gpointer sort_data;
+			struct ReverseSortData reverse_data;
+
+			if (model->priv->sort_reverse) {
+				sort_func = (GCompareDataFunc) _reverse_sorting_func;
+				sort_data = &reverse_data;
+				reverse_data.func = model->priv->sort_func;
+				reverse_data.data = model->priv->sort_data;
+			} else {
+				sort_func = model->priv->sort_func;
+				sort_data = model->priv->sort_data;
+			}
+
+			ptr = g_sequence_insert_sorted (model->priv->limited_entries, entry,
+							sort_func,
+							sort_data);
 		}
+		break;
 
-		ptr = g_sequence_insert_sorted (model->priv->limited_entries, entry,
-						sort_func,
-						sort_data);
-	} else {
-		ptr = g_sequence_get_end_iter (model->priv->limited_entries);
-		g_sequence_insert_before (ptr, entry);
-		ptr = g_sequence_iter_prev (ptr);
+	case RHYTHMDB_QUERY_MODEL_ORDER_MANUAL:
+		{
+			ptr = g_sequence_get_end_iter (model->priv->limited_entries);
+			g_sequence_insert_before (ptr, entry);
+			ptr = g_sequence_iter_prev (ptr);
+		}
+		break;
+	default:
+		g_assert_not_reached ();
 	}
 
 	/* the hash now owns this reference to the entry */
@@ -1277,7 +1332,7 @@ rhythmdb_query_model_update_limited_entries (RhythmDBQueryModel *model)
 		/* take temporary ref */
 		rhythmdb_entry_ref (entry);
 		rhythmdb_query_model_remove_from_main_list (model, entry);
-		rhythmdb_query_model_insert_into_limited_list (model, entry);
+		rhythmdb_query_model_insert_into_limited_list (model, entry, -1);
 		/* release temporary ref */
 		rhythmdb_entry_unref (entry);
 	}
@@ -1376,6 +1431,8 @@ rhythmdb_query_model_do_reorder (RhythmDBQueryModel *model,
 	gpointer sort_data;
 	struct ReverseSortData reverse_data;
 
+	if (model->priv->order_type != RHYTHMDB_QUERY_MODEL_ORDER_SORTED)
+		return FALSE;
 	if (model->priv->sort_func == NULL)
 		return FALSE;
 
@@ -1443,6 +1500,7 @@ rhythmdb_query_model_do_insert (RhythmDBQueryModel *model,
 	GSequenceIter *ptr;
 	GtkTreePath *path;
 	GtkTreeIter iter;
+	gboolean emit_inserted;
 
 	g_assert (model->priv->show_hidden || !rhythmdb_entry_get_boolean (entry, RHYTHMDB_PROP_HIDDEN));
 
@@ -1455,28 +1513,56 @@ rhythmdb_query_model_do_insert (RhythmDBQueryModel *model,
 
 	ptr = g_hash_table_lookup (model->priv->limited_reverse_map, entry);
 	if (ptr != NULL) {
-		rhythmdb_query_model_remove_from_limited_list (model, entry);
+		switch (model->priv->order_type) {
+
+		case RHYTHMDB_QUERY_MODEL_ORDER_SORTED:
+			rhythmdb_query_model_remove_from_limited_list (model, entry);
+			break;
+
+		case RHYTHMDB_QUERY_MODEL_ORDER_MANUAL:
+			/* hm, this probably shouldn't happen. */
+		case RHYTHMDB_QUERY_MODEL_ORDER_RANDOM:
+			rhythmdb_entry_unref (entry);
+			return;
+		}
 	}
 
-	rhythmdb_query_model_insert_into_main_list (model, entry, index);
+	switch (model->priv->order_type) {
+	case RHYTHMDB_QUERY_MODEL_ORDER_RANDOM:
+		/* just insert it anywhere */
+		emit_inserted = rhythmdb_query_model_percolate_entry (model, entry);
+		break;
+
+	case RHYTHMDB_QUERY_MODEL_ORDER_SORTED:
+	case RHYTHMDB_QUERY_MODEL_ORDER_MANUAL:
+		{
+			rhythmdb_query_model_insert_into_main_list (model, entry, index);
+			emit_inserted = TRUE;
+		}
+		break;
+	default:
+		g_assert_not_reached ();
+	}
 
 	/* release temporary ref */
 	rhythmdb_entry_unref (entry);
 
-	/* it was added to the main list, send out the inserted signal */
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
-	iter.stamp = model->priv->stamp;
-	iter.user_data = ptr;
-	path = rhythmdb_query_model_get_path (GTK_TREE_MODEL (model),
-					      &iter);
-	gtk_tree_model_row_inserted (GTK_TREE_MODEL (model),
-				     path, &iter);
-	gtk_tree_path_free (path);
+	if (emit_inserted) {
+		/* it was added to the main list, send out the inserted signal */
+		ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+		iter.stamp = model->priv->stamp;
+		iter.user_data = ptr;
+		path = rhythmdb_query_model_get_path (GTK_TREE_MODEL (model),
+						      &iter);
+		gtk_tree_model_row_inserted (GTK_TREE_MODEL (model),
+					     path, &iter);
+		gtk_tree_path_free (path);
+	}
 
 	rhythmdb_query_model_update_limited_entries (model);
 }
 
-static void
+static gboolean
 rhythmdb_query_model_filter_out_entry (RhythmDBQueryModel *model,
 				       RhythmDBEntry *entry)
 {
@@ -1486,15 +1572,17 @@ rhythmdb_query_model_filter_out_entry (RhythmDBQueryModel *model,
 	if (ptr != NULL) {
 		rhythmdb_query_model_remove_from_main_list (model, entry);
 		rhythmdb_query_model_update_limited_entries (model);
-		return;
+		return TRUE;
 	}
 
 	ptr = g_hash_table_lookup (model->priv->limited_reverse_map, entry);
 	if (ptr != NULL) {
 		rhythmdb_query_model_remove_from_limited_list (model, entry);
 		rhythmdb_query_model_update_limited_entries (model);
-		return;
+		return TRUE;
 	}
+
+	return FALSE;
 }
 
 void
@@ -1510,6 +1598,9 @@ rhythmdb_query_model_shuffle_entries (RhythmDBQueryModel *model)
 	GtkTreeIter tree_iter;
 	int *map_new_old;
 
+	if (model->priv->order_type == RHYTHMDB_QUERY_MODEL_ORDER_SORTED)
+		return;
+
 	/* Convert the entries list to an array, for fast lookups. */
 	listsize = g_sequence_get_length (model->priv->entries);
 	entries = (RhythmDBEntry **)g_malloc (sizeof(RhythmDBEntry *) * listsize);
@@ -1712,7 +1803,8 @@ rhythmdb_query_model_drag_data_delete (RbTreeDragSource *dragsource,
 
 	/* we don't delete if it is a reorder drag and drop because the deletion already
 	   occured in rhythmdb_query_model_drag_data_received */
-	if (model->priv->sort_func == NULL && !model->priv->reorder_drag_and_drop) {
+	if ((model->priv->order_type != RHYTHMDB_QUERY_MODEL_ORDER_SORTED) &&
+	    !model->priv->reorder_drag_and_drop) {
 
 		RhythmDBEntry *entry;
 		GtkTreeIter iter;
@@ -1835,7 +1927,7 @@ rhythmdb_query_model_drag_data_received (RbTreeDragDest *drag_dest,
 
 	rb_debug ("drag received");
 
-	if (model->priv->sort_func != NULL)
+	if (model->priv->order_type == RHYTHMDB_QUERY_MODEL_ORDER_SORTED)
 		return FALSE;
 
 	if (selection_data->format == 8 && selection_data->length >= 0) {
@@ -1946,7 +2038,7 @@ rhythmdb_query_model_row_drop_possible (RbTreeDragDest *drag_dest,
 	RhythmDBQueryModel *model = RHYTHMDB_QUERY_MODEL (drag_dest);
 
 	while (model) {
-		if (model->priv->sort_func != NULL)
+		if (model->priv->order_type == RHYTHMDB_QUERY_MODEL_ORDER_SORTED)
 			return FALSE;
 
 		model = model->priv->base_model;
@@ -2270,6 +2362,9 @@ rhythmdb_query_model_set_sort_order (RhythmDBQueryModel *model,
 	if (model->priv->sort_data_destroy && model->priv->sort_data)
 		model->priv->sort_data_destroy (model->priv->sort_data);
 
+	/* not entirely sure about this.. */
+	model->priv->order_type = RHYTHMDB_QUERY_MODEL_ORDER_SORTED;
+
 	model->priv->sort_func = sort_func;
 	model->priv->sort_data = sort_data;
 	model->priv->sort_data_destroy = sort_data_destroy;
@@ -2452,7 +2547,7 @@ rhythmdb_query_model_base_rows_reordered (GtkTreeModel *base_model,
 	_BaseRowsReorderedData data;
 
 	/* ignore, if this model sorts */
-	if (model->priv->sort_func)
+	if (model->priv->order_type == RHYTHMDB_QUERY_MODEL_ORDER_SORTED)
 		return;
 
 	data.new_entries = g_sequence_new (NULL);
@@ -2535,6 +2630,75 @@ rhythmdb_query_model_reapply_query (RhythmDBQueryModel *model,
 		rhythmdb_query_model_update_limited_entries (model);
 }
 
+static gboolean
+rhythmdb_query_model_reapply_query_cb (RhythmDBQueryModel *model)
+{
+	GDK_THREADS_ENTER ();
+	rhythmdb_query_model_reapply_query (model, FALSE);
+	rhythmdb_do_full_query_async_parsed (model->priv->db,
+					     RHYTHMDB_QUERY_RESULTS (model),
+					     model->priv->original_query);
+	GDK_THREADS_LEAVE ();
+	return TRUE;
+}
+
+/**
+ * rhythmdb_query_model_percolate_entry:
+ * @model: a #RhythmDBQueryModel
+ * @entry: a #RhythmDBEntry
+ *
+ * If the query model is randomly ordered, this moves the entry
+ * to a new random position.
+ *
+ * The idea here is that this should be called when an entry has been
+ * played (or any such action) to keep the random selection fresh.
+ *
+ * Return value: %TRUE if the entry was added to the main list, %FALSE otherwise
+ */
+gboolean
+rhythmdb_query_model_percolate_entry (RhythmDBQueryModel *model, RhythmDBEntry *entry)
+{
+	int main_size;
+	int total_size;
+	int index;
+	gboolean result;
+
+	if (model->priv->order_type != RHYTHMDB_QUERY_MODEL_ORDER_RANDOM)
+		return FALSE;
+
+	index = 0;
+	main_size = g_hash_table_size (model->priv->reverse_map);
+	total_size = main_size + g_hash_table_size (model->priv->limited_reverse_map);
+	if (total_size > 0) {
+		index = g_random_int_range (0, total_size + 1);
+	}
+
+	/* temporary ref */
+	rhythmdb_entry_ref (entry);
+
+	/* remove from wherever it currently lives.  hm, may not be smart enough.. */
+	if (rhythmdb_query_model_filter_out_entry (model, entry) == FALSE) {
+		/* it wasn't already in the model, so we need to check if it matches
+		 * the query before we add it.
+		 */
+		if (rhythmdb_evaluate_query (model->priv->db, model->priv->query, entry) == FALSE) {
+			rhythmdb_entry_unref (entry);
+			return FALSE;
+		}
+	}
+
+	/* and add to the new location */
+	if (index < main_size) {
+		rhythmdb_query_model_insert_into_main_list (model, entry, index);
+		result = TRUE;
+	} else {
+		rhythmdb_query_model_insert_into_limited_list (model, entry, index - main_size);
+		result = FALSE;
+	}
+	rhythmdb_entry_unref (entry);
+	return result;
+}
+
 static gint
 _reverse_sorting_func (gpointer a,
 		       gpointer b,
@@ -2889,14 +3053,24 @@ rhythmdb_query_model_limit_type_get_type (void)
 	return etype;
 }
 
-static gboolean
-rhythmdb_query_model_reapply_query_cb (RhythmDBQueryModel *model)
+GType
+rhythmdb_query_model_order_type_get_type (void)
 {
-	GDK_THREADS_ENTER ();
-	rhythmdb_query_model_reapply_query (model, FALSE);
-	rhythmdb_do_full_query_async_parsed (model->priv->db,
-					     RHYTHMDB_QUERY_RESULTS (model),
-					     model->priv->original_query);
-	GDK_THREADS_LEAVE ();
-	return TRUE;
+	static GType etype = 0;
+
+	if (etype == 0)
+	{
+		static const GEnumValue values[] =
+		{
+
+			ENUM_ENTRY (RHYTHMDB_QUERY_MODEL_ORDER_MANUAL, "Manual ordering"),
+			ENUM_ENTRY (RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Sorted order"),
+			ENUM_ENTRY (RHYTHMDB_QUERY_MODEL_ORDER_RANDOM, "Random order"),
+			{ 0, 0, 0 }
+		};
+
+		etype = g_enum_register_static ("RhythmDBQueryModelOrderType", values);
+	}
+
+	return etype;
 }
diff --git a/rhythmdb/rhythmdb-query-model.h b/rhythmdb/rhythmdb-query-model.h
index c0cf06e..d9f4d88 100644
--- a/rhythmdb/rhythmdb-query-model.h
+++ b/rhythmdb/rhythmdb-query-model.h
@@ -50,6 +50,9 @@ G_BEGIN_DECLS
 GType rhythmdb_query_model_limit_type_get_type (void);
 #define RHYTHMDB_TYPE_QUERY_MODEL_LIMIT_TYPE (rhythmdb_query_model_limit_type_get_type ())
 
+GType rhythmdb_query_model_order_type_get_type (void);
+#define RHYTHMDB_TYPE_QUERY_MODEL_ORDER_TYPE (rhythmdb_query_model_order_type_get_type ())
+
 typedef enum {
 	RHYTHMDB_QUERY_MODEL_LIMIT_NONE,
 	RHYTHMDB_QUERY_MODEL_LIMIT_COUNT,
@@ -57,6 +60,12 @@ typedef enum {
 	RHYTHMDB_QUERY_MODEL_LIMIT_TIME,
 } RhythmDBQueryModelLimitType;
 
+typedef enum {
+	RHYTHMDB_QUERY_MODEL_ORDER_MANUAL,
+	RHYTHMDB_QUERY_MODEL_ORDER_SORTED,
+	RHYTHMDB_QUERY_MODEL_ORDER_RANDOM
+} RhythmDBQueryModelOrderType;
+
 typedef struct RhythmDBQueryModelPrivate RhythmDBQueryModelPrivate;
 
 #define RHYTHMDB_QUERY_MODEL_SUGGESTED_UPDATE_CHUNK 1024
@@ -93,6 +102,7 @@ GType			rhythmdb_query_model_get_type		(void);
 
 RhythmDBQueryModel *	rhythmdb_query_model_new		(RhythmDB *db,
 								 GPtrArray *query,
+								 RhythmDBQueryModelOrderType order_type,
 								 GCompareDataFunc sort_func,
 								 gpointer sort_data,
 								 GDestroyNotify sort_data_destroy,
@@ -120,6 +130,9 @@ void			rhythmdb_query_model_move_entry 	(RhythmDBQueryModel *model,
 								 RhythmDBEntry *entry,
 								 gint index);
 
+gboolean		rhythmdb_query_model_percolate_entry	(RhythmDBQueryModel *model,
+								 RhythmDBEntry *entry);
+
 guint64 	        rhythmdb_query_model_get_size		(RhythmDBQueryModel *model);
 
 long			rhythmdb_query_model_get_duration 	(RhythmDBQueryModel *model);
@@ -190,6 +203,7 @@ gint 			rhythmdb_query_model_ulong_sort_func	(RhythmDBEntry *a,
 gint 			rhythmdb_query_model_date_sort_func	(RhythmDBEntry *a,
 								 RhythmDBEntry *b,
 								 gpointer data);
+
 G_END_DECLS
 
 #endif /* __RHYTHMDB_QUERY_MODEL_H */
diff --git a/shell/rb-playlist-manager.c b/shell/rb-playlist-manager.c
index 6471071..a83bd5e 100644
--- a/shell/rb-playlist-manager.c
+++ b/shell/rb-playlist-manager.c
@@ -1079,12 +1079,14 @@ rb_playlist_manager_set_automatic_playlist (RBPlaylistManager *mgr,
 {
 	RhythmDBQueryModelLimitType limit_type;
 	GValueArray *limit_value = NULL;
+	RhythmDBQueryModelOrderType order_type;
 	const char *sort_key;
 	gint sort_direction;
 	GPtrArray *query;
 
 	rb_query_creator_get_limit (creator, &limit_type, &limit_value);
 	rb_query_creator_get_sort_order (creator,
+					 &order_type,
 					 &sort_key,
 					 &sort_direction);
 
@@ -1093,6 +1095,7 @@ rb_playlist_manager_set_automatic_playlist (RBPlaylistManager *mgr,
 					   query,
 					   limit_type,
 					   limit_value,
+					   order_type,
 					   sort_key,
 					   sort_direction);
 	rhythmdb_query_free (query);
@@ -1172,6 +1175,7 @@ rb_playlist_manager_cmd_edit_automatic_playlist (GtkAction *action,
 		GPtrArray *query;
 		char *sort_key;
 		gint sort_direction;
+		RhythmDBQueryModelOrderType order_type;
 		EditAutoPlaylistData *data;
 
 		sort_key = NULL;
@@ -1179,6 +1183,7 @@ rb_playlist_manager_cmd_edit_automatic_playlist (GtkAction *action,
 						   &query,
 						   &limit_type,
 						   &limit_value,
+						   &order_type,
 						   &sort_key,
 						   &sort_direction);
 
@@ -1186,6 +1191,7 @@ rb_playlist_manager_cmd_edit_automatic_playlist (GtkAction *action,
 									     query,
 									     limit_type,
 									     limit_value,
+									     order_type,
 									     sort_key,
 									     sort_direction));
 		if (limit_value != NULL) {
diff --git a/shell/rb-shell-player.c b/shell/rb-shell-player.c
index 80e3f50..34e7cc8 100644
--- a/shell/rb-shell-player.c
+++ b/shell/rb-shell-player.c
@@ -3047,31 +3047,53 @@ rb_shell_player_error (RBShellPlayer *player,
 	}
 }
 
+typedef struct {
+	RBShellPlayer *player;
+	RhythmDBEntry *new_entry;
+	RhythmDBEntry *old_entry;
+} NewPlayingStreamData;
+
 static gboolean
-new_playing_stream_idle_cb (RBShellPlayer *player)
+new_playing_stream_idle_cb (NewPlayingStreamData *data)
 {
-	RhythmDBEntry *entry;
-	const char *location;
+	const char *location = NULL;
 
 	GDK_THREADS_ENTER ();
 
-	player->priv->emit_playing_id = 0;
+	data->player->priv->emit_playing_id = 0;
 
 	/* emit some interesting signals */
-	entry = rb_shell_player_get_playing_entry (player);
-	location = rhythmdb_entry_get_string (entry, RHYTHMDB_PROP_LOCATION);
-	rb_debug ("new playing stream: %s", location);
-	g_signal_emit (G_OBJECT (player),
+	if (data->new_entry != NULL) {
+		location = rhythmdb_entry_get_string (data->new_entry, RHYTHMDB_PROP_LOCATION);
+		rb_debug ("new playing stream: %s", location);
+	}
+	g_signal_emit (G_OBJECT (data->player),
 		       rb_shell_player_signals[PLAYING_SONG_CHANGED], 0,
-		       entry);
-	g_signal_emit (G_OBJECT (player),
+		       data->new_entry);
+	g_signal_emit (G_OBJECT (data->player),
 		       rb_shell_player_signals[PLAYING_URI_CHANGED], 0,
 		       location);
 
+	/* if the old entry was from a random selection, percolate it */
+	if (data->old_entry != NULL) {
+		/* we actually want to ignore the queue for this, so we use player->priv->source */
+		if (data->player->priv->source != NULL) {
+			RhythmDBQueryModel *model;
+			g_object_get (data->player->priv->source, "base-query-model", &model, NULL);
+			if (model != NULL) {
+				rhythmdb_query_model_percolate_entry (model, data->old_entry);
+				g_object_unref (model);
+			}
+		}
+	}
+
 	/* resync UI */
-	rb_shell_player_sync_with_source (player);
-	rb_shell_player_sync_buttons (player);
-	g_object_notify (G_OBJECT (player), "playing");
+	rb_shell_player_sync_with_source (data->player);
+	rb_shell_player_sync_buttons (data->player);
+	g_object_notify (G_OBJECT (data->player), "playing");
+
+	/* probably unref the entries? */
+	g_free (data);
 
 	GDK_THREADS_LEAVE ();
 	return FALSE;
@@ -3105,7 +3127,12 @@ playing_stream_cb (RBPlayer *mmplayer,
 
 	/* only emit playing-song-changed etc. when the entry changes */
 	if (player->priv->playing_entry != entry) {
-		player->priv->emit_playing_id = g_idle_add ((GSourceFunc) new_playing_stream_idle_cb, player);
+		NewPlayingStreamData *data;
+		data = g_new0 (NewPlayingStreamData, 1);
+		data->player = player;
+		data->new_entry = entry;
+		data->old_entry = player->priv->playing_entry;
+		player->priv->emit_playing_id = g_idle_add ((GSourceFunc) new_playing_stream_idle_cb, data);
 	} else {
 		player->priv->emit_playing_id = g_idle_add ((GSourceFunc) current_playing_stream_idle_cb, player);
 	}
diff --git a/sources/rb-auto-playlist-source.c b/sources/rb-auto-playlist-source.c
index e3a1a42..0797d52 100644
--- a/sources/rb-auto-playlist-source.c
+++ b/sources/rb-auto-playlist-source.c
@@ -78,6 +78,8 @@ static void rb_auto_playlist_source_get_property (GObject *object,
 /* source methods */
 static gboolean impl_show_popup (RBSource *source);
 static gboolean impl_receive_drag (RBSource *asource, GtkSelectionData *data);
+static gboolean impl_can_delete (RBSource *source);
+static void impl_delete (RBSource *source);
 static void impl_search (RBSource *asource, const char *search_text);
 static void impl_reset_filters (RBSource *asource);
 static void impl_browser_toggled (RBSource *source, gboolean enabled);
@@ -126,6 +128,7 @@ struct _RBAutoPlaylistSourcePrivate
 	RhythmDBQueryModel *cached_all_query;
 	GPtrArray *query;
 	gboolean query_resetting;
+	RhythmDBQueryModelOrderType order_type;
 	RhythmDBQueryModelLimitType limit_type;
 	GValueArray *limit_value;
 
@@ -161,7 +164,8 @@ rb_auto_playlist_source_class_init (RBAutoPlaylistSourceClass *klass)
 	object_class->get_property = rb_auto_playlist_source_get_property;
 
 	source_class->impl_can_cut = (RBSourceFeatureFunc) rb_false_function;
-	source_class->impl_can_delete = (RBSourceFeatureFunc) rb_false_function;
+	source_class->impl_can_delete = impl_can_delete;
+	source_class->impl_delete = impl_delete;
 	source_class->impl_receive_drag = impl_receive_drag;
 	source_class->impl_show_popup = impl_show_popup;
 	source_class->impl_can_browse = (RBSourceFeatureFunc) rb_true_function;
@@ -377,6 +381,8 @@ rb_auto_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node)
 	GValueArray *limit_value = NULL;
 	gchar *sort_key = NULL;
 	gint sort_direction = 0;
+	RhythmDBQueryModelOrderType order_type = RHYTHMDB_QUERY_MODEL_ORDER_MANUAL;
+	gchar *order_key = NULL;
 	GValue val = {0,};
 
 	child = node->children;
@@ -435,24 +441,39 @@ rb_auto_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node)
 		}
 	}
 
-	sort_key = (gchar*) xmlGetProp (node, RB_PLAYLIST_SORT_KEY);
-	if (sort_key && *sort_key) {
-		tmp = xmlGetProp (node, RB_PLAYLIST_SORT_DIRECTION);
-		if (tmp) {
-			sort_direction = atoi ((char*) tmp);
-			g_free (tmp);
-		}
+
+	order_key = (gchar*) xmlGetProp (node, RB_PLAYLIST_ORDER_KEY);
+	if (rb_safe_strcmp (order_key, (gchar *) RB_PLAYLIST_ORDER_RANDOM) == 0) {
+		order_type = RHYTHMDB_QUERY_MODEL_ORDER_RANDOM;
+	} else if (rb_safe_strcmp (order_key, (gchar *) RB_PLAYLIST_ORDER_MANUAL) == 0) {
+		order_type = RHYTHMDB_QUERY_MODEL_ORDER_MANUAL;
 	} else {
-		g_free (sort_key);
-		sort_key = NULL;
-		sort_direction = 0;
+		/* backwards compatibility: use sorted order if there's a sort key,
+		 * manual order otherwise.
+		 */
+		sort_key = (gchar*) xmlGetProp (node, RB_PLAYLIST_SORT_KEY);
+		if (sort_key && *sort_key) {
+			order_type = RHYTHMDB_QUERY_MODEL_ORDER_SORTED;
+			tmp = xmlGetProp (node, RB_PLAYLIST_SORT_DIRECTION);
+			if (tmp) {
+				sort_direction = atoi ((char*) tmp);
+				g_free (tmp);
+			}
+		} else {
+			g_free (sort_key);
+			order_type = RHYTHMDB_QUERY_MODEL_ORDER_MANUAL;
+			sort_key = NULL;
+			sort_direction = 0;
+		}
 	}
 
 	rb_auto_playlist_source_set_query (source, query,
 					   limit_type,
 					   limit_value,
+					   order_type,
 					   sort_key,
 					   sort_direction);
+	g_free (order_key);
 	g_free (sort_key);
 	g_value_array_free (limit_value);
 	rhythmdb_query_free (query);
@@ -622,6 +643,7 @@ impl_receive_drag (RBSource *asource, GtkSelectionData *data)
 					      RHYTHMDB_QUERY_END);
 		rb_auto_playlist_source_set_query (RB_AUTO_PLAYLIST_SOURCE (source), query,
 						   RHYTHMDB_QUERY_MODEL_LIMIT_NONE, NULL,
+						   RHYTHMDB_QUERY_MODEL_ORDER_MANUAL,
 						   NULL, 0);
 
 		rhythmdb_query_free (subquery);
@@ -665,6 +687,7 @@ impl_save_contents_to_xml (RBPlaylistSource *psource,
 	GPtrArray *query;
 	RhythmDBQueryModelLimitType limit_type;
 	GValueArray *limit_value = NULL;
+	RhythmDBQueryModelOrderType order_type;
 	char *sort_key;
 	gint sort_direction;
 	RBAutoPlaylistSource *source = RB_AUTO_PLAYLIST_SOURCE (psource);
@@ -676,6 +699,7 @@ impl_save_contents_to_xml (RBPlaylistSource *psource,
 					   &query,
 					   &limit_type,
 					   &limit_value,
+					   &order_type,
 					   &sort_key,
 					   &sort_direction);
 
@@ -709,6 +733,20 @@ impl_save_contents_to_xml (RBPlaylistSource *psource,
 		g_free (temp_str);
 	}
 
+	switch (order_type) {
+	case RHYTHMDB_QUERY_MODEL_ORDER_MANUAL:
+		xmlSetProp (node, RB_PLAYLIST_ORDER_KEY, RB_PLAYLIST_ORDER_MANUAL);
+		break;
+	case RHYTHMDB_QUERY_MODEL_ORDER_SORTED:
+		xmlSetProp (node, RB_PLAYLIST_ORDER_KEY, RB_PLAYLIST_ORDER_SORTED);
+		break;
+	case RHYTHMDB_QUERY_MODEL_ORDER_RANDOM:
+		xmlSetProp (node, RB_PLAYLIST_ORDER_KEY, RB_PLAYLIST_ORDER_RANDOM);
+		break;
+	default:
+		g_assert_not_reached ();
+	}
+
 	rhythmdb_query_serialize (rb_playlist_source_get_db (psource), query, node);
 	rhythmdb_query_free (query);
 	g_value_array_free (limit_value);
@@ -792,6 +830,7 @@ rb_auto_playlist_source_do_query (RBAutoPlaylistSource *source, gboolean subset)
  * @query: the new database query
  * @limit_type: the playlist limit type
  * @limit_value: the playlist limit value
+ * @order_type: the playlist ordering type (manual, sorted, or random)
  * @sort_key: the sorting key
  * @sort_direction: the sorting direction (as a #GtkSortType)
  *
@@ -803,6 +842,7 @@ rb_auto_playlist_source_set_query (RBAutoPlaylistSource *source,
 				   GPtrArray *query,
 				   RhythmDBQueryModelLimitType limit_type,
 				   GValueArray *limit_value,
+				   RhythmDBQueryModelOrderType order_type,
 				   const char *sort_key,
 				   gint sort_direction)
 {
@@ -830,11 +870,13 @@ rb_auto_playlist_source_set_query (RBAutoPlaylistSource *source,
 	priv->query = rhythmdb_query_copy (query);
 	priv->limit_type = limit_type;
 	priv->limit_value = limit_value ? g_value_array_copy (limit_value) : NULL;
+	priv->order_type = order_type;
 
 	priv->cached_all_query = g_object_new (RHYTHMDB_TYPE_QUERY_MODEL,
 					       "db", db,
 					       "limit-type", priv->limit_type,
 					       "limit-value", priv->limit_value,
+					       "order-type", priv->order_type,
 					       NULL);
 	rb_library_browser_set_model (priv->browser, priv->cached_all_query, TRUE);
 	rhythmdb_do_full_query_async_parsed (db,
@@ -850,6 +892,7 @@ rb_auto_playlist_source_set_query (RBAutoPlaylistSource *source,
  * @query: returns the database query for the playlist
  * @limit_type: returns the playlist limit type
  * @limit_value: returns the playlist limit value
+ * @order_type: returns the playlist ordering type
  * @sort_key: returns the playlist sorting key
  * @sort_direction: returns the playlist sorting direction (as a GtkSortOrder)
  *
@@ -860,6 +903,7 @@ rb_auto_playlist_source_get_query (RBAutoPlaylistSource *source,
 				   GPtrArray **query,
 				   RhythmDBQueryModelLimitType *limit_type,
 				   GValueArray **limit_value,
+				   RhythmDBQueryModelOrderType *order_type,
 				   char **sort_key,
 				   gint *sort_direction)
 {
@@ -874,6 +918,7 @@ rb_auto_playlist_source_get_query (RBAutoPlaylistSource *source,
 	*query = rhythmdb_query_copy (priv->query);
 	*limit_type = priv->limit_type;
 	*limit_value = (priv->limit_value) ? g_value_array_copy (priv->limit_value) : NULL;
+	*order_type = priv->order_type;
 
 	rb_entry_view_get_sorting_order (songs, sort_key, sort_direction);
 }
@@ -976,3 +1021,27 @@ search_action_changed (GtkRadioAction  *action,
 		g_object_unref (source);
 	}
 }
+
+static gboolean
+impl_can_delete (RBSource *source)
+{
+	RBAutoPlaylistSourcePrivate *priv = RB_AUTO_PLAYLIST_SOURCE_GET_PRIVATE (source);
+	/* 'remove' for randomly ordered playlists means 'percolate the selected entries' */
+	return (priv->order_type == RHYTHMDB_QUERY_MODEL_ORDER_RANDOM);
+}
+
+static void
+impl_delete (RBSource *source)
+{
+	RBAutoPlaylistSourcePrivate *priv = RB_AUTO_PLAYLIST_SOURCE_GET_PRIVATE (source);
+	RBEntryView *songs;
+	GList *selection, *i;
+
+	songs = rb_source_get_entry_view (source);
+	selection = rb_entry_view_get_selected_entries (songs);
+	for (i = selection; i != NULL; i = i->next) {
+		rhythmdb_query_model_percolate_entry (priv->cached_all_query, (RhythmDBEntry *)i->data);
+	}
+	g_list_foreach (selection, (GFunc)rhythmdb_entry_unref, NULL);
+	g_list_free (selection);
+}
diff --git a/sources/rb-auto-playlist-source.h b/sources/rb-auto-playlist-source.h
index 9da98c5..83ad06d 100644
--- a/sources/rb-auto-playlist-source.h
+++ b/sources/rb-auto-playlist-source.h
@@ -70,6 +70,7 @@ void		rb_auto_playlist_source_set_query	(RBAutoPlaylistSource *source,
 							 GPtrArray *query,
 							 RhythmDBQueryModelLimitType limit_type,
 							 GValueArray *limit_value,
+							 RhythmDBQueryModelOrderType order_type,
 							 const char *sort_key,
 						 	 gint sort_order);
 
@@ -77,6 +78,7 @@ void		rb_auto_playlist_source_get_query	(RBAutoPlaylistSource *source,
 							 GPtrArray **query,
 							 RhythmDBQueryModelLimitType *limit_type,
 							 GValueArray **limit_value,
+							 RhythmDBQueryModelOrderType *order_type,
 							 char **sort_key,
 							 gint *sort_order);
 
diff --git a/sources/rb-import-errors-source.c b/sources/rb-import-errors-source.c
index 1c9ad5a..c272edf 100644
--- a/sources/rb-import-errors-source.c
+++ b/sources/rb-import-errors-source.c
@@ -162,6 +162,7 @@ rb_import_errors_source_constructor (GType type, guint n_construct_properties,
 	g_boxed_free (RHYTHMDB_TYPE_ENTRY_TYPE, entry_type);
 
 	model = rhythmdb_query_model_new (source->priv->db, query,
+					  RHYTHMDB_QUERY_MODEL_ORDER_SORTED,
 					  (GCompareDataFunc) rhythmdb_query_model_string_sort_func,
 					  GUINT_TO_POINTER (RHYTHMDB_PROP_LOCATION), NULL, FALSE);
 	rhythmdb_query_free (query);
diff --git a/sources/rb-library-source.c b/sources/rb-library-source.c
index 3200b81..9215e32 100644
--- a/sources/rb-library-source.c
+++ b/sources/rb-library-source.c
@@ -1361,6 +1361,7 @@ rb_library_source_add_child_source (const char *path, RBLibrarySource *library_s
 				      RHYTHMDB_QUERY_END);
 	rb_auto_playlist_source_set_query (RB_AUTO_PLAYLIST_SOURCE (source), query,
 					   RHYTHMDB_QUERY_MODEL_LIMIT_NONE, NULL,
+					   RHYTHMDB_QUERY_MODEL_ORDER_SORTED,
 					   sort_column, sort_order);
 	rhythmdb_query_free (query);
 	g_free (sort_column);
diff --git a/sources/rb-missing-files-source.c b/sources/rb-missing-files-source.c
index 8766fb9..65e144a 100644
--- a/sources/rb-missing-files-source.c
+++ b/sources/rb-missing-files-source.c
@@ -176,6 +176,7 @@ rb_missing_files_source_constructor (GType type, guint n_construct_properties,
 	g_boxed_free (RHYTHMDB_TYPE_ENTRY_TYPE, entry_type);
 
 	model = rhythmdb_query_model_new (source->priv->db, query,
+					  RHYTHMDB_QUERY_MODEL_ORDER_MANUAL,
 					  NULL, NULL, NULL, FALSE);
 
 	rhythmdb_query_free (query);
diff --git a/sources/rb-playlist-xml.h b/sources/rb-playlist-xml.h
index 6559dec..2e45f7d 100644
--- a/sources/rb-playlist-xml.h
+++ b/sources/rb-playlist-xml.h
@@ -55,8 +55,14 @@
 #define RB_PLAYLIST_LIMIT_COUNT (xmlChar *) "limit-count"
 #define RB_PLAYLIST_LIMIT_SIZE (xmlChar *) "limit-size"
 #define RB_PLAYLIST_LIMIT_TIME (xmlChar *) "limit-time"
+#define RB_PLAYLIST_ORDER_KEY (xmlChar *) "order-type"
 #define RB_PLAYLIST_SORT_KEY (xmlChar *) "sort-key"
 #define RB_PLAYLIST_SORT_DIRECTION (xmlChar *) "sort-direction"
 #define RB_PLAYLIST_LIMIT (xmlChar *) "limit"
 
+/* values for the 'order-type' attribute */
+#define RB_PLAYLIST_ORDER_MANUAL (xmlChar *) "manual"
+#define RB_PLAYLIST_ORDER_SORTED (xmlChar *) "sorted"
+#define RB_PLAYLIST_ORDER_RANDOM (xmlChar *) "random"
+
 #endif	/* __RB_PLAYLIST_XML_H */
diff --git a/tests/test-rhythmdb-property-model.c b/tests/test-rhythmdb-property-model.c
index c8b2378..e63a173 100644
--- a/tests/test-rhythmdb-property-model.c
+++ b/tests/test-rhythmdb-property-model.c
@@ -205,7 +205,7 @@ START_TEST (test_rhythmdb_property_model_query)
 				        RHYTHMDB_PROP_ARTIST, "x",
 				      RHYTHMDB_QUERY_END);
 
-	model = rhythmdb_query_model_new (db, query, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
+	model = rhythmdb_query_model_new (db, query, RHYTHMDB_QUERY_MODEL_ORDER_SORTED, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
 	rhythmdb_query_free (query);
 
 	query = rhythmdb_query_parse (db,
@@ -214,7 +214,7 @@ START_TEST (test_rhythmdb_property_model_query)
 				      RHYTHMDB_QUERY_PROP_LIKE,
 				        RHYTHMDB_PROP_ARTIST, "y",
 				      RHYTHMDB_QUERY_END);
-	model2 = rhythmdb_query_model_new (db, query, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
+	model2 = rhythmdb_query_model_new (db, query, RHYTHMDB_QUERY_MODEL_ORDER_SORTED, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
 	rhythmdb_query_free (query);
 
 
@@ -335,7 +335,7 @@ START_TEST (test_rhythmdb_property_model_query_chain)
 				        RHYTHMDB_PROP_SEARCH_MATCH, "y",
 				      RHYTHMDB_QUERY_END);
 
-	base_model = rhythmdb_query_model_new (db, query, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
+	base_model = rhythmdb_query_model_new (db, query, RHYTHMDB_QUERY_MODEL_ORDER_SORTED, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
 	rhythmdb_query_free (query);
 
 	query = rhythmdb_query_parse (db,
@@ -344,7 +344,7 @@ START_TEST (test_rhythmdb_property_model_query_chain)
 				      RHYTHMDB_QUERY_PROP_EQUALS,
 				        RHYTHMDB_PROP_TRACK_NUMBER, 1,
 				      RHYTHMDB_QUERY_END);
-	model = rhythmdb_query_model_new (db, query, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
+	model = rhythmdb_query_model_new (db, query, RHYTHMDB_QUERY_MODEL_ORDER_SORTED, (GCompareDataFunc)rhythmdb_query_model_location_sort_func, NULL, NULL, FALSE);
 	rhythmdb_query_free (query);
 
 	rhythmdb_query_model_chain (model, base_model, TRUE);
diff --git a/widgets/rb-query-creator-private.h b/widgets/rb-query-creator-private.h
index 4c0bfaf..a6039e3 100644
--- a/widgets/rb-query-creator-private.h
+++ b/widgets/rb-query-creator-private.h
@@ -30,6 +30,7 @@
 
 #include <gtk/gtk.h>
 #include "rhythmdb.h"
+#include "rhythmdb-query-model.h"
 
 #ifndef __RB_QUERY_CREATOR_PRIVATE_H
 #define __RB_QUERY_CREATOR_PRIVATE_H
@@ -44,6 +45,7 @@ typedef struct
 typedef struct
 {
 	const char *name;
+	RhythmDBQueryModelOrderType order_type;
 	const char *sort_key;
 	const char *sort_descending_name;
 } RBQueryCreatorSortOption;
diff --git a/widgets/rb-query-creator-properties.c b/widgets/rb-query-creator-properties.c
index 4ae961c..d77951e 100644
--- a/widgets/rb-query-creator-properties.c
+++ b/widgets/rb-query-creator-properties.c
@@ -95,21 +95,23 @@ const int num_property_options = G_N_ELEMENTS (property_options);
 
 /*
  * This table describes which properties can be used for sorting a playlist
- * All entries MUST have column keys column keys listed in rb-entry-view.c
+ * All entries with order_type == RHYTHMDB_QUERY_MODEL_ORDER_SORTED
+ * must have column keys column keys listed in rb-entry-view.c
  */
 const RBQueryCreatorSortOption sort_options[] =
 {
-	{ N_("Artist"), "Artist", N_("_In reverse alphabetical order") },
-	{ N_("Album"), "Album", N_("_In reverse alphabetical order") },
-	{ N_("Genre"), "Genre", N_("_In reverse alphabetical order") },
-	{ N_("Title"), "Title", N_("_In reverse alphabetical order") },
-	{ N_("Rating"), "Rating", N_("W_ith more highly rated tracks first") },
-	{ N_("Play Count"), "PlayCount", N_("W_ith more often played songs first") },
-	{ N_("Year"), "Year", N_("W_ith newer tracks first") },
-	{ N_("Duration"), "Time", N_("W_ith longer tracks first") },
-	{ N_("Track Number"), "Track", N_("_In decreasing order")},
-	{ N_("Last Played"), "LastPlayed", N_("W_ith more recently played tracks first") },
-	{ N_("Date Added"), "FirstSeen", N_("W_ith more recently added tracks first") },
+	{ N_("Artist"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Artist", N_("_In reverse alphabetical order") },
+	{ N_("Album"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Album", N_("_In reverse alphabetical order") },
+	{ N_("Genre"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Genre", N_("_In reverse alphabetical order") },
+	{ N_("Title"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Title", N_("_In reverse alphabetical order") },
+	{ N_("Rating"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Rating", N_("W_ith more highly rated tracks first") },
+	{ N_("Play Count"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "PlayCount", N_("W_ith more often played songs first") },
+	{ N_("Year"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Year", N_("W_ith newer tracks first") },
+	{ N_("Duration"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Time", N_("W_ith longer tracks first") },
+	{ N_("Track Number"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "Track", N_("_In decreasing order")},
+	{ N_("Last Played"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "LastPlayed", N_("W_ith more recently played tracks first") },
+	{ N_("Date Added"), RHYTHMDB_QUERY_MODEL_ORDER_SORTED, "FirstSeen", N_("W_ith more recently added tracks first") },
+	{ N_("Random"), RHYTHMDB_QUERY_MODEL_ORDER_RANDOM, NULL, NULL },
 };
 
 const int num_sort_options = G_N_ELEMENTS (sort_options);
diff --git a/widgets/rb-query-creator.c b/widgets/rb-query-creator.c
index 12028cb..eb021a4 100644
--- a/widgets/rb-query-creator.c
+++ b/widgets/rb-query-creator.c
@@ -447,24 +447,32 @@ rb_query_creator_load_query (RBQueryCreator *creator,
 
 static gboolean
 rb_query_creator_set_sorting (RBQueryCreator *creator,
+			      RhythmDBQueryModelOrderType order_type,
                               const char *sort_column,
                               gint sort_direction)
 {
 	RBQueryCreatorPrivate *priv = QUERY_CREATOR_GET_PRIVATE (creator);
 	int i;
 
-	if (!sort_column || ! *sort_column) {
-		g_warning("No playlist sorting order");
+	if (order_type == RHYTHMDB_QUERY_MODEL_ORDER_SORTED) {
+		if (!sort_column || ! *sort_column) {
+			g_warning ("No playlist sorting order");
 
-		sort_column = sort_options[DEFAULT_SORTING_COLUMN].sort_key;
-		sort_direction = DEFAULT_SORTING_ORDER;
+			sort_column = sort_options[DEFAULT_SORTING_COLUMN].sort_key;
+			sort_direction = DEFAULT_SORTING_ORDER;
+		}
 	}
 
 	gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (priv->sort_desc), (sort_direction == GTK_SORT_DESCENDING));
 
-	for (i = 0; i < num_sort_options; i++)
-		if (strcmp (sort_options[i].sort_key, sort_column) == 0)
+	g_print ("setting sort order [%d]%s\n", order_type, sort_column ? sort_column : "<none>");
+	for (i = 0; i < num_sort_options; i++) {
+		if (sort_options[i].order_type != order_type)
+			continue;
+
+		if (rb_safe_strcmp (sort_options[i].sort_key, sort_column) == 0)
 			break;
+	}
 
 	/* check that it is a valid sort option */
 	g_return_val_if_fail (i < num_property_options, FALSE);
@@ -481,6 +489,7 @@ rb_query_creator_set_sorting (RBQueryCreator *creator,
  * @query: an existing query to start from
  * @limit_type: the type of result set limit
  * @limit_value: the result set limit value
+ * @order_type: the ordering type to use for query results
  * @sort_column: the column on which to sort query results
  * @sort_direction: the direction in which to sort query results
  *
@@ -494,6 +503,7 @@ rb_query_creator_new_from_query (RhythmDB *db,
                                  GPtrArray *query,
 				 RhythmDBQueryModelLimitType limit_type,
                                  GValueArray *limit_value,
+				 RhythmDBQueryModelOrderType order_type,
 				 const char *sort_column,
                                  gint sort_direction)
 {
@@ -503,7 +513,7 @@ rb_query_creator_new_from_query (RhythmDB *db,
 		return NULL;
 
 	if ( !rb_query_creator_load_query (creator, query, limit_type, limit_value)
-	   | !rb_query_creator_set_sorting (creator, sort_column, sort_direction)) {
+	   | !rb_query_creator_set_sorting (creator, order_type, sort_column, sort_direction)) {
 		gtk_widget_destroy (GTK_WIDGET (creator));
 		return NULL;
 	}
@@ -603,14 +613,14 @@ rb_query_creator_get_query (RBQueryCreator *creator)
 			data->val = val;
 
 			g_ptr_array_add (sub_query, data);
-			}
-
-			if (disjunction && row->next)
-				rhythmdb_query_append (priv->db,
-						       sub_query,
-						       RHYTHMDB_QUERY_DISJUNCTION,
-						       RHYTHMDB_QUERY_END);
 		}
+
+		if (disjunction && row->next)
+			rhythmdb_query_append (priv->db,
+					       sub_query,
+					       RHYTHMDB_QUERY_DISJUNCTION,
+					       RHYTHMDB_QUERY_END);
+	}
 	query = rhythmdb_query_parse (priv->db,
 				      /* type=songs */
 				      RHYTHMDB_QUERY_PROP_EQUALS,
@@ -682,18 +692,23 @@ rb_query_creator_get_limit (RBQueryCreator *creator,
 /**
  * rb_query_creator_get_sort_order:
  * @creator: #RBQueryCreator instance
+ * @order_type; the ordering type (manual, random, or sorted)
  * @sort_key: returns the sort key name
  * @sort_direction: returns the sort direction
  *
  * Retrieves the sort settings from the query creator.
  * The sort direction is returned as a #GtkSortType value.
+ * Sort key and direction are only returned if the order type
+ * is RHYTHMDB_QUERY_MODEL_ORDER_SORTED.
  */
 void
 rb_query_creator_get_sort_order (RBQueryCreator *creator,
+				 RhythmDBQueryModelOrderType *order_type,
                                  const char **sort_key,
                                  gint *sort_direction)
 {
 	RBQueryCreatorPrivate *priv;
+	int i;
 
 	g_return_if_fail (RB_IS_QUERY_CREATOR (creator));
 
@@ -706,11 +721,14 @@ rb_query_creator_get_sort_order (RBQueryCreator *creator,
 			*sort_direction = GTK_SORT_ASCENDING;
 	}
 
+	i = gtk_option_menu_get_history (GTK_OPTION_MENU (priv->sort_menu));
+
 	if (sort_key != NULL) {
-		int i;
-		i = gtk_option_menu_get_history (GTK_OPTION_MENU (priv->sort_menu));
 		*sort_key = sort_options[i].sort_key;
 	}
+	if (order_type != NULL) {
+		*order_type = sort_options[i].order_type;
+	}
 }
 
 static void
@@ -966,8 +984,14 @@ sort_option_menu_changed (GtkOptionMenu *propmenu,
 	RBQueryCreatorPrivate *priv = QUERY_CREATOR_GET_PRIVATE (creator);
 	int index = gtk_option_menu_get_history (propmenu);
 
-	gtk_button_set_label (GTK_BUTTON (priv->sort_desc), _(sort_options[index].sort_descending_name));
-	rb_debug("changing descending label to %s[%d]", sort_options[index].sort_descending_name, index);
+	if (sort_options[index].sort_descending_name != NULL) {
+		rb_debug ("changing descending label to %s[%d]", sort_options[index].sort_descending_name, index);
+		gtk_widget_show (priv->sort_desc);
+		gtk_button_set_label (GTK_BUTTON (priv->sort_desc), _(sort_options[index].sort_descending_name));
+	} else {
+		rb_debug ("hiding descending label as this sort option has no such option");
+		gtk_widget_hide (priv->sort_desc);
+	}
 }
 
 static void
diff --git a/widgets/rb-query-creator.h b/widgets/rb-query-creator.h
index 7e2eaed..670f63d 100644
--- a/widgets/rb-query-creator.h
+++ b/widgets/rb-query-creator.h
@@ -63,6 +63,7 @@ GtkWidget *	rb_query_creator_new		(RhythmDB *db);
 
 GtkWidget *	rb_query_creator_new_from_query	(RhythmDB *db, GPtrArray *query,
 						 RhythmDBQueryModelLimitType limit_type, GValueArray *limit_value,
+						 RhythmDBQueryModelOrderType order_type,
 						 const char *sort_column, gint sort_direction);
 
 GPtrArray *	rb_query_creator_get_query	(RBQueryCreator *creator);
@@ -71,7 +72,10 @@ void		rb_query_creator_get_limit	(RBQueryCreator *creator,
 						 RhythmDBQueryModelLimitType *type,
 						 GValueArray **limit);
 
-void		rb_query_creator_get_sort_order (RBQueryCreator *creator, const char **sort_key, gint *sort_direction);
+void		rb_query_creator_get_sort_order (RBQueryCreator *creator,
+						 RhythmDBQueryModelOrderType *order_type,
+						 const char **sort_key,
+						 gint *sort_direction);
 
 G_END_DECLS
 
