Occasionally, you may need to defragment or rebuild your UIM indexes.
You will need to reindex on a regular basis (off peak hours on weekends or once a month at a minimum). Typically the more frequently you reindex, the shorter it will take. This sort of operation is analogous to defragmenting your hard drive. The longer you wait between defragmentation operations, the longer it will take.
Also, as part of regular maintenance, run UPDATE STATISTICS after performing a reindex as well as running DBCC CHECKDB as a first step with all maintenance (to make sure you don't have any corrupted indexes and for general database health).
Please reference the following Microsoft Articles regarding DBCC CHECK DB and UPDATE STATISTICS:
If you are using any supported edition of SQL Server that is not an Enterprise Edition, then index rebuilds must be performed offline.
Online index rebuilds were introduced with SQL Server 2005 Enterprise Edition. This ability allows you to rebuild indexes without taking the index offline and without locking the table while the index is being rebuilt. What this means is that the data_engine and other connections to the NIS will be able to access SLM data while the index rebuild is happening.
Note that if you are using an Enterprise Edition of SQL Server 2005 or later and chose to perform an online index rebuild, it is a longer operation than rebuilding them offline. If you can afford the downtime, an offline index rebuild is still recommended since it is faster.
Defragmenting indexes on the other hand is an online operation. This means that while the index defragmentation process is happening, your users will be able to access the data.
Also, rebuilding indexes is often faster than defragmenting them.
There are several articles on the internet which go into depth on how to rebuild and defragment indexes for SQL Server databases as well as other best practices. Additionally, UIM has a whitepaper on SQL Server Best Practices (attached to this article).