--- a/browser/components/newtab/PlacesProvider.jsm
+++ b/browser/components/newtab/PlacesProvider.jsm
@@ -25,16 +25,19 @@ XPCOMUtils.defineLazyGetter(this, "Event
   return EventEmitter;
 });
 
 XPCOMUtils.defineLazyGetter(this, "gPrincipal", function() {
   let uri = Services.io.newURI("about:newtab", null, null);
   return Services.scriptSecurityManager.getNoAppCodebasePrincipal(uri);
 });
 
+XPCOMUtils.defineLazyModuleGetter(this, "Task",
+                                  "resource://gre/modules/Task.jsm");
+
 // The maximum number of results PlacesProvider retrieves from history.
 const HISTORY_RESULTS_LIMIT = 100;
 
 /**
  * Singleton that checks if a given link should be displayed on about:newtab
  * or if we should rather not do it for security reasons. URIs that inherit
  * their caller's principal will be filtered.
  */
@@ -63,56 +66,16 @@ let LinkChecker = {
     } catch (e) {
       // We got a weird URI or one that would inherit the caller's principal.
       Cu.reportError(e);
     }
     return result;
   }
 };
 
-/**
- * Singleton that provides utility functions for links.
- * A link is a plain object that looks like this:
- *
- * {
- *   url: "http://www.mozilla.org/",
- *   title: "Mozilla",
- *   frecency: 1337,
- *   lastVisitDate: 1394678824766431,
- * }
- */
-const LinkUtils = {
-  _sortProperties: [
-    "frecency",
-    "lastVisitDate",
-    "url",
-  ],
-
-  /**
-   * Compares two links.
-   *
-   * @param {String} aLink1 The first link.
-   * @param {String} aLink2 The second link.
-   * @return {Number} A negative number if aLink1 is ordered before aLink2, zero if
-   *         aLink1 and aLink2 have the same ordering, or a positive number if
-   *         aLink1 is ordered after aLink2.
-   *         Order is ascending.
-   */
-  compareLinks: function LinkUtils_compareLinks(aLink1, aLink2) {
-    for (let prop of LinkUtils._sortProperties) {
-      if (!aLink1.hasOwnProperty(prop) || !aLink2.hasOwnProperty(prop)) {
-        throw new Error("Comparable link missing required property: " + prop);
-      }
-    }
-    return aLink2.frecency - aLink1.frecency ||
-           aLink2.lastVisitDate - aLink1.lastVisitDate ||
-           aLink1.url.localeCompare(aLink2.url);
-  },
-};
-
 /* Queries history to retrieve the most visited sites. Emits events when the
  * history changes.
  * Implements the EventEmitter interface.
  */
 let Links = function Links() {
   EventEmitter.decorate(this);
 };
 
@@ -187,85 +150,99 @@ Links.prototype = {
     PlacesUtils.history.removeObserver(this.historyObserver);
   },
 
   /**
    * Gets the current set of links delivered by this provider.
    *
    * @returns {Promise} Returns a promise with the array of links as payload.
    */
-  getLinks: function PlacesProvider_getLinks() {
-    let getLinksPromise = new Promise((resolve, reject) => {
-      let options = PlacesUtils.history.getNewQueryOptions();
-      options.maxResults = this.maxNumLinks;
+  getLinks: Task.async(function*() {
+    // Select a single page per host with highest frecency, highest recency.
+    // Choose N top such pages. Note +rev_host, to turn off optimizer per :mak
+    // suggestion.
+    let sqlQuery = `SELECT url, title, frecency,
+                          last_visit_date as lastVisitDate,
+                          "history" as type
+                   FROM moz_places
+                   WHERE frecency in (
+                     SELECT MAX(frecency) as frecency
+                     FROM moz_places
+                     WHERE hidden = 0 AND last_visit_date NOTNULL
+                     GROUP BY +rev_host
+                     ORDER BY frecency DESC
+                     LIMIT :limit
+                   )
+                   GROUP BY rev_host HAVING MAX(lastVisitDate)
+                   ORDER BY frecency DESC, lastVisitDate DESC, url`;
 
-      // Sort by frecency, descending.
-      options.sortingMode = Ci.nsINavHistoryQueryOptions
-        .SORT_BY_FRECENCY_DESCENDING;
+    let links = yield this.executePlacesQuery(sqlQuery, {
+                  columns: ["url", "title", "lastVisitDate", "frecency", "type"],
+                  params: {limit: this.maxNumLinks}
+                });
 
-      let links = [];
+    return links.filter(link => LinkChecker.checkLoadURI(link.url));
+  }),
 
-      let queryHandlers = {
-        handleResult: function(aResultSet) {
-          for (let row = aResultSet.getNextRow(); row; row = aResultSet.getNextRow()) {
-            let url = row.getResultByIndex(1);
-            if (LinkChecker.checkLoadURI(url)) {
-              let link = {
-                url: url,
-                title: row.getResultByIndex(2),
-                frecency: row.getResultByIndex(12),
-                lastVisitDate: row.getResultByIndex(5),
-                type: "history",
-              };
-              links.push(link);
+  /**
+   * Executes arbitrary query against places database
+   *
+   * @param {String} aSql
+   *        SQL query to execute
+   * @param {Object} [optional] aOptions
+   *        aOptions.columns - an array of column names. if supplied the returned
+   *        items will consist of objects keyed on column names. Otherwise
+   *        an array of raw values is returned in the select order
+   *        aOptions.param - an object of SQL binding parameters
+   *        aOptions.callback - a callback to handle query rows
+   *
+   * @returns {Promise} Returns a promise with the array of retrieved items
+   */
+  executePlacesQuery: Task.async(function*(aSql, aOptions={}) {
+    let {columns, params, callback} = aOptions;
+    let items = [];
+    let queryError = null;
+    let conn = yield PlacesUtils.promiseDBConnection();
+    yield conn.executeCached(aSql, params, aRow => {
+      try {
+        // check if caller wants to handle query raws
+        if (callback) {
+          callback(aRow);
+        }
+        // otherwise fill in the item and add items array
+        else {
+          let item = null;
+          // if columns array is given construct an object
+          if (columns && Array.isArray(columns)) {
+            item = {};
+            columns.forEach(column => {
+              item[column] = aRow.getResultByName(column);
+            });
+          } else {
+            // if no columns - make an array of raw values
+            item = [];
+            for (let i = 0; i < aRow.numEntries; i++) {
+              item.push(aRow.getResultByIndex(i));
             }
           }
-        },
-
-        handleError: function(aError) {
-          reject(aError);
-        },
-
-        handleCompletion: function(aReason) { // jshint ignore:line
-          // The Places query breaks ties in frecency by place ID descending, but
-          // that's different from how Links.compareLinks breaks ties, because
-          // compareLinks doesn't have access to place IDs.  It's very important
-          // that the initial list of links is sorted in the same order imposed by
-          // compareLinks, because Links uses compareLinks to perform binary
-          // searches on the list.  So, ensure the list is so ordered.
-          let i = 1;
-          let outOfOrder = [];
-          while (i < links.length) {
-            if (LinkUtils.compareLinks(links[i - 1], links[i]) > 0) {
-              outOfOrder.push(links.splice(i, 1)[0]);
-            } else {
-              i++;
-            }
-          }
-          for (let link of outOfOrder) {
-            i = BinarySearch.insertionIndexOf(LinkUtils.compareLinks, links, link);
-            links.splice(i, 0, link);
-          }
-
-          resolve(links);
+          items.push(item);
         }
-      };
-
-      // Execute the query.
-      let query = PlacesUtils.history.getNewQuery();
-      let db = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase);
-      db.asyncExecuteLegacyQueries([query], 1, options, queryHandlers);
+      } catch (e) {
+        queryError = e;
+        throw StopIteration;
+      }
     });
-
-    return getLinksPromise;
-  }
+    if (queryError) {
+      throw new Error(queryError);
+    }
+    return items;
+  }),
 };
 
 /**
  * Singleton that serves as the default link provider for the grid.
  */
 const gLinks = new Links(); // jshint ignore:line
 
 let PlacesProvider = {
   LinkChecker: LinkChecker,
-  LinkUtils: LinkUtils,
   links: gLinks,
 };

--- a/browser/components/newtab/tests/xpcshell/test_PlacesProvider.js
+++ b/browser/components/newtab/tests/xpcshell/test_PlacesProvider.js
@@ -26,16 +26,40 @@ XPCOMUtils.defineLazyModuleGetter(this, 
 
 // ensure a profile exists
 do_get_profile();
 
 function run_test() {
   run_next_test();
 }
 
+// url prefix for test history population
+const TEST_URL = "https://mozilla.com/";
+// time when the test starts execution
+const TIME_NOW = (new Date()).getTime();
+
+// utility function to compute past timestap
+function timeDaysAgo(numDays) {
+  return TIME_NOW - (numDays * 24 * 60 * 60 * 1000);
+}
+
+// utility function to make a visit for insetion into places db
+function makeVisit(index, daysAgo, isTyped, domain=TEST_URL) {
+  let {
+    TRANSITION_TYPED,
+    TRANSITION_LINK
+  } = PlacesUtils.history;
+
+  return {
+    uri: NetUtil.newURI(`${domain}${index}`),
+    visitDate: timeDaysAgo(daysAgo),
+    transition: (isTyped) ? TRANSITION_TYPED : TRANSITION_LINK,
+  };
+}
+
 /** Test LinkChecker **/
 
 add_task(function test_LinkChecker_securityCheck() {
 
   let urls = [
     {url: "file://home/file/image.png", expected: false},
     {url: "resource:///modules/PlacesProvider.jsm", expected: false},
     {url: "javascript:alert('hello')", expected: false}, // jshint ignore:line
@@ -45,107 +69,16 @@ add_task(function test_LinkChecker_secur
     {url: "ftp://example.com", expected: true},
   ];
   for (let {url, expected} of urls) {
     let observed = PlacesProvider.LinkChecker.checkLoadURI(url);
     equal(observed , expected, `can load "${url}"?`);
   }
 });
 
-/** Test LinkUtils **/
-
-add_task(function test_LinkUtils_compareLinks() {
-
-  let fixtures = {
-    firstOlder: {
-      url: "http://www.mozilla.org/firstolder",
-      title: "Mozilla",
-      frecency: 1337,
-      lastVisitDate: 1394678824766431,
-    },
-    older: {
-      url: "http://www.mozilla.org/older",
-      title: "Mozilla",
-      frecency: 1337,
-      lastVisitDate: 1394678824766431,
-    },
-    newer: {
-      url: "http://www.mozilla.org/newer",
-      title: "Mozilla",
-      frecency: 1337,
-      lastVisitDate: 1494678824766431,
-    },
-    moreFrecent: {
-      url: "http://www.mozilla.org/moreFrecent",
-      title: "Mozilla",
-      frecency: 1337357,
-      lastVisitDate: 1394678824766431,
-    }
-  };
-
-  let links = [
-    // tests string ordering, f is before o
-    {link1: fixtures.firstOlder, link2: fixtures.older, expected: false},
-
-    // test identity
-    {link1: fixtures.older, link2: fixtures.older, expected: false},
-
-    // test ordering by date
-    {link1: fixtures.older, link2: fixtures.newer, expected: true},
-    {link1: fixtures.newer, link2: fixtures.older, expected: false},
-
-    // test frecency
-    {link1: fixtures.moreFrecent, link2: fixtures.older, expected: false},
-  ];
-
-  for (let {link1, link2, expected} of links) {
-    let observed = PlacesProvider.LinkUtils.compareLinks(link1, link2) > 0;
-    equal(observed , expected, `comparing ${link1.url} and ${link2.url}`);
-  }
-
-  // test error scenarios
-
-  let errorFixtures = {
-    missingFrecency: {
-      url: "http://www.mozilla.org/firstolder",
-      title: "Mozilla",
-      lastVisitDate: 1394678824766431,
-    },
-    missingVisitDate: {
-      url: "http://www.mozilla.org/firstolder",
-      title: "Mozilla",
-      frecency: 1337,
-    },
-    missingURL: {
-      title: "Mozilla",
-      frecency: 1337,
-      lastVisitDate: 1394678824766431,
-    }
-  };
-
-  let errorLinks = [
-    {link1: fixtures.older, link2: errorFixtures.missingFrecency},
-    {link2: fixtures.older, link1: errorFixtures.missingFrecency},
-    {link1: fixtures.older, link2: errorFixtures.missingVisitDate},
-    {link1: fixtures.older, link2: errorFixtures.missingURL},
-    {link1: errorFixtures.missingFrecency, link2: errorFixtures.missingVisitDate}
-  ];
-
-  let errorCount = 0;
-  for (let {link1, link2} of errorLinks) {
-    try {
-      let observed = PlacesProvider.LinkUtils.compareLinks(link1, link2) > 0; // jshint ignore:line
-    } catch (e) {
-      ok(true, `exception for comparison of ${link1.url} and ${link2.url}`);
-      errorCount += 1;
-    }
-  }
-  equal(errorCount, errorLinks.length);
-});
-
 /** Test Provider **/
 
 add_task(function* test_Links_getLinks() {
   yield PlacesTestUtils.clearHistory();
   let provider = PlacesProvider.links;
 
   let links = yield provider.getLinks();
   equal(links.length, 0, "empty history yields empty links");
@@ -157,51 +90,58 @@ add_task(function* test_Links_getLinks()
   links = yield provider.getLinks();
   equal(links.length, 1, "adding a visit yields a link");
   equal(links[0].url, testURI.spec, "added visit corresponds to added url");
 });
 
 add_task(function* test_Links_getLinks_Order() {
   yield PlacesTestUtils.clearHistory();
   let provider = PlacesProvider.links;
-  let {
-    TRANSITION_TYPED,
-    TRANSITION_LINK
-  } = PlacesUtils.history;
 
-  function timeDaysAgo(numDays) {
-    let now = new Date();
-    return now.getTime() - (numDays * 24 * 60 * 60 * 1000);
-  }
-
-  let timeEarlier = timeDaysAgo(0);
-  let timeLater = timeDaysAgo(2);
-
+  // all four visits must come from different domains to avoid deduplication
   let visits = [
-    // frecency 200
-    {uri: NetUtil.newURI("https://mozilla.com/0"), visitDate: timeEarlier, transition: TRANSITION_TYPED},
-    // sort by url, frecency 200
-    {uri: NetUtil.newURI("https://mozilla.com/1"), visitDate: timeEarlier, transition: TRANSITION_TYPED},
-    // sort by last visit date, frecency 200
-    {uri: NetUtil.newURI("https://mozilla.com/2"), visitDate: timeLater, transition: TRANSITION_TYPED},
-    // sort by frecency, frecency 10
-    {uri: NetUtil.newURI("https://mozilla.com/3"), visitDate: timeLater, transition: TRANSITION_LINK},
+    makeVisit(0, 0, true, "http://bar.com/"), // frecency 200, today
+    makeVisit(1, 0, true, "http://foo.com/"), // frecency 200, today
+    makeVisit(2, 2, true, "http://buz.com/"), // frecency 200, 2 days ago
+    makeVisit(3, 2, false, "http://aaa.com/"), // frecency 10, 2 days ago, transition
   ];
 
   let links = yield provider.getLinks();
   equal(links.length, 0, "empty history yields empty links");
   yield PlacesTestUtils.addVisits(visits);
 
   links = yield provider.getLinks();
   equal(links.length, visits.length, "number of links added is the same as obtain by getLinks");
   for (let i = 0; i < links.length; i++) {
     equal(links[i].url, visits[i].uri.spec, "links are obtained in the expected order");
   }
 });
 
+add_task(function* test_Links_getLinks_Deduplication() {
+  yield PlacesTestUtils.clearHistory();
+  let provider = PlacesProvider.links;
+
+  // all for visits must come from different domains to avoid deduplication
+  let visits = [
+    makeVisit(0, 2, true, "http://bar.com/"), // frecency 200, 2 days ago
+    makeVisit(1, 0, true, "http://bar.com/"), // frecency 200, today
+    makeVisit(2, 0, false, "http://foo.com/"), // frecency 10, today
+    makeVisit(3, 0, true, "http://foo.com/"), // frecency 200, today
+  ];
+
+  let links = yield provider.getLinks();
+  equal(links.length, 0, "empty history yields empty links");
+  yield PlacesTestUtils.addVisits(visits);
+
+  links = yield provider.getLinks();
+  equal(links.length, 2, "only two links must be left after deduplication");
+  equal(links[0].url, visits[1].uri.spec, "earliest link is present");
+  equal(links[1].url, visits[3].uri.spec, "most fresent link is present");
+});
+
 add_task(function* test_Links_onLinkChanged() {
   let provider = PlacesProvider.links;
   provider.init();
 
   let url = "https://example.com/onFrecencyChanged1";
   let linkChangedMsgCount = 0;
 
   let linkChangedPromise = new Promise(resolve => {
@@ -300,8 +240,127 @@ add_task(function* test_Links_onManyLink
 
   // trigger DecayFrecency
   PlacesUtils.history.QueryInterface(Ci.nsIObserver).
     observe(null, "idle-daily", "");
 
   yield promise;
   provider.destroy();
 });
+
+add_task(function* test_Links_execute_query() {
+  yield PlacesTestUtils.clearHistory();
+  let provider = PlacesProvider.links;
+
+  let visits = [
+    makeVisit(0, 0, true), // frecency 200, today
+    makeVisit(1, 0, true), // frecency 200, today
+    makeVisit(2, 2, true), // frecency 200, 2 days ago
+    makeVisit(3, 2, false), // frecency 10, 2 days ago, transition
+  ];
+
+  yield PlacesTestUtils.addVisits(visits);
+
+  function testItemValue(results, index, value) {
+    equal(results[index][0], `${TEST_URL}${value}`, "raw url");
+    equal(results[index][1], `test visit for ${TEST_URL}${value}`, "raw title");
+  }
+
+  function testItemObject(results, index, columnValues) {
+    Object.keys(columnValues).forEach(name => {
+      equal(results[index][name], columnValues[name], "object name " + name);
+    });
+  }
+
+  // select all 4 records
+  let results = yield provider.executePlacesQuery("select url, title from moz_places");
+  equal(results.length, 4, "expect 4 items");
+  // check for insert order sequence
+  for (let i = 0; i < results.length; i++) {
+    testItemValue(results, i, i);
+  }
+
+  // test parameter passing
+  results = yield provider.executePlacesQuery(
+              "select url, title from moz_places limit :limit",
+              {params: {limit: 2}}
+            );
+  equal(results.length, 2, "expect 2 items");
+  for (let i = 0; i < results.length; i++) {
+    testItemValue(results, i, i);
+  }
+
+  // test extracting items by name
+  results = yield provider.executePlacesQuery(
+              "select url, title from moz_places limit :limit",
+              {columns: ["url", "title"], params: {limit: 4}}
+            );
+  equal(results.length, 4, "expect 4 items");
+  for (let i = 0; i < results.length; i++) {
+    testItemObject(results, i, {
+      "url": `${TEST_URL}${i}`,
+      "title": `test visit for ${TEST_URL}${i}`,
+    });
+  }
+
+  // test ordering
+  results = yield provider.executePlacesQuery(
+              "select url, title, last_visit_date, frecency from moz_places " +
+              "order by frecency DESC, last_visit_date DESC, url DESC limit :limit",
+              {columns: ["url", "title", "last_visit_date", "frecency"], params: {limit: 4}}
+            );
+  equal(results.length, 4, "expect 4 items");
+  testItemObject(results, 0, {url: `${TEST_URL}1`});
+  testItemObject(results, 1, {url: `${TEST_URL}0`});
+  testItemObject(results, 2, {url: `${TEST_URL}2`});
+  testItemObject(results, 3, {url: `${TEST_URL}3`});
+
+  // test callback passing
+  results = [];
+  function handleRow(aRow) {
+    results.push({
+      url:              aRow.getResultByName("url"),
+      title:            aRow.getResultByName("title"),
+      last_visit_date:  aRow.getResultByName("last_visit_date"),
+      frecency:         aRow.getResultByName("frecency")
+    });
+  };
+  yield provider.executePlacesQuery(
+        "select url, title, last_visit_date, frecency from moz_places " +
+        "order by frecency DESC, last_visit_date DESC, url DESC",
+        {callback: handleRow}
+      );
+  equal(results.length, 4, "expect 4 items");
+  testItemObject(results, 0, {url: `${TEST_URL}1`});
+  testItemObject(results, 1, {url: `${TEST_URL}0`});
+  testItemObject(results, 2, {url: `${TEST_URL}2`});
+  testItemObject(results, 3, {url: `${TEST_URL}3`});
+
+  // negative test cases
+  // bad sql
+  try {
+    yield provider.executePlacesQuery("select from moz");
+    do_throw("bad sql should've thrown");
+  }
+  catch (e) {
+    do_check_true("expected failure - bad sql");
+  }
+  // missing bindings
+  try {
+    yield provider.executePlacesQuery("select * from moz_places limit :limit");
+    do_throw("bad sql should've thrown");
+  }
+  catch (e) {
+    do_check_true("expected failure - missing bidning");
+  }
+  // non-existent column name
+  try {
+    yield provider.executePlacesQuery("select * from moz_places limit :limit",
+                                     {columns: ["no-such-column"], params: {limit: 4}});
+    do_throw("bad sql should've thrown");
+  }
+  catch (e) {
+    do_check_true("expected failure - wrong column name");
+  }
+
+  // cleanup
+  yield PlacesTestUtils.clearHistory();
+});