What is the fastest way to get node title from nid? Say I have an nid (or a lot of them). Would it be faster to load the node to access get the title, or do the very simple db_query required to get the node title?
You said fastest. 

If you can compromise two things, this should be the fastest one. Now, note that you have to compromise:


If you are only trying to get the node title, and if you are sure that there are no other hook_node_load implementations (basically module handlers that would alter the node load at the time they are loaded), you can skip using the node_load() or node_load_multiple() functions and go for this solution.
When loading a node from the database, it's advised that you use a query tag to make sure that the user has access to those nodes. If you don't use any node access modules, you can go down for this solution.


With both above points in mind you can uses something like this:

function MYMODULE_node_get_title_fast(array $nids) {
  $titles = &amp;drupal_static(__FUNCTION__, array());
  $return = array();
  $unavailable = array();
  foreach ($nids as $nid) {
    // Lookup static cache of self.
    if (array_key_exists($nid, $titles)) {
      $return[$nid] = $titles[$nid];
    }
    else { // Set NULL, so unavailable nodes will have NULL as their return value.
      $unavailable[$nid] = NULL;
    }
  }

  if ($unavailable) {
    $results = db_query("SELECT nid, title FROM {node} WHERE nid IN (:nids)", array(':nids' =&gt; array_keys($unavailable)))-&gt;fetchAllKeyed(0, 1);
    if ($results) {
      $return = $results + $unavailable;
      $titles = $return + $titles;
    }
  }

  return $return;
}


You can pass an array of node IDs, and the above function will return their titles without the overhead of node_load, field_attach, or entity_load overheads. It also skips node access checks, so do not use this in sites that you want any sort of access restrictions. 

Usage example:

 $titles = MYMODULE_node_get_title_fast(array(256, 258, 54898));


You would return an array, with all given array values as keys, and the title as their value. NULL if the node is unavailable.