What is the algorithm used for Index Recommendation in SQL Databases? I have used tuning adviser tool in SQL Server which provide index recommendation based on a given workload. 

I want to create a similar tool for PostgreSQL. I went through some research papers. But I am unable to find the exact algorithm used by SQL Server Tuning Adviser to provide index recommendations. 

If anyone is aware of the algorithm or any source from where I can get the algorithm please guide me. Please note that I want to provide recommendation based on a workload, not for a single query. Thanks in advance.
The database tuning advisor exact algorithm isn't documented, but you can have somewhat of a look how it works by using a server side trace to look at the commands it generates.

I'm not sure what algorithm it uses to determine which ones to create but it relies heavily on  creating hypothetical indexes and then using the undocumented DBCC AUTOPILOT to create execution plans that use these hypothetical indexes.

I suppose it then somehow compares the resulting execution plans to determine which ones have the lower cost.

Daniel Farina has an excellent post explaining how it works and how you can do it by hand if you really want to: SQL Server Performance Tuning with Hypothetical Indexes.

From that page: 


  You are tuning a query and need to check the performance impact of a
  new index. But the table has millions of rows and it will take a lot
  of time to create an index. Keep reading and you will see how to
  create and test hypothetical indexes with the undocumented DBCC
  AUTOPILOT command.


and


  Since this is an undocumented feature there is not information about
  it but, as far as I can tell, giving the fact that AUTOPILOT is the
  key component of Database Engine Tuning Advisor (DTA); this should
  work on all version in which DTA is available.