3 * Class for fetching backlink lists, approximate backlink counts and
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; if not, write to the Free Software Foundation, Inc.,
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 * http://www.gnu.org/copyleft/gpl.html
22 * @author Tim Starling
23 * @copyright © 2009, Tim Starling, Domas Mituzas
24 * @copyright © 2010, Max Sem
25 * @copyright © 2011, Antoine Musso
28 use Wikimedia\Rdbms\FakeResultWrapper
;
29 use Wikimedia\Rdbms\IDatabase
;
30 use Wikimedia\Rdbms\IResultWrapper
;
31 use MediaWiki\MediaWikiServices
;
34 * Class for fetching backlink lists, approximate backlink counts and
35 * partitions. This is a shared cache.
37 * Instances of this class should typically be fetched with the method
38 * $title->getBacklinkCache().
40 * Ideally you should only get your backlinks from here when you think
41 * there is some advantage in caching them. Otherwise it's just a waste
44 * Introduced by r47317
47 /** @var BacklinkCache */
48 protected static $instance;
51 * Multi dimensions array representing batches. Keys are:
52 * > (string) links table name
54 * > 'numRows' : Number of rows for this link table
55 * > 'batches' : [ $start, $end ]
57 * @see BacklinkCache::partitionResult()
59 * Cleared with BacklinkCache::clear()
62 protected $partitionCache = [];
65 * Contains the whole links from a database result.
66 * This is raw data that will be partitioned in $partitionCache
68 * Initialized with BacklinkCache::getLinks()
69 * Cleared with BacklinkCache::clear()
70 * @var IResultWrapper[]
72 protected $fullResultCache = [];
80 * Local copy of a database object.
82 * Accessor: BacklinkCache::getDB()
83 * Mutator : BacklinkCache::setDB()
84 * Cleared with BacklinkCache::clear()
89 * Local copy of a Title object
93 const CACHE_EXPIRY
= 3600;
96 * Create a new BacklinkCache
98 * @param Title $title : Title object to create a backlink cache for
100 public function __construct( Title
$title ) {
101 $this->title
= $title;
102 $this->wanCache
= MediaWikiServices
::getInstance()->getMainWANObjectCache();
106 * Create a new BacklinkCache or reuse any existing one.
107 * Currently, only one cache instance can exist; callers that
108 * need multiple backlink cache objects should keep them in scope.
110 * @param Title $title Title object to get a backlink cache for
111 * @return BacklinkCache
113 public static function get( Title
$title ) {
114 if ( !self
::$instance ||
!self
::$instance->title
->equals( $title ) ) {
115 self
::$instance = new self( $title );
117 return self
::$instance;
121 * Serialization handler, diasallows to serialize the database to prevent
122 * failures after this class is deserialized from cache with dead DB
128 return [ 'partitionCache', 'fullResultCache', 'title' ];
132 * Clear locally stored data and database object. Invalidate data in memcache.
134 public function clear() {
135 $this->partitionCache
= [];
136 $this->fullResultCache
= [];
137 $this->wanCache
->touchCheckKey( $this->makeCheckKey() );
142 * Set the Database object to use
144 * @param IDatabase $db
146 public function setDB( $db ) {
151 * Get the replica DB connection to the database
152 * When non existing, will initialize the connection.
155 protected function getDB() {
156 if ( !isset( $this->db
) ) {
157 $this->db
= wfGetDB( DB_REPLICA
);
164 * Get the backlinks for a given table. Cached in process memory only.
165 * @param string $table
166 * @param int|bool $startId
167 * @param int|bool $endId
169 * @return TitleArrayFromResult
171 public function getLinks( $table, $startId = false, $endId = false, $max = INF
) {
172 return TitleArray
::newFromResult( $this->queryLinks( $table, $startId, $endId, $max ) );
176 * Get the backlinks for a given table. Cached in process memory only.
177 * @param string $table
178 * @param int|bool $startId
179 * @param int|bool $endId
181 * @param string $select 'all' or 'ids'
182 * @return IResultWrapper
184 protected function queryLinks( $table, $startId, $endId, $max, $select = 'all' ) {
185 $fromField = $this->getPrefix( $table ) . '_from';
187 if ( !$startId && !$endId && is_infinite( $max )
188 && isset( $this->fullResultCache
[$table] )
190 wfDebug( __METHOD__
. ": got results from cache\n" );
191 $res = $this->fullResultCache
[$table];
193 wfDebug( __METHOD__
. ": got results from DB\n" );
194 $conds = $this->getConditions( $table );
195 // Use the from field in the condition rather than the joined page_id,
196 // because databases are stupid and don't necessarily propagate indexes.
198 $conds[] = "$fromField >= " . intval( $startId );
201 $conds[] = "$fromField <= " . intval( $endId );
203 $options = [ 'ORDER BY' => $fromField ];
204 if ( is_finite( $max ) && $max > 0 ) {
205 $options['LIMIT'] = $max;
208 if ( $select === 'ids' ) {
209 // Just select from the backlink table and ignore the page JOIN
210 $res = $this->getDB()->select(
212 [ $this->getPrefix( $table ) . '_from AS page_id' ],
213 array_filter( $conds, function ( $clause ) { // kind of janky
214 return !preg_match( '/(\b|=)page_id(\b|=)/', $clause );
220 // Select from the backlink table and JOIN with page title information
221 $res = $this->getDB()->select(
223 [ 'page_namespace', 'page_title', 'page_id' ],
226 array_merge( [ 'STRAIGHT_JOIN' ], $options )
230 if ( $select === 'all' && !$startId && !$endId && $res->numRows() < $max ) {
231 // The full results fit within the limit, so cache them
232 $this->fullResultCache
[$table] = $res;
234 wfDebug( __METHOD__
. ": results from DB were uncacheable\n" );
242 * Get the field name prefix for a given table
243 * @param string $table
244 * @throws MWException
245 * @return null|string
247 protected function getPrefix( $table ) {
250 'imagelinks' => 'il',
251 'categorylinks' => 'cl',
252 'templatelinks' => 'tl',
256 if ( isset( $prefixes[$table] ) ) {
257 return $prefixes[$table];
260 Hooks
::run( 'BacklinkCacheGetPrefix', [ $table, &$prefix ] );
264 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
270 * Get the SQL condition array for selecting backlinks, with a join
272 * @param string $table
273 * @throws MWException
276 protected function getConditions( $table ) {
277 $prefix = $this->getPrefix( $table );
281 case 'templatelinks':
283 "{$prefix}_namespace" => $this->title
->getNamespace(),
284 "{$prefix}_title" => $this->title
->getDBkey(),
285 "page_id={$prefix}_from"
290 "{$prefix}_namespace" => $this->title
->getNamespace(),
291 "{$prefix}_title" => $this->title
->getDBkey(),
292 $this->getDB()->makeList( [
293 "{$prefix}_interwiki" => '',
294 "{$prefix}_interwiki IS NULL",
296 "page_id={$prefix}_from"
300 case 'categorylinks':
302 "{$prefix}_to" => $this->title
->getDBkey(),
303 "page_id={$prefix}_from"
308 Hooks
::run( 'BacklinkCacheGetConditions', [ $table, $this->title
, &$conds ] );
310 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
318 * Check if there are any backlinks
319 * @param string $table
322 public function hasLinks( $table ) {
323 return ( $this->getNumLinks( $table, 1 ) > 0 );
327 * Get the approximate number of backlinks
328 * @param string $table
329 * @param int $max Only count up to this many backlinks
332 public function getNumLinks( $table, $max = INF
) {
333 global $wgUpdateRowsPerJob;
335 // 1) try partition cache ...
336 if ( isset( $this->partitionCache
[$table] ) ) {
337 $entry = reset( $this->partitionCache
[$table] );
339 return min( $max, $entry['numRows'] );
342 // 2) ... then try full result cache ...
343 if ( isset( $this->fullResultCache
[$table] ) ) {
344 return min( $max, $this->fullResultCache
[$table]->numRows() );
347 $memcKey = $this->wanCache
->makeKey(
349 md5( $this->title
->getPrefixedDBkey() ),
353 // 3) ... fallback to memcached ...
355 $count = $this->wanCache
->get(
359 $this->makeCheckKey()
362 if ( $count && ( $curTTL > 0 ) ) {
363 return min( $max, $count );
366 // 4) fetch from the database ...
367 if ( is_infinite( $max ) ) { // no limit at all
368 // Use partition() since it will batch the query and skip the JOIN.
369 // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs.
370 $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache
371 return $this->partitionCache
[$table][$wgUpdateRowsPerJob]['numRows'];
372 } else { // probably some sane limit
373 // Fetch the full title info, since the caller will likely need it next
374 $count = $this->getLinks( $table, false, false, $max )->count();
375 if ( $count < $max ) { // full count
376 $this->wanCache
->set( $memcKey, $count, self
::CACHE_EXPIRY
);
380 return min( $max, $count );
384 * Partition the backlinks into batches.
385 * Returns an array giving the start and end of each range. The first
386 * batch has a start of false, and the last batch has an end of false.
388 * @param string $table The links table name
389 * @param int $batchSize
392 public function partition( $table, $batchSize ) {
393 // 1) try partition cache ...
394 if ( isset( $this->partitionCache
[$table][$batchSize] ) ) {
395 wfDebug( __METHOD__
. ": got from partition cache\n" );
397 return $this->partitionCache
[$table][$batchSize]['batches'];
400 $this->partitionCache
[$table][$batchSize] = false;
401 $cacheEntry =& $this->partitionCache
[$table][$batchSize];
403 // 2) ... then try full result cache ...
404 if ( isset( $this->fullResultCache
[$table] ) ) {
405 $cacheEntry = $this->partitionResult( $this->fullResultCache
[$table], $batchSize );
406 wfDebug( __METHOD__
. ": got from full result cache\n" );
408 return $cacheEntry['batches'];
411 $memcKey = $this->wanCache
->makeKey(
413 md5( $this->title
->getPrefixedDBkey() ),
418 // 3) ... fallback to memcached ...
420 $memcValue = $this->wanCache
->get(
424 $this->makeCheckKey()
427 if ( is_array( $memcValue ) && ( $curTTL > 0 ) ) {
428 $cacheEntry = $memcValue;
429 wfDebug( __METHOD__
. ": got from memcached $memcKey\n" );
431 return $cacheEntry['batches'];
434 // 4) ... finally fetch from the slow database :(
435 $cacheEntry = [ 'numRows' => 0, 'batches' => [] ]; // final result
436 // Do the selects in batches to avoid client-side OOMs (T45452).
437 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
438 $selectSize = max( $batchSize, 200000 - ( 200000 %
$batchSize ) );
441 $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' );
442 $partitions = $this->partitionResult( $res, $batchSize, false );
443 // Merge the link count and range partitions for this chunk
444 $cacheEntry['numRows'] +
= $partitions['numRows'];
445 $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
446 if ( count( $partitions['batches'] ) ) {
447 list( , $lEnd ) = end( $partitions['batches'] );
448 $start = $lEnd +
1; // pick up after this inclusive range
450 } while ( $partitions['numRows'] >= $selectSize );
451 // Make sure the first range has start=false and the last one has end=false
452 if ( count( $cacheEntry['batches'] ) ) {
453 $cacheEntry['batches'][0][0] = false;
454 $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
457 // Save partitions to memcached
458 $this->wanCache
->set( $memcKey, $cacheEntry, self
::CACHE_EXPIRY
);
460 // Save backlink count to memcached
461 $memcKey = $this->wanCache
->makeKey(
463 md5( $this->title
->getPrefixedDBkey() ),
466 $this->wanCache
->set( $memcKey, $cacheEntry['numRows'], self
::CACHE_EXPIRY
);
468 wfDebug( __METHOD__
. ": got from database\n" );
470 return $cacheEntry['batches'];
474 * Partition a DB result with backlinks in it into batches
475 * @param IResultWrapper $res Database result
476 * @param int $batchSize
477 * @param bool $isComplete Whether $res includes all the backlinks
478 * @throws MWException
481 protected function partitionResult( $res, $batchSize, $isComplete = true ) {
483 $numRows = $res->numRows();
484 $numBatches = ceil( $numRows / $batchSize );
486 for ( $i = 0; $i < $numBatches; $i++
) {
487 if ( $i == 0 && $isComplete ) {
490 $rowNum = $i * $batchSize;
491 $res->seek( $rowNum );
492 $row = $res->fetchObject();
493 $start = (int)$row->page_id
;
496 if ( $i == ( $numBatches - 1 ) && $isComplete ) {
499 $rowNum = min( $numRows - 1, ( $i +
1 ) * $batchSize - 1 );
500 $res->seek( $rowNum );
501 $row = $res->fetchObject();
502 $end = (int)$row->page_id
;
506 if ( $start && $end && $start > $end ) {
507 throw new MWException( __METHOD__
. ': Internal error: query result out of order' );
510 $batches[] = [ $start, $end ];
513 return [ 'numRows' => $numRows, 'batches' => $batches ];
517 * Get a Title iterator for cascade-protected template/file use backlinks
522 public function getCascadeProtectedLinks() {
523 $dbr = $this->getDB();
525 // @todo: use UNION without breaking tests that use temp tables
527 $resSets[] = $dbr->select(
528 [ 'templatelinks', 'page_restrictions', 'page' ],
529 [ 'page_namespace', 'page_title', 'page_id' ],
531 'tl_namespace' => $this->title
->getNamespace(),
532 'tl_title' => $this->title
->getDBkey(),
540 if ( $this->title
->getNamespace() == NS_FILE
) {
541 $resSets[] = $dbr->select(
542 [ 'imagelinks', 'page_restrictions', 'page' ],
543 [ 'page_namespace', 'page_title', 'page_id' ],
545 'il_to' => $this->title
->getDBkey(),
555 // Combine and de-duplicate the results
557 foreach ( $resSets as $res ) {
558 foreach ( $res as $row ) {
559 $mergedRes[$row->page_id
] = $row;
563 return TitleArray
::newFromResult(
564 new FakeResultWrapper( array_values( $mergedRes ) ) );
568 * Returns check key for the backlinks cache for a particular title
572 private function makeCheckKey() {
573 return $this->wanCache
->makeKey(
575 md5( $this->title
->getPrefixedDBkey() )