I hit this, and upon investigation I found that it appears to be stale records in nova_api_db.build_requests.

In my case, I think these are lost "scheduling" requests?

MariaDB [nova_api]> select * from build_requests;
+---------------------+------------+----+-----------------+----------------------------------+----------------------------------+--------------------------+-------------------+----------+----------+------------+--------------------------------------+--------------+--------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------+--------------+----------+-----------+---------------+----------+-----------------------+
| created_at          | updated_at | id | request_spec_id | project_id                       | user_id                          | display_name             | instance_metadata | progress | vm_state | task_state | image_ref                            | access_ip_v4 | access_ip_v6 | info_cache                                                                                                                                                                                                                                                              | security_groups                                                                                                                               | config_drive | key_name | locked_by | instance_uuid | instance | block_device_mappings |
+---------------------+------------+----+-----------------+----------------------------------+----------------------------------+--------------------------+-------------------+----------+----------+------------+--------------------------------------+--------------+--------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------+--------------+----------+-----------+---------------+----------+-----------------------+
| 2016-08-10 14:54:33 | NULL       | 89 |             281 | a392bb9328fc43f4ae44fe14db3520fd | 0ea46d4298a5447f8e0b552c810b10bd | bp2_prod_1               | {}                |        0 | building | scheduling | b2a5a52c-4d39-459c-9001-4e49abfba593 | NULL         | NULL         | {"nova_object.version": "1.5", "nova_object.changes": ["instance_uuid", "network_info"], "nova_object.name": "InstanceInfoCache", "nova_object.data": {"instance_uuid": "987e1a2f-c886-4f18-b798-60ce785e1056", "network_info": "[]"}, "nova_object.namespace": "nova"} | {"nova_object.version": "1.0", "nova_object.name": "SecurityGroupList", "nova_object.data": {"objects": []}, "nova_object.namespace": "nova"} |            0 | NULL     | NULL      | NULL          | NULL     | NULL                  |
| 2016-10-15 03:51:14 | NULL       | 90 |             689 | 8fca764a642842aeacbdff79a76e50c5 | 9e50cfdc5a524165ae2938acfd72f0a0 | bamboo-6500-repo-manager | {}                |        0 | building | scheduling |                                      | NULL         | NULL         | {"nova_object.version": "1.5", "nova_object.changes": ["instance_uuid", "network_info"], "nova_object.name": "InstanceInfoCache", "nova_object.data": {"instance_uuid": "ea26bc22-1330-4752-8252-bf729ca9b286", "network_info": "[]"}, "nova_object.namespace": "nova"} | {"nova_object.version": "1.0", "nova_object.name": "SecurityGroupList", "nova_object.data": {"objects": []}, "nova_object.namespace": "nova"} |            0 | NULL     | NULL      | NULL          | NULL     | NULL                  |
+---------------------+------------+----+-----------------+----------------------------------+----------------------------------+--------------------------+-------------------+----------+----------+------------+--------------------------------------+--------------+--------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------+--------------+----------+-----------+---------------+----------+-----------------------+
2 rows in set (0.00 sec)

Since they looked old, and unnecessary, I went ahead and deleted them from the table. This cleared the issue and everything seems good now?