Your ix_hugetable looks quite useless because:

• it is the clustered index (PK)
• the INCLUDE makes no difference because a clustered index INCLUDEs all non-key columns (non-key values at lowest leaf = INCLUDEd = what a clustered index is)

In addition: - added or fk should be first - ID is first = not much use

Try changing the clustered key to (added, fk, id) and drop ix_hugetable. You've already tried (fk, added, id). If nothing else, you'll save a lot of disk space and index maintenance

Another option might be to try the FORCE ORDER hint with table order boh ways and no JOIN/INDEX hints. I try not to use JOIN/INDEX hints personally because you remove options for the optimiser. Many years ago I was told (seminar with a SQL Guru) that FORCE ORDER hint can help when you have huge table JOIN small table: YMMV 7 years later...

Oh, and let us know where the DBA lives so we can arrange for some percussion adjustment

Edit, after 02 Jun update

The 4th column is not part of the non-clustered index so it uses the clustered index.

Try changing the NC index to INCLUDE the value column so it doesn't have to access the value column for the clustered index

create nonclustered index ix_hugetable on dbo.hugetable (
    fk asc, added asc
) include(value)

Note: If value is not nullable then it is the same as COUNT(*) semantically. But for SUM it need the actual value, not existence.

As an example, if you change COUNT(value) to COUNT(DISTINCT value) without changing the index it should break the query again because it has to process value as a value, not as existence.

The query needs 3 columns: added, fk, value. The first 2 are filtered/joined so are key columns. value is just used so can be included. Classic use of a covering index.

The simplest solution is this:

SELECT DISTINCT city_name, country_name FROM yourtable

That takes the list of result rows and returns each one only once, even if it appears in the table multiple times. See "DISTINCT" in http://docs.oracle.com/cd/B28359_01/server.111/b28286/statements_10002.htm fro details.

If you also want to know mor information about each row group, like how many hotels exist in each city you can use GROUP BY instead:

SELECT city_name, country_name, COUNT(1) AS Cnt
  FROM yourtable
 GROUP BY city_name, country_name

This again returns each city only once but additionally counts how often it appears in the table. See http://docs.oracle.com/cd/B28359_01/server.111/b28286/statements_10002.htm#i2065777 for more details on that.

SQL Fiddle

Oracle 11g R2 Schema Setup:

CREATE TABLE hotels(name VARCHAR(100),city_name VARCHAR(100),country_name VARCHAR(100));

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel1','Seattle','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel2','Seattle','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel5','Seattle','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel7','Washington','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel8','New York','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel9','New York','USA');

Query 1:

SELECT DISTINCT city_name,country_name FROM hotels

Results:

|  CITY_NAME | COUNTRY_NAME |
-----------------------------
|    Seattle |          USA |
| Washington |          USA |
|   New York |          USA |

Query 2:

SELECT city_name,country_name, COUNT(1) cnt
  FROM hotels
 GROUP BY city_name,country_name

Results:

|  CITY_NAME | COUNTRY_NAME | CNT |
-----------------------------------
|    Seattle |          USA |   3 |
| Washington |          USA |   1 |
|   New York |          USA |   2 |

If you want to create a view for each country you can just add a WHERE clause with the country name like this:

SQL Fiddle

Oracle 11g R2 Schema Setup:

CREATE TABLE hotels(name VARCHAR(100),city_name VARCHAR(100),country_name VARCHAR(100));

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel1','Seattle','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel2','Seattle','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel5','Seattle','USA');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel7','Hamburg','Germany');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel8','Paris','France');

INSERT INTO hotels(name,city_name,country_name)
VALUES('hotel9','Paris','France');


CREATE VIEW US_Hotels 
AS
SELECT city_name,country_name, COUNT(1) cnt
  FROM hotels
 WHERE country_name = 'USA'
 GROUP BY city_name,country_name;


CREATE VIEW Ger_Hotels 
AS
SELECT city_name,country_name, COUNT(1) cnt
  FROM hotels
 WHERE country_name = 'Germany'
 GROUP BY city_name,country_name;

Query 1:

SELECT * FROM US_Hotels

Results:

| CITY_NAME | COUNTRY_NAME | CNT |
----------------------------------
|   Seattle |          USA |   3 |

Query 2:

SELECT * FROM Ger_Hotels

Results:

| CITY_NAME | COUNTRY_NAME | CNT |
----------------------------------
|   Hamburg |      Germany |   1 |